Problem 1466

### Part (a)
We need to prove that the numbers $1$ through $16$ can be arranged on a $4 \times 4$ board such that any two numbers in cells that share a side differ by at most $4$.

Consider the following arrangement:

$$\begin{array}{|c|c|c|c|} \hline 16 & 15 & 11 & 7 \\ \hline 14 & 12 & 8 & 4 \\ \hline 13 & 9 & 5 & 3 \\ \hline 10 & 6 & 2 & 1 \\ \hline \end{array}$$

We will check the differences between adjacent cells:

- For the first row: $|16 - 15| = 1$, $|15 - 11| = 4$, $|11 - 7| = 4$
- For the second row: $|14 - 12| = 2$, $|12 - 8| = 4$, $|8 - 4| = 4$
- For the third row: $|13 - 9| = 4$, $|9 - 5| = 4$, $|5 - 3| = 2$
- For the fourth row: $|10 - 6| = 4$, $|6 - 2| = 4$, $|2 - 1| = 1$

For the columns:
- For the first column: $|16 - 14| = 2$, $|14 - 13| = 1$, $|13 - 10| = 3$
- For the second column: $|15 - 12| = 3$, $|12 - 9| = 3$, $|9 - 6| = 3$
- For the third column: $|11 - 8| = 3$, $|8 - 5| = 3$, $|5 - 2| = 3$
- For the fourth column: $|7 - 4| = 3$, $|4 - 3| = 1$, $|3 - 1| = 2$

All differences are $\leq 4$, so the arrangement satisfies the condition.

### Part (b)
We need to prove that it is impossible to arrange the numbers $1$ through $16$ on a $4 \times 4$ board such that any two numbers in cells that share a side differ by at most $3$.

First, note that the difference between the largest number (16) and the smallest number (1) is $15$. If any two adjacent cells differ by at most $3$, then the minimum number of steps required to go from $1$ to $16$ is $\lceil \frac{15}{3} \rceil = 5$ steps. This means that $16$ and $1$ must be at least 5 cells apart.

Consider the following board with $16$ in the top-left corner and $1$ in the bottom-right corner:

$$\begin{array}{|c|c|c|c|} \hline 16 & a & b & c \\ \hline d & e & f & g \\ \hline h & i & j & k \\ \hline l & m & n & 1 \\ \hline \end{array}$$

For $16$ and $1$ to be 5 cells apart, we need to ensure that the differences between adjacent cells are at most $3$. Let's analyze the path from $16$ to $1$:

1. $16 - a \leq 3$
2. $a - b \leq 3$
3. $b - c \leq 3$
4. $c - g \leq 3$
5. $g - 1 \leq 3$

Adding these inequalities, we get:

$$16 - 1 \leq 3 + 3 + 3 + 3 + 3 = 15$$

This is true, but it implies that $a, b, c, g$ must be specific values to satisfy the constraints. Let's consider the values:

- $a = 13$
- $b = 10$
- $c = 7$
- $g = 4$

Now, consider the other cells. For example, $d$ must satisfy $16 - d \leq 3$ and $d - h \leq 3$. This implies $d = 13$ and $h = 10$, but $10$ is already used for $b$. This leads to a contradiction because all numbers must be unique.

Therefore, it is impossible to arrange the numbers $1$ through $16$ on a $4 \times 4$ board such that any two numbers in cells that share a side differ by at most $3$.

$\blacksquare$