Competition problem — Combinatorics

Library / /8 of 16

Combinatorics Difficulty 6.3 National olympiad Prove it Argentina

Consider a $99 \times 99$ table with its columns and rows labelled $1$ to $99$ from left to right and bottom to top respectively. Lucía writes the numbers from $1$ to $3160$ in increasing order by steps, in the following way:

| | | | | | | | | | |
|--------|----|----|----|----|----|----|----|----|----|
| Row 4 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | | |
| Row 3 | 26 | 9 | 10 | 11 | 12 | 13 | 18 | | |
| Row 2 | 27 | 8 | 5 | 4 | 3 | 14 | 17 | | |
| Row 1 | 28 | 7 | 6 | 1 | 2 | 15 | 16 | | |
| | 47 | 48 | 49 | 50 | 51 | 52 | 53 | | |

* Number $1$ is in the cell of row $1$ and column $50$ .

* In the first step, she fills every cell which is a neighbor of $1$ , anti-clockwise.
* In the second step, she fills every cell which is a neighbor of any cell filled in the previous step, clockwise.
* She continues this way in each step, filling the cells that are neighbors of the cells filled in the previous step and changing the orientation.

The figure shows the table after Lucía completed the first three steps.
In which step will Lucía write the number $2022$ ? In which row and which column is $2022$ written?

Solution

First, let us observe that every step contains four more numbers than the previous one. In fact, the number of cells filled in step $k$ is $4k + 1$ . After $31$ steps, there are $1+5+7+...+(4 \cdot 31+1) = 2016$ numbers in the table. We can compute that sum by multiplying by $4$ the sum of the numbers from $1$ to $31$ and then adding $32$ .

On the other hand, after $32$ steps there are $2016+(4 \cdot 32+1) = 2145$ numbers in the table. Hence, $2022$ is written in step $32$ .

Now, notice that the last number written in step $31$ is $2016$ and, since $31$ is odd, in that step the numbers were filled anti-clockwise, so $2016$ is in column $50 - 31 = 19$ and row $1$ . Finally, since the numbers of step $32$ are filled clockwise, $2022$ is in column $18$ and row $6$ .

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.