The answer is $6$ which can be achieved through the following blocks of numbers: block A: 330 331 441 444 block B: 5 5 block C: 12033 12233 We can put an infinite row of blocs A, an infinite row of blocks B, an infinite row of blocks C, an infinite row of blocks B, and we repeat this exact pattern. Now assume there is a cell with a number $\geq 6$ (wlog say $6$, since it is the worst case). Since there has to be $6$ $6$s near it, there is at least one in each "direction"(the three blocks to the left, right,..., but also the three blocks to the right or up or up-tight, etc). Therefore we can "travel" from a $6$ to another $5$ or another number $\geq 5$ (different from $6$) through a chain of $6$s (we can always decrease the Manhattan distance except when the $6$ and the other number are vertically/horizontally aligned but in that case we can decrease the distance in another move). Therefore we can eventually have a $6$ and a number $\geq 5$ (wlog $5$ which is the worst case) horizontally/vertically nearby. At this point we have $10$ total "free" neighbours to $6$ and $5$ but we have $6+5=11>10$ cells to occupy, and so we get a contradiction. Therefore, there can only be one number which is $\geq 5$. This means that there are at most $5+1=6$ distinct numbers, and so we are done.

No zero?

cadaeibf wrote: The answer is $6$ which can be achieved through the following blocks of numbers: block A: 330 331 441 444 block B: 5 5 block C: 12033 12233 We can put an infinite row of blocs A, an infinite row of blocks B, an infinite row of blocks C, an infinite row of blocks B, and we repeat this exact pattern. Now assume there is a cell with a number $\geq 6$ (wlog say $6$, since it is the worst case). Since there has to be $6$ $6$s near it, there is at least one in each "direction"(the three blocks to the left, right,..., but also the three blocks to the right or up or up-tight, etc). Therefore we can "travel" from a $6$ to another $5$ or another number $\geq 5$ (different from $6$) through a chain of $6$s (we can always decrease the Manhattan distance except when the $6$ and the other number are vertically/horizontally aligned but in that case we can decrease the distance in another move). Therefore we can eventually have a $6$ and a number $\geq 5$ (wlog $5$ which is the worst case) horizontally/vertically nearby. At this point we have $10$ total "free" neighbours to $6$ and $5$ but we have $6+5=11>10$ cells to occupy, and so we get a contradiction. Therefore, there can only be one number which is $\geq 5$. This means that there are at most $5+1=6$ distinct numbers, and so we are done. $0$ is not a natural number

Mr.C wrote: cadaeibf wrote: The answer is $6$ which can be achieved through the following blocks of numbers: block A: 330 331 441 444 block B: 5 5 block C: 12033 12233 We can put an infinite row of blocs A, an infinite row of blocks B, an infinite row of blocks C, an infinite row of blocks B, and we repeat this exact pattern. Now assume there is a cell with a number $\geq 6$ (wlog say $6$, since it is the worst case). Since there has to be $6$ $6$s near it, there is at least one in each "direction"(the three blocks to the left, right,..., but also the three blocks to the right or up or up-tight, etc). Therefore we can "travel" from a $6$ to another $5$ or another number $\geq 5$ (different from $6$) through a chain of $6$s (we can always decrease the Manhattan distance except when the $6$ and the other number are vertically/horizontally aligned but in that case we can decrease the distance in another move). Therefore we can eventually have a $6$ and a number $\geq 5$ (wlog $5$ which is the worst case) horizontally/vertically nearby. At this point we have $10$ total "free" neighbours to $6$ and $5$ but we have $6+5=11>10$ cells to occupy, and so we get a contradiction. Therefore, there can only be one number which is $\geq 5$. This means that there are at most $5+1=6$ distinct numbers, and so we are done. $0$ is not a natural number We can easily fix the strategy. Take instead the following blocks: A: 5 5 B: 333 344 444 C: 333 312 212 Now take 4 infinite rows of blocks A,B,A,C and repeat this pattern infinitely many times. Once again, we can't have more than one distinct number $\geq 5$, and so we can have at most $5$ distinct numbers, so this is the maximum.

