Natural numbers are placed in the cells of an infinite grid, such that the number in each cell is equal to the number of its adjacent cells having the same number (two cells of the grid are adjacent if they have a common vertex). Find the maximum value of distinct numbers this infinite grid can have.
Solution
The answer is . For the example consider the following table (see the cover photo of the booklet).
Where is the number written in the cell .
To prove that is maximum, note that if there is one in this table all other cells should be . If there is a in this table then it has a neighbor which is not , and should have a neighbour which is not . Now none of the common neighbors of can be . But it is easy to see that has a common neighbor with number which is a contradiction. Hence, can not appear in this table.
Assume that all the numbers will appear in this table. Define the taxi-cab distance between and to be . Let and be a cell with number with minimal taxi-cab distance with . We claim that which is equivalent to say that and have a common edge.
To prove the claim, note that if and , because of symmetry we may assume , . Note that we have or or and all these three cells have less taxi-cab distance with than . So every cell filled with number having minimal taxi-cab distance to should be in the same row or column with this cell. Suppose that and . Now, we have or or . But all three cases are impossible. Indeed contradicts minimality of taxi-cab distance from to , and contradicts the observation above that cells with number and minimal distance to should be in the same row or column. So the claim is proved.
Now consider the two adjacent cells with numbers . These two cells have neighbors in total, of them should be and of them should be which is impossible. Thus, the maximum possible number is and the solution is complete.