0
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ I would have thought $1267650600228229401496703205375$ by considering how to place the $0$s $\endgroup$
    – Henry
    Oct 8, 2021 at 8:42
  • $\begingroup$ Would you please expand your solution a bit more? How did you placed 0s ? @Henry $\endgroup$ Oct 8, 2021 at 8:52
  • $\begingroup$ 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? $\endgroup$
    – Henry
    Oct 8, 2021 at 8:55
  • 1
    $\begingroup$ The number given by Henry is $2^{100}$ $\endgroup$ Oct 8, 2021 at 9:27
  • 1
    $\begingroup$ @DanielMathias Not exactly. See, all powers of $2$ (higher than $2^0$) are even. $\endgroup$
    – CiaPan
    Oct 8, 2021 at 9:30

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.