Maths Olympiad Prep

Library / /33 of 48

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Consider a 2018×20192018 \times 2019 board with integers in each unit square. Two unit squares are said to be neighbours if they share a common edge. In each turn, you choose some unit squares. Then for each chosen unit square the average of all its neighbours is calculated. Finally, after these calculations are done, the number in each chosen unit square is replaced by the corresponding average. Is it always possible to make the numbers in all squares become the same after finitely many turns?

Solution

Let nn be a positive integer relatively prime to 22 and 33. We may study the whole process modulo nn by replacing divisions by 2,3,42,3,4 with multiplications by the corresponding inverses modulo nn. If at some point the original process makes all the numbers equal, then the process modulo nn will also have all the numbers equal. Our aim is to choose nn and an initial configuration modulo nn for which no process modulo nn reaches a board with all numbers equal modulo nn. We split this goal into two lemmas.

Lemma 1. There is a 2×32 \times 3 board that stays constant modulo 55 and whose entries are not all equal.

Proof. Here is one such a board:

| 3 | 1 | 3 |
| :--- | :--- | :--- |
| 0 | 2 | 0 |

The fact that the board remains constant regardless of the choice of squares can be checked square by square. \square

Lemma 2. If there is an r×sr \times s board with r2,s2r \geq 2, s \geq 2, that stays constant modulo 55, then there is also a kr×lsk r \times l s board with the same property.

Proof. We prove by a case by case analysis that repeatedly reflecting the r×sr \times s with respect to an edge preserves the property:

- If a cell had 44 neighbors, after reflections it still has the same neighbors.
- If a cell with aa had 33 neighbors b,c,db, c, d, we have by hypothesis that a31(b+c+d)2(b+c+d) (mod5)a \equiv 3^{-1}(b+c+d) \equiv 2(b+c+d)\ (\bmod 5). A reflection may add aa as a neighbor of the cell and now
41(a+b+c+d)4(a+b+c+d)4a+2aa (mod5) 4^{-1}(a+b+c+d) \equiv 4(a+b+c+d) \equiv 4a+2a \equiv a\ (\bmod 5)
- If a cell with aa had 22 neighbors b,cb, c, we have by hypothesis that a21(b+c)3(b+c) (mod5)a \equiv 2^{-1}(b+c) \equiv 3(b+c)\ (\bmod 5). If the reflections add one aa as neighbor, now
31(a+b+c)2(3(b+c)+b+c)8(b+c)3(b+c)a (mod5) 3^{-1}(a+b+c) \equiv 2(3(b+c)+b+c) \equiv 8(b+c) \equiv 3(b+c) \equiv a\ (\bmod 5)
- If a cell with aa had 22 neighbors b,cb, c, we have by hypothesis that a21(b+c) (mod5)a \equiv 2^{-1}(b+c)\ (\bmod 5). If the reflections add two aa's as neighbors, now
41(2a+b+c)(21a+21a)a (mod5) 4^{-1}(2a+b+c) \equiv (2^{-1}a+2^{-1}a) \equiv a\ \quad(\bmod 5)

In the three cases, any cell is still preserved modulo 55 after an operation. Hence we can fill in the kr×lsk r \times l s board by k×lk \times l copies by reflection. \square

Since 220182 \mid 2018 and 320193 \mid 2019, we can get through reflections the following board:

Figure 1

By the lemmas above, the board is invariant modulo 55, so the answer is no.

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.