Maths Olympiad Prep

Library / Asian Pacific Mathematics Olympiad /36 of 55

Asian Pacific Mathematics Olympiad

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:

313
020

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 r≥2,s≥2r \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 a≡3−1(b+c+d)≡2(b+c+d) ( mod 5)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
4−1(a+b+c+d)≡4(a+b+c+d)≡4a+2a≡a ( mod 5) 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 a≡2−1(b+c)≡3(b+c) ( mod 5)a \equiv 2^{-1}(b+c) \equiv 3(b+c)\ (\bmod 5). If the reflections add one aa as neighbor, now
3−1(a+b+c)≡2(3(b+c)+b+c)≡8(b+c)≡3(b+c)≡a ( mod 5) 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 a≡2−1(b+c) ( mod 5)a \equiv 2^{-1}(b+c)\ (\bmod 5). If the reflections add two aa's as neighbors, now
4−1(2a+b+c)≡(2−1a+2−1a)≡a ( mod 5) 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 2∣20182 \mid 2018 and 3∣20193 \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.