4. Determine the largest integer $k$ with the following property: no matter how the numbers $1,2, \ldots, 64$ are written in the cells of an $8 \times 8$ board, there exist two adjacent cells such that the difference between the numbers written in these cells is not less than $k$. (Two cells are adjacent if they share at least one common vertex.)
Solution. In the table shown in the right diagram, the numbers $1,2,3, \ldots, 64$ are written in the cells such that the difference between any two adjacent numbers is not greater than 9. This means that $k \leq 9$.

We will prove that $k=9$. No matter how the numbers are written in the cells of the table from the cell with the number 1 to the cell with the number 64, it can be reached in at most 7 steps, where in each step a move is made to an adjacent cell. From $\frac{64-1}{7}=9$, it follows that there exist two adjacent cells such that the difference between the numbers written in them is not less than 9. Therefore, $k>8$, so $k=9$.

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
| 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 |
| 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |