Maths Olympiad Prep

Library / /2 of 4

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Italy

Problem:

Alberto chooses 2022 integers a1,a2,,a2022a_{1}, a_{2}, \ldots, a_{2022} (not necessarily positive and not necessarily distinct) and arranges them on a 2022×20222022 \times 2022 table so that in cell (i,j)(i, j) there is the number aka_{k}, with kk equal to the maximum between ii and jj, as in the following figure (in which, for greater readability, we have denoted a2022a_{2022} by ana_{n}).

a1a_{1}a2a_{2}a3a_{3}a4a_{4}a5a_{5}ana_{n}
a2a_{2}a2a_{2}a3a_{3}a4a_{4}a5a_{5}ana_{n}
a3a_{3}a3a_{3}a3a_{3}a4a_{4}a5a_{5}ana_{n}
a4a_{4}a4a_{4}a4a_{4}a4a_{4}a5a_{5}ana_{n}
a5a_{5}a5a_{5}a5a_{5}a5a_{5}a5a_{5}ana_{n}
. . .ana_{n}
ana_{n}ana_{n}ana_{n}ana_{n}ana_{n}ana_{n}ana_{n}

Barbara does not know the numbers chosen by Alberto, but she knows how they were arranged in the table. Having fixed an integer kk, with 1k20221 \leq k \leq 2022, Barbara wants to determine the value of aka_{k}, while she is not interested in determining the values of the other aia_{i} with iki \neq k. To do this, Barbara can ask Alberto one or more questions, in each of which she asks Alberto what the sum of the numbers contained in the cells of a "path" is, where by the term "path" we mean an ordered list of cells with the following characteristics:
- the path starts with the top-left cell and ends with the bottom-right cell,
- the cells of the path are all distinct,
- two consecutive cells of the path always share a side.

Determine, as kk varies, the minimum number of questions Barbara needs to determine aka_{k}.

Solution

Solution:

For every admissible kk, the minimum number of paths needed to determine aka_{k} with certainty is two.

One path is not enough
Consider a path, and denote by cic_{i} the number of cells containing the value aia_{i} traversed by the path. We observe that ci1c_{i} \geq 1 for every ii and the sum equals
S=c1a1++ckak++c2022a2022. S = c_{1} a_{1} + \ldots + c_{k} a_{k} + \ldots + c_{2022} a_{2022}.
Now Barbara knows the coefficients c1,,c2022c_{1}, \ldots, c_{2022}, and would like to determine the number aka_{k} uniquely. Suppose we have found this value of aka_{k}, and choose an index hkh \neq k. One verifies that the sum SS does not change if aka_{k} is replaced by ak+cha_{k} + c_{h}, and aha_{h} is replaced by ahcka_{h} - c_{k}, leaving all the other aia_{i} unchanged. This shows that there is never a unique value of aka_{k} that is compatible with the given sum.

Two paths are enough when 2k20222 \leq k \leq 2022
Consider the path PP that traverses the first row to the right until it reaches aka_{k}, then moves down into the second row and goes back until the first column, then moves down to the last row and finally moves to the right until the destination. Also consider the path PP' analogous to the previous one, with the only difference that the first "turn" happens one move earlier, that is, when the path reaches the cell with ak1a_{k-1} (in the case k=2k=2 this means that the path PP' moves directly downward).

The following figure represents the two paths in the special case k=5k=5 (for simplicity we have written ana_{n} instead of a2022a_{2022}).

Figure 1

Path PP

Figure 2

Path PP'

The only difference between the two paths is that PP has two more cells with aka_{k}. Denoting by SS and SS' the sums over the two paths, it follows that
SS=2ak S - S' = 2 a_{k}
from which the value of aka_{k} is immediately obtained.

Two paths are enough when k=1k=1
Consider the two paths PP and PP' that start by going from the initial cell to cell (4,4)(4,4) in this way.
- Path PP makes in succession two moves to the right, one downward, one to the right, and finally two downward.
- Path PP' traverses the entire first row, then descends into the second row and goes back to the second cell of the second row, then makes one move downward, one to the left, one downward, and finally traverses the fourth row to the right up to cell (4,4)(4,4).

From cell (4,4)(4,4) to the end the two paths continue in the same way, always alternating one move to the right and one downward. In this way the two sums turn out to be
S=a1+a2+2a3+3a4+2(a5++a2022) S = a_{1} + a_{2} + 2 a_{3} + 3 a_{4} + 2(a_{5} + \ldots + a_{2022})
and
S=a1+2a2+4a3+6a4+4(a5++a2022) S' = a_{1} + 2 a_{2} + 4 a_{3} + 6 a_{4} + 4(a_{5} + \ldots + a_{2022})
from which it follows that
2SS=a1 2S - S' = a_{1}

Figure 3

Path PP

Figure 4

Path PP'

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 translated into English from it; metadata (topic, difficulty) added by this project.