NMO Selection Tests for the Junior Balkan Mathematical Olympiad

Look at two contiguous rows of a $2n\times 2n$ array, containing $k$ diagonals in the cells of row $A$ and $\ell$ diagonals in the cells of row $B$. The ends of these diagonals on the separating line of the two rows have to be distinct points, and they can only occupy at most the $2n+1$ available positions, therefore $k+\ell \le 2n+1$. Since the $2n$ rows may be grouped in $n$ sets of pairwise contiguous rows, the total number of diagonals drawn in the array is at most $n(2n+1)=\left(\genfrac{}{}{0ex}{}{2n+1}{2}\right)$. A model is easily found – only use / type diagonals in the cells of coordinates $(2i+1,j)$ and $(j,2i+1)$, with $1\le 2i+1\le j\le 2n$. The answer for $2n=8$ is therefore $36$.

Alternative Solution.

Colour the nodes of the array alternatively white and black by columns, starting with the left side. Any diagonal drawn will then have its ends of different colour. Since there are exactly $n(2n+1)$ black nodes (while there are $(n+1)(2n+1)$ white nodes), and all diagonals are disjoint, it follows the total number of diagonals drawn in the array is at most $n(2n+1)=\left(\genfrac{}{}{0ex}{}{2n+1}{2}\right)$. At close inspection, it is virtually the same idea as above, in a more elegant setting.