What is the maximum number of coins can be arranged in cells of the table $n \times n$ (each cell is not more of the one coin) so that any coin was not simultaneously below and to the right than any other?
Problem
Source: SRMC 2014
Tags: combinatorics proposed, combinatorics
01.04.2014 08:42
The conditions are unclear. Please elaborate.
02.04.2014 18:23
By below (and to the right), do you mean precisely below (in the same column), or just below (not necessarily in the same column)? Do you mean immediately below (in the row right afterward), or just below (not necessarily in the row right afterward)? Or in other terms: O. AB CD Which coins are below O?
09.04.2019 23:42
Its easy to see than no two coins can lie at the same diagonal(parallel to the diagonal from left upper corner to the right down corner).So the answer is $2n-1$(the total number of diagonals) and example follows.
18.09.2020 16:19
If the problem states that no two coins should be on the same row or column(which I doubt) then the answer is $n$ which is the obviously the maximum from the description and is possible when the coins are placed in one of the diagonals of the big square. Now if we are looking to place the coins in order for none of them to be immediately below or right to each other the we can achive the maximum by placing them in a chess order starting from $(1,1)$. And hence if we let $f(n)$ be the maximum number of coins we can place it is gonna be $f(n)=2\lfloor{\tfrac{n}{2}}\rfloor^2+2\lfloor{\tfrac{n}{2}}\rfloor+1$ if $n$ is odd $f(n)=\tfrac{n^2}{2}$ if $n$ is even.