How many $10\times 10$ tables can we made?

Question

Each cell of a $10 \times 10$ table is filled with a non-negative integer , two numbers in this table are called adjacent whenever the cells containing these two Have a common side . We are looking for a table which has these two following features:

A) difference of every two adjacent number should be $0$ or $1$ .

B) if a number is less than or equal to all adjacent numbers, In this case, it must be $0$.

How many of these tables can we made?

Using the first condition (A) I proved there should be a integer which repeat at least $10$ times in the table , but I wasn't successful to apply second condition in a way that leads me to the solution.

Any help is appreciated , thanks!

Answer 1

The arrangement is determined by the set of tiles with zeros $A$.

You get that tile $x$ must have color $d(x,A)$ where $d(x,A)$ is the minimum number of times you must move along adjacent tiles to get to a tile with a zero.

First note that the number is at most $d(x,A)$ because otherwise you can look at a minimum-length path to $A$ and at least one of the differences is larger than $1$.

Let the set of tiles with numbers smaller than $d(x,A)$ be $Y$. Take $y\in Y$ with the smallest value written on it. Clearly $y$ has a value less than or equal to its neighbours in $Y$ by definition. And it also has a value smaller than or equal to its neighbours not in $Y$, since their distance to $A$ is at most $d(y,A)-1$. It follows $y$ sassfies condition $2$, so $d(y)=0$, so $y$ is in $A$, which is a contradiction.

We conclude everything must have label $d(x,A)$.

Finally note that both conditions always work with this labelling for any non-empty $A$.

There are $2^{100}-1$ options for $A$ ( Note that there must be at least one zero as otherwise a tile with minimum label violates the second condition).