74th NMO Selection Tests for JBMO

We alternately color (as a chessboard) the cells of an $n$-type tiles triangle, as below: We have $b_n=1+2+\dots +n=\frac{n(n+1)}{2}$ black cells and $a_n=1+2+\dots +(n-1)=\frac{n(n-1)}{2}$ white cells. In any sequence of cells with the required propriety, their color alternates, hence its length cannot exceed $2(a_n+1)$. Therefore, we infer that the maximal length of such a sequence is $L\le n^2-n+1$.

To complete the solution, we now provide an example of a sequence in an $n$-type tiles triangle which satisfies the required condition and has length $L=n^2-n+1$. We consider a sequence of cells which begins with the top cell. At each step, we choose the cell below the last cell chosen in the previous step, together with a maximum length sequence of cells situated on the same line, up to one of its ends. For instance, for a 3-type tiles triangle the following succession is a solution: The length of a sequence as we described before is: $1+2+4+\dots +2(n-1)=1+n(n-1)=n^2-n+1$.

Therefore, the answer is $L=n^2-n+1$.