Kvant Math Problem 1497

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m25s
Source on kvant.digital

Problem

Prove that it is impossible to place 15 queens on a 15×15 toroidal chessboard so that no two queens attack each other.

Exploration

A toroidal $15\times 15$ chessboard can be identified with the group $\mathbb Z_{15}\times\mathbb Z_{15}$, where coordinates are taken modulo $15$. A queen attacks along rows, columns, and both diagonals. Thus two queens at $(x_1,y_1)$ and $(x_2,y_2)$ attack each other if

$$x_1=x_2,\qquad y_1=y_2,\qquad x_1-y_1=x_2-y_2,\qquad x_1+y_1=x_2+y_2$$

in $\mathbb Z_{15}$.

If 15 nonattacking queens exist, then no two can lie in the same row or column. Since there are exactly $15$ rows and $15$ columns, there must be exactly one queen in each row and each column. Hence the queens are given by a permutation

$$y=f(x),\qquad x\in\mathbb Z_{15}.$$

The diagonal conditions become

$$x-f(x)$$

all distinct modulo $15$, and

$$x+f(x)$$

all distinct modulo $15$.

This means that the three maps

$$x,\qquad f(x),\qquad x-f(x)$$

are all permutations of $\mathbb Z_{15}$.

The modulus $15$ is not prime. Since $15=3\cdot5$, it is natural to reduce everything modulo $3$. If the above three maps are permutations modulo $15$, their reductions modulo $3$ are permutations of $\mathbb Z_3$ as well.

Now a permutation of $\mathbb Z_3$ has values ${0,1,2}$ in some order, so its sum is

$$0+1+2\equiv0\pmod3.$$

Suppose $g$ is the reduction of $f$ modulo $3$. Since both $g$ and $x-g(x)$ are permutations of $\mathbb Z_3$,

$$\sum g(x)\equiv0, \qquad \sum (x-g(x))\equiv0 \pmod3.$$

But

$$\sum (x-g(x)) = \sum x-\sum g(x) \equiv0-0 \equiv0.$$

This gives no contradiction yet.

The crucial point is stronger. Because $g$ is a permutation of $\mathbb Z_3$,

$$\sum g(x)^2\equiv0^2+1^2+2^2\equiv2\pmod3.$$

Likewise $x-g(x)$ is also a permutation, so

$$\sum (x-g(x))^2\equiv2\pmod3.$$

Expanding,

$$\sum (x-g(x))^2 = \sum x^2+\sum g(x)^2-2\sum xg(x).$$

Modulo $3$ this becomes

$$2\equiv2+2+\sum xg(x),$$

since $-2\equiv1\pmod3$. Hence

$$\sum xg(x)\equiv1\pmod3.$$

On the other hand, every permutation of $\mathbb Z_3$ gives

$$\sum xg(x)\equiv 0\cdot g(0)+1\cdot g(1)+2\cdot g(2) \equiv g(1)-g(2).$$

Because ${g(1),g(2)}={1,2}$ or contains $0$, the value can never be congruent to $1$ modulo $3$ for a permutation whose difference map $x-g(x)$ is also a permutation. Checking the six permutations of $\mathbb Z_3$ shows none satisfies both requirements. Thus no such reduced permutation exists, and consequently no arrangement modulo $15$ exists.

The delicate point is identifying the correct obstruction modulo $3$. Once the problem is reduced to permutations of $\mathbb Z_3$, a direct examination becomes feasible.

Problem Understanding

We must prove that on a toroidal chessboard of size $15\times15$ it is impossible to place $15$ queens so that no two attack one another.

This is a Type B problem. The task is a pure impossibility proof.

The core difficulty is that on a toroidal board the diagonals wrap around. Classical arguments for ordinary chessboards do not apply. The toroidal geometry is naturally expressed in modular arithmetic, and the problem becomes a statement about permutations of the cyclic group $\mathbb Z_{15}$.

Proof Architecture

Lemma 1. Any configuration of $15$ pairwise nonattacking queens contains exactly one queen in every row and every column.

The reason is that two queens in the same row or column attack, while there are exactly $15$ rows and $15$ columns.

Lemma 2. Such a configuration determines a permutation $f:\mathbb Z_{15}\to\mathbb Z_{15}$ for which the maps $f$, $x-f(x)$, and $x+f(x)$ are all permutations.

Rows, columns, and the two diagonal directions correspond exactly to these three distinctness conditions.

Lemma 3. Reducing modulo $3$ yields a permutation $g:\mathbb Z_3\to\mathbb Z_3$ such that both $g$ and $x-g(x)$ are permutations of $\mathbb Z_3$.

A permutation modulo $15$ remains a permutation after reduction modulo $3$.

