The numbers from $1$ to $100$ are placed without repetition in each cell of a \(10 \times 10\) board. An increasing path of length \(k\) on this board is a sequence of cells \(c_1, c_2, \ldots, c_k\) such that, for each \(i = 2, 3, \ldots, k\), the following properties are satisfied: • The cells \(c_i\) and \(c_{i-1}\) share a side or a vertex; • The number in \(c_i\) is greater than the number in \(c_{i-1}\). What is the largest positive integer \(k\) for which we can always find an increasing path of length \(k\), regardless of how the numbers from 1 to 100 are arranged on the board?
Problem
Source: Brazilian Mathematical Olympiad 2024, Level 2, Problem 3
Tags: combinatorics, board
Bonime
13.10.2024 00:59
The answer is $k=4$. Note, first, that every board configuration guarantees an increasing path of length 4: just look at any subboard $2\times2$. All the squares will be connected to each other and there must be an increasing order of the numbers of these squares, which will give us an increasing path of length 4. Let us then show a configuration in which it is not possible to obtain $k\geq4$: Divide the board $10\times10$ into $25$ subboards $2\times2$, and, in each subboard, color it as follows. However, note that this coloring ensures that two houses with the same letter do not have a vertex or side in common, so we just need to position the numbers from 76 to 100 in the houses with the letter $A$, the numbers from 51 to 75 in the houses with the letter $B$, those from 26 to 50 in the houses with the letter $C$ and finally, those from 1 to 25 in the houses with the letter $D$. Once this is done, note that houses with the letter $A$ must end an increasing path; with the letter $B$, they must be the penultimate, since they can only be predecessors of houses with the letter $A$; with the letter $C$, they must be predecessors of houses with the letter $B$, or with the letter $A$ and houses with the letter $D$ must be the predecessors of houses with the letter $C, B$ or $A$. Therefore, every increasing path must end in a house with the letter $A$, and in this configuration, the largest increasing path of length 4 is given by the path $D-C-B-A$.
Attachments:
