Can one place the numbers $1-64$ in the squares of a chessboard so that every two squares that share an edge have a difference of at most seven?
No, this is not possible.
Argument: Suppose for the sake of contradiction that such a placement would exist. We number the rows $1$ to $8$, and we number the columns $1$ to $8$.
- Denote by $S$ the set of squares that contain the small numbers $1,\ldots,32$.
- For $1\le i\le8$, let $r_i$ denote the number of squares in $S$ that belong to the $i$th row.
- A row $i$ with $r_i=0$ is called empty, and a row with $r_i=8$ is called full.
- For $1\le i\le8$, let $c_i$ denote the number of squares in $S$ that belong to the $i$th column.
- Denote by $T$ the set of squares in $S$, that have at least one neighbor outside $S$.
Our goal is to show that $T$ contains at least eight elements: then the smallest number of a square in $T$ is at most $25$, and its neighbor outside $S$ has number at least $33$. Done.
We may assume without loss of generality that $S$ contains the first $r_i$ squares from every row $i$ and the first $j$ squares from every column $j$.
Case 1: There are no full and no empty rows.
Then every row contains at least one square from $T$, and $|T|\ge8$.
Case 2: There exists some full row, and there exists some empty row.
Rotate the chessboard by 90 degrees, and you are in Case 1.
Case 3: There exists some empty row, but there are no full rows.
Then $r_1\le7$ and $r_8=0$. Then there exists a square $(i,j)\in S$ with $i+j\ge9$; otherwise $S$ could not have $32$ elements. Then the squares $(k,c_k)$ with $1\le k\le i$ and the squares $(a_m,m)$ with $1\le m\le j$ all are in $T$. These are at least $i+j-1\ge 8$ distinct squares (as the square $(i,j)$ itself may be counted twice).
Case 4: There exists some full row, but there are no empty rows.
Use a symmetric argument that is centered around the large numbers $33,\ldots,64$.
Thought I would post this proof since it reduces the case analysis, though it is the same basic idea as Gamow's solution.
Given a partially filled out chessboard, say a row or column is started if there is at least one number in that row or column. Let $S$ be the set of squares containing the numbers $1$ through $k$. Here $k$ is the smallest number so that all the rows are started or all the columns are started.
Let $T$ be all the squares of $S$ that are adjacent to squares outside of $S$. Like in Gamow's solution, we just need $|T| \geq 8$, since there would then be no way to fill in the square adjacent to the smallest numbered square of $T$.
Without loss of generality, assume $k$ starts the final row to be started. No row can be completely full, since the row with $k$ contains only $k$, and if any other row were full every column would have been started, meaning we should have chosen a smaller value for $k$. Since every row is started but no row is full, there must be a element of $T$ in every row.