Browse · MathNet
PrintAPMO
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?

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:
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.
Lemma 1. There is a board that stays constant modulo and whose entries are not all equal.
Proof. Here is one such a board:
| 3 | 1 | 3 |
|---|---|---|
| 0 | 2 | 0 |
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