Lemma 4. No permutation $g$ of $\mathbb Z_3$ has the property that both $g$ and $x-g(x)$ are permutations.

This is verified by examining the six permutations of $\mathbb Z_3$.

Lemma 4 is the critical step. If it is correct, the contradiction is immediate.

Solution

Assume that $15$ pairwise nonattacking queens can be placed on a toroidal $15\times15$ board.

Represent the board as

$$\mathbb Z_{15}\times\mathbb Z_{15},$$

where coordinates are taken modulo $15$.

Since queens attack along rows and columns, no two queens may share the same first coordinate or the same second coordinate. Because there are $15$ queens and $15$ rows, each row contains exactly one queen. Likewise each column contains exactly one queen.

Hence the queens have the form

$$(x,f(x)), \qquad x\in\mathbb Z_{15},$$

for some permutation $f$ of $\mathbb Z_{15}$.

On a toroidal board, two squares lie on the same descending diagonal precisely when their values of $x-y$ are equal modulo $15$, and they lie on the same ascending diagonal precisely when their values of $x+y$ are equal modulo $15$.

Since no two queens attack each other, the numbers

$$x-f(x)$$

must all be distinct modulo $15$, and the numbers

$$x+f(x)$$

must all be distinct modulo $15$.

Thus the maps

$$x-f(x) \quad\text{and}\quad x+f(x)$$

are permutations of $\mathbb Z_{15}$.

Reduce all values modulo $3$. Let

$$g:\mathbb Z_3\to\mathbb Z_3$$

be the induced map. Because $f$, $x-f(x)$, and $x+f(x)$ are permutations modulo $15$, the maps

$$g(x) \quad\text{and}\quad x-g(x)$$

are permutations of $\mathbb Z_3$.

There are only six permutations of $\mathbb Z_3$.

$$g=(0,1,2),$$

then

$$x-g(x)=(0,0,0),$$

which is not a permutation.

$$g=(0,2,1),$$

then

$$x-g(x)=(0,2,1),$$

which is a permutation.

However,

$$x+g(x)=(0,0,0),$$

so the second diagonal condition fails.

$$g=(1,0,2),$$

then

$$x-g(x)=(2,1,0),$$

a permutation, but

$$x+g(x)=(1,1,1),$$

not a permutation.

$$g=(1,2,0),$$

then

$$x-g(x)=(2,2,2),$$

not a permutation.

$$g=(2,0,1),$$

then

$$x-g(x)=(1,1,1),$$

not a permutation.

$$g=(2,1,0),$$

then

$$x-g(x)=(1,0,2),$$

a permutation, but

$$x+g(x)=(2,2,2),$$

not a permutation.

In every case at least one of the required permutation conditions fails. Thus no permutation $g$ of $\mathbb Z_3$ can arise.

This contradicts the existence of the assumed permutation $f$ on $\mathbb Z_{15}$.

Hence no configuration of $15$ pairwise nonattacking queens exists on a toroidal $15\times15$ board.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the passage from queens to permutations. A careless argument might only use the row condition. Since there are $15$ queens and $15$ rows, pairwise nonattacking queens force exactly one queen in each row. The column condition then forces exactly one queen in each column. This is what allows the representation $(x,f(x))$.

The second delicate step is the interpretation of diagonals. On a toroidal board, the square reached by moving one step down and one step right repeatedly has constant value of $x-y$ modulo $15$. Likewise the other diagonal direction has constant value of $x+y$ modulo $15$. Forgetting the modular nature of the board would produce the wrong attack relation.

The third delicate step is the reduction modulo $3$. Consider the permutation

$$g=(0,2,1).$$

Then

$$x-g(x)=(0,2,1)$$

is itself a permutation. If one checked only the condition involving $x-g(x)$, one would incorrectly believe that this permutation is admissible. The second diagonal condition gives

$$x+g(x)=(0,0,0),$$

which is not a permutation. Both diagonal families must be enforced simultaneously.

Alternative Approaches

A more conceptual proof uses a classical theorem of Pólya. For a toroidal board of size $n\times n$, a complete set of $n$ nonattacking queens exists if and only if $n$ is relatively prime to both $2$ and $3$. Since

$$15=3\cdot5,$$

the condition fails, and the desired configuration cannot exist.

Another approach works directly in the group $\mathbb Z_{15}$. From the permutation conditions one obtains a complete mapping of the cyclic group. Hall and Paige proved that cyclic groups admit such mappings precisely when their Sylow $2$-subgroup is trivial and the group has no factor of order $3$. For $\mathbb Z_{15}$ this criterion fails because of the factor $3$. The elementary modulo $3$ argument used above is preferable for a Kvant problem because it avoids any group-theoretic machinery and reduces the contradiction to a finite check of six permutations.