Maths Olympiad Prep

Library / /150 of 299

Combinatorics Difficulty 6.5 National Olympiad Prove it Iran

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 55. For the example consider the following table (see the cover photo of the booklet).
aij={2i1(mod8)5i4,5(mod8)4i0(mod8) or i7(mod8) and j≢2,5(mod6)1i3(mod8) and j≢2,5(mod6)3otherwise. a_{ij} = \begin{cases} 2 & i \equiv 1 \pmod{8} \\ 5 & i \equiv 4, 5 \pmod{8} \\ 4 & i \equiv 0 \pmod{8} \text{ or } i \equiv 7 \pmod{8} \text{ and } j \not\equiv 2, 5 \pmod{6} \\ 1 & i \equiv 3 \pmod{8} \text{ and } j \not\equiv 2, 5 \pmod{6} \\ 3 & \text{otherwise.} \end{cases}
Where aija_{ij} is the number written in the cell (i,j)(i, j).

To prove that 55 is maximum, note that if there is one 88 in this table all other cells should be 88. If there is a 77 in this table then it has a neighbor aa which is not 77, and aa should have a neighbour bb which is not 77. Now none of the common neighbors of a,ba, b can be 77. But it is easy to see that a,ba, b has a common neighbor with number 77 which is a contradiction. Hence, 77 can not appear in this table.

Assume that all the numbers {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\} will appear in this table. Define the taxi-cab distance between (i,j)(i, j) and (i,j)(i', j') to be ii+jj|i - i'| + |j - j'|. Let ai,j=5a_{i',j'} = 5 and (i,j)(i,j) be a cell with number 66 with minimal taxi-cab distance with (i,j)(i', j'). We claim that ii+jj=1|i - i'| + |j - j'| = 1 which is equivalent to say that (i,j)(i, j) and (i,j)(i', j') have a common edge.

To prove the claim, note that if iii \neq i' and jjj \neq j', because of symmetry we may assume i>ii > i', j>jj > j'. Note that we have ai+1,j=6a_{i+1,j} = 6 or ai,j+1=6a_{i,j+1} = 6 or ai+1,j+1=6a_{i+1,j+1} = 6 and all these three cells have less taxi-cab distance with (i,j)(i', j') than (i,j)(i, j). So every cell filled with number 66 having minimal taxi-cab distance to (i,j)(i', j') should be in the same row or column with this cell. Suppose that j=jj = j' and i<ii < i'. Now, we have ai+1,j+1=6a_{i+1,j+1} = 6 or ai+1,j=6a_{i+1,j} = 6 or ai+1,j1=6a_{i+1,j-1} = 6. But all three cases are impossible. Indeed ai+1,j=6a_{i+1,j} = 6 contradicts minimality of taxi-cab distance from (i,j)(i,j) to (i,j)(i',j'), and ai+1,j±1=6a_{i+1,j \pm 1} = 6 contradicts the observation above that cells with number 66 and minimal distance to (i,j)(i',j') should be in the same row or column. So the claim is proved.

Now consider the two adjacent cells with numbers 6,56,5. These two cells have 1010 neighbors in total, 66 of them should be 66 and 55 of them should be 55 which is impossible. Thus, the maximum possible number is 55 and the solution is complete.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.