An $n$-type triangle where $n\geqslant 2$ is formed by the cells of a $(2n+1)\times(2n+1)$ board, situated under both main diagonals. For instance, a $3$-type triangle looks like this:Determine the maximal length of a sequence with pairwise distinct cells in an $n$-type triangle, such that, beggining with the second one, any cell of the sequence has a common side with the previous one. Cristi Săvescu
Problem
Source: Romania JBMO TST 2024 Day 1 P5
Tags: combinatorics, board
31.07.2024 16:08
I claim that the answer is $n^2-n+1$. For the bounding, we color the figure in the chessboard way. Clearly each move goes from a white cell to a black cell or in the opposite way. Note that the total number of cells in one of the colors is $1+2+\dots+(n-1)=\frac{n^2-n}{2}$. Since the color changes in each turn, the total number of moves is at most $n^2-n$ and the maximum length of the sequence is $n^2-n+1$. You can find the construction for $n^2-n+1$ inductively. I’m on my phone but I’ll upload a figure showing it later!
22.09.2024 14:03
Let $P(n)$ be the maximal length of the sequence in $n$-type triangle, then $P(n+1)$ is equal to $P(n)+2n$ because the bottom will consist of $2n+1$ cells and we can't go through the row fully, at least one cell should be skipped if not then the sequence won't be pairwise distinct and we will go through one cell another time.So, $P(n+1)=P(n)+2n$ considering that $P(2)=3, P(n)=n^2-n+1.$ Now we should see if this is possible,consider a snake that will start at the top of $n$-type triangle and will go down, going from $k$th to $k+1$th row snake will go as left as prossible if in $k$th row it ended at the furthest right cell and vice versa. This way $n^2-n+1$ can be achieved and we are done.
11.01.2025 15:23
The answer is $n^2-n+1$ $Proof:$ By checking the base cases like $1,2…$ we conclude that $a_n=n^2-n+1$ Now let us prove it by induction: Assume it is true for $n$,then add one extra line depending on the construction we either go left or right in the construction and skip one square,by that we color $2n$ squares. Solving this reccurence relation gives that $a_n=n^2-n+1$ Construction: $\begin{vmatrix} & & \boxed{C} & & \\ & \boxed{} &\boxed{C} &\boxed{C} & \\ \boxed{C} &\boxed{C} &\boxed{C} &\boxed{C} &\boxed{} \\ & & & & \end{vmatrix} $