Maths Olympiad Prep

Library / /11 of 11

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Romania

An nn-type tiles triangle, where n2n \geq 2, is formed by the cells of a (2n+1)×(2n+1)(2n + 1) \times (2n + 1) array which are situated below its diagonals. For instance, a 3-type tiles triangle is the following:
Figure 1
Determine the maximal length of a sequence with pairwise distinct cells in an nn-type tiles triangle, such that, beginning with the second one, any cell of the sequence has a common side with the previous one.

Solution

We alternately color (as a chessboard) the cells of an nn-type tiles triangle, as below:
Figure 2
We have bn=1+2++n=n(n+1)2b_n = 1 + 2 + \ldots + n = \frac{n(n+1)}{2} black cells and an=1+2++(n1)=n(n1)2a_n = 1 + 2 + \ldots + (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(an+1)2(a_n + 1). Therefore, we infer that the maximal length of such a sequence is Ln2n+1L \leq n^2 - n + 1.

To complete the solution, we now provide an example of a sequence in an nn-type tiles triangle which satisfies the required condition and has length L=n2n+1L = 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:
Figure 3
The length of a sequence as we described before is: 1+2+4++2(n1)=1+n(n1)=n2n+11 + 2 + 4 + \ldots + 2(n - 1) = 1 + n(n - 1) = n^2 - n + 1.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.