# Keep the chessboard differences below eight

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

• "We may assume without loss of generality that S contains..." Why can we assume this? – Lopsy Oct 9 '15 at 17:29
• @Lopsy: Just consider the number of elements in T in every row. – Gamow Oct 9 '15 at 17:46
• Wow. Never would've got this glad I gave up. But I did, at least, make a generalization: puzzling.stackexchange.com/questions/23063/… – warspyking Oct 10 '15 at 1:55
• Does this generalize to n*n squares requiring a difference of n or more? – xnor Oct 10 '15 at 3:15
• @xnor: Yes, the very same argument works (just replace 8 by n; 64 by n^2; 32 by n^2/2; etc. – Gamow Oct 10 '15 at 12:30

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.