Skip to main content
OlympiadHQ

Browse · MathNet

Print

APMO

counting and probability

Problem

Consider a 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?

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

Lemma 1. There is a board that stays constant modulo 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.

Lemma 2. If there is an board with , that stays constant modulo , then there is also a board with the same property.

Proof. We prove by a case by case analysis that repeatedly reflecting the with respect to an edge preserves the property:

- If a cell had neighbors, after reflections it still has the same neighbors. - If a cell with had neighbors , we have by hypothesis that . A reflection may add as a neighbor of the cell and now - If a cell with had neighbors , we have by hypothesis that . If the reflections add one as neighbor, now - If a cell with had neighbors , we have by hypothesis that . If the reflections add two 's as neighbors, now

In the three cases, any cell is still preserved modulo after an operation. Hence we can fill in the board by copies by reflection.

Since and , we can get through reflections the following board:



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

Techniques

Invariants / monovariantsInverses mod n