7
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

Answer:

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

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

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.

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