Iran TST 2021 Second Exam/1 wrote: Natural numbers are placed in an infinite grid such that the number in each cell is equal to the number of its adjacent cells having the same number. Find the maximal number of distinct numbers this infinite grid can have. (Two cells of the grid are adjacent if they have a common vertex) Redefine adjacent cells as neighbors. We call two cells $A$ and $B$ a friend if and only if $A$ and $B$ are adjacent, and $A$ and $B$ have the same number. From the problem itself, for any cell $A$, there is always a cell $B$ such that $A$ and $B$ is a friend. Let $\mathcal{S}$ be the set of numbers used in the infinite grid. We want to maximize $|\mathcal{S}|$. Claim 01. If $a \in \mathcal{S}$ and $|\mathcal{S}| \ge 2$, then $a \in \{1, 2, 3, 4, 5, 6 \}$. Proof. Notice that if $a \in \mathcal{S}$, then $a$ must satisfy $a \le |\text{Number of Neighbors}| = 8$. If $ 8 \in \mathcal{S}$, take a cell of number $8$. Then, all of its neighbor must have the number $8$ as well, and so, repeating the process, all numbers in the infinite grid must have number $8$, contradicting $|\mathcal{S}| \ge 2$, a contradiction. If $7 \in \mathcal{S}$, then take a cell $A$ of number $7$. By definition, exactly one of its neighbors must have number not equal to $7$. Let this be $B$. Notice that $B$ has a friend, and let it be cell $C$. We claim that any cell adjacent to $2$ cells that is not of number $7$ can''t have the number $7$. Indeed, otherwise, let the cell of number $7$ be $Z$. These two cells don't have the number $7$, which means that there are $2$ non-$7$ number in this cell $Z$'s neighbors, which is a contradiction. As $B$ has at least a friend, we can keep applying this claim until it forces all of $B$'s neighbors to be not $7$, which is a contradiction. Claim 02. $|\mathcal{S}| < 6$. Proof. Indeed, suppose that there exists an infinite grid such that $|\mathcal{S}| = 6$. This means that all numbers from $1$ to $6$ inclusive are used. This means that there is a cell of number $6$ and a cell of number $5$. We claim that there exists two cells of number $6$ and number $5$ that are adjacent and lie on the same row/column. Indeed, consider cell $A$ that has the minimum Manhattan distance to this cell of number $5$. If more than one exists, consider the one that is not the same row or column with the current cell of number $5$. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \draw[fill=blue] (0,0) circle (3 pt); \draw[fill=red] (0,-1) circle (3 pt); \draw[fill=red] (1,-1) circle (3 pt); \draw[fill=red] (1,-2) circle (3 pt); \draw[fill=blue] (1,0) circle (3 pt); \draw[fill = blue] (2,0) circle (3 pt); \draw[fill = blue] (2,-1) circle (3 pt); \draw[fill = blue] (2,-2) circle (3 pt); \draw[fill = blue] (3,0) circle (3 pt); \draw[fill = blue] (3,-1) circle (3 pt); \draw[fill = blue] (3,-2) circle (3 pt); \draw[fill = blue] (4,-1) circle (3 pt); \draw[fill = blue] (4,-2) circle (3 pt); \node[black, font = \small] at (0,-2) {$6$}; \node[black, font = \small] at (4,0) {$5$}; \end{tikzpicture}");[/asy][/asy] Consider the illustration above for better visualization. Now, look at the neighboring cells of the cell numbered $6$ that has a more minimal Manhattan distance. (which is colored red for the above illustration). Since cell $6$ has $6$ neighbors, at least one of the red colored neighbors, and this has a more minimal Manhattan distance. Therefore, we know that if $A$ has a minimal Manhattan distance to this cell of number $5$, then it must be unique and they must be on the same row or column. WLOG they are on the same row. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \node[black, font = \small] at (0,0) {$6$}; \draw[fill=red] (1,0) circle (3 pt); \draw[fill=red] (1,1) circle (3 pt); \draw[fill=red] (1,-1) circle (3 pt); \draw[fill=blue] (2,0) circle (3 pt); \draw[fill = blue] (2,1) circle (3 pt); \draw[fill = blue] (2,-1) circle (3 pt); \draw[fill = blue] (3,0) circle (3 pt); \draw[fill = blue] (3,1) circle (3 pt); \draw[fill = blue] (3,-1) circle (3 pt); \node[black, font = \small] at (4,0) {$5$}; \end{tikzpicture}");[/asy][/asy] We have assumed that they are not adjacent. Now consider the three adjacent cells (which are colored red). Notice that one of these three red cells must have number $6$. But, they must all have the same or less Manhattan distance than the current cell, which is a contradiction as we have proved that such cell must be unique. Therefore, there must exists two cells of number $6$ and number $5$ that are on the same row/column. Now, consider the following illustration. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \node[black, font = \small] at (0,0) {$6$}; \node[black, font = \small] at (1,0) {$5$}; \draw[fill = blue] (-1,0) circle (3 pt); \draw[fill = green] (0,1) circle (3 pt); \draw[fill = blue] (-1,1) circle (3 pt); \draw[fill = green] (0,-1) circle (3 pt); \draw[fill = blue] (-1,-1) circle (3 pt); \draw[fill = green] (1,1) circle (3 pt); \draw[fill = green] (1,-1) circle (3 pt); \draw[fill = yellow] (2,1) circle (3 pt); \draw[fill = yellow] (2,0) circle (3 pt); \draw[fill = yellow] (2,-1) circle (3 pt); \end{tikzpicture}");[/asy][/asy] Notice that there must be $5$ number of cells numbered $5$ among both the green and yellow colored cells, and there must be $6$ number of cells numbered $6$ among both the green and blue colored cells. However, \[ 11 > |\text{Total number of colored cells}| = 10 \]which results to a contradiction. Claim 03. $|\mathcal{S}| \le 5$ and equality can hold. Proof. From the previous two claims, we established that $|\mathcal{S}| \le 5$. Now, we will construct a grid such that $|\mathcal{S}| = 5$, using numbers from the set $\{ 1, 2, 3, 4, 5 \}$. Indeed, tesselate the following grid onto the infinite grid, and it is easy to check that this indeed satisfies the requirement, and hence, we are done. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \node[black, font = \small] at (-2,3) {$2$}; \node[black, font = \small] at (-1,3) {$2$}; \node[black, font = \small] at (0,3) {$2$}; \node[black, font = \small] at (1,3) {$2$}; \node[black, font = \small] at (2,3) {$2$}; \node[black, font = \small] at (3,3) {$2$}; \node[green, font = \small] at (-2,2) {$3$}; \node[green, font = \small] at (-1,2) {$3$}; \node[green, font = \small] at (0,2) {$3$}; \node[green, font = \small] at (1,2) {$3$}; \node[green, font = \small] at (2,2) {$3$}; \node[green, font = \small] at (3,2) {$3$}; \node[green, font = \small] at (-1,1) {$3$}; \node[green, font = \small] at (2,1) {$3$}; \node[red, font = \small] at (-2,1) {$1$}; \node[red, font = \small] at (0,1) {$1$}; \node[red, font = \small] at (1,1) {$1$}; \node[red, font = \small] at (3,1) {$1$}; \node[violet, font = \small] at (-2,0) {$5$}; \node[violet, font = \small] at (-1,0) {$5$}; \node[violet, font = \small] at (0,0) {$5$}; \node[violet, font = \small] at (1,0) {$5$}; \node[violet, font = \small] at (2,0) {$5$}; \node[violet, font = \small] at (3,0) {$5$}; \node[violet, font = \small] at (-2,-1) {$5$}; \node[violet, font = \small] at (-1,-1) {$5$}; \node[violet, font = \small] at (0,-1) {$5$}; \node[violet, font = \small] at (1,-1) {$5$}; \node[violet, font = \small] at (2,-1) {$5$}; \node[violet, font = \small] at (3,-1) {$5$}; \node[green, font = \small] at (-2,-2) {$3$}; \node[green, font = \small] at (-1,-2) {$3$}; \node[green, font = \small] at (0,-2) {$3$}; \node[green, font = \small] at (1,-2) {$3$}; \node[green, font = \small] at (2,-2) {$3$}; \node[green, font = \small] at (3,-2) {$3$}; \node[green, font = \small] at (-1,-3) {$3$}; \node[green, font = \small] at (2,-3) {$3$}; \node[blue, font = \small] at (-2,-3) {$4$}; \node[blue, font = \small] at (0,-3) {$4$}; \node[blue, font = \small] at (1,-3) {$4$}; \node[blue, font = \small] at (3,-3) {$4$}; \node[blue, font = \small] at (-2,-4) {$4$}; \node[blue, font = \small] at (-1,-4) {$4$}; \node[blue, font = \small] at (0,-4) {$4$}; \node[blue, font = \small] at (1,-4) {$4$}; \node[blue, font = \small] at (2,-4) {$4$}; \node[blue, font = \small] at (3,-4) {$4$}; \draw[yellow, dashed, very thick] (-3,-5) -- (-3,4) -- (4,4) -- (4,-5) -- cycle; \end{tikzpicture}");[/asy][/asy]