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?
Answer
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$.
No comments:
Post a Comment