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

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!

• I would have thought $1267650600228229401496703205375$ by considering how to place the $0$s Oct 8, 2021 at 8:42
• Would you please expand your solution a bit more? How did you placed 0s ? @Henry Oct 8, 2021 at 8:52
• Hint: How many $0$s can you have? How many $0$s must you have? How many ways of placing them? What constraints does this put on the other values? Oct 8, 2021 at 8:55
• The number given by Henry is $2^{100}$ Oct 8, 2021 at 9:27
• @DanielMathias Not exactly. See, all powers of $2$ (higher than $2^0$) are even. Oct 8, 2021 at 9:30

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).