1
$\begingroup$

Given an $n$ x $n$ board, assume that $n \geq 5$ and that $n$ is not divisible by $2$ or $3$. Prove that the following positioning of $n$ queens $Q_0, Q_2, ..., Q_{n-1}$ works, i.e no two queens threaten each other:

For $0 \leq i \leq n-1$ we position the queen $Q_i$ on the field $(i, 2i \text{ } \pmod n)$.

Here we're using the ($x$-coordinate, $y$-coordinate) coordinate system, where $x$ describes the horizontal position, and $y$ the vertical. For example, in the formula above, $x$ would be $i$, and $y$ would be $2i \pmod n$.

My idea was to prove by contradiction and break up each case on how the queens are positioned to not threaten each other (horizontally, vertically and diagonally), but I can't see what follows. Can someone offer their thoughts or point me in the right direction?

$\endgroup$
1
  • $\begingroup$ The condition n ≥ 5 is not needed. n = 2, 3, 4 are divisible by 2 or 3, and for n = 1 the algorithm works. $\endgroup$ – gnasher729 Jun 9 '20 at 22:11
2
$\begingroup$

Vertically: if $Q_i$ and $Q_j$ have the same $x$-coordinate, $i = j$ so they're the same queen.

Horizontally: if $Q_i$ and $Q_j$ have the same $y$-coordinate, $2i = 2j \pmod n$, so $2i = 2j + kn$ for some $k \in \mathbb{Z}$; since $n$ isn't divisible by 2, $k$ must be, and we have $i = j + (2k')n$, so $i = j \pmod n$. Since both $i$ and $j$ are $\le n$, they're equal.

Diagonally: we have two cases: the diagonals parallel to $(0, 0) \to (1, 1)$ and the 'antidiagonals'. First case: if $i - 2i = j - 2j \pmod n$, $-i = -j \pmod n$, so $i = j \pmod n$. Second case: if $i + 2i = j + 2j \pmod n$, so $3i = 3j + kn$ for some $k \in \mathbb{Z}$; since $n$ isn't divisible by 3, $k$ must be, and we have $i = j + (3k')n$, so $i = j \pmod n$.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer! What does $k'$ stand for in your notation? $\endgroup$ – Karla Jun 9 '20 at 19:43
  • $\begingroup$ Just another natural number ($k$ divided by 2 or 3). $\endgroup$ – Glorfindel Jun 9 '20 at 19:44
2
$\begingroup$

Consider $i < j$ between 0 and $ n-1$. Of course, the first coordinate can’t be same for any two queens, hence they aren’t in same row.

Now, suppose, for the sake of contradiction, they lie on the same column. Then, $2(i-j) = nk$ for some natural $k$. Now, as n doesn’t contain 2 as it’s divisor, $k$ must be even. So, either $k$ is 0, which is not possible because that will contradict our assumption that $i$ and $j$ are not equal, or $k\geq 2$. In the latter case, $LHS = 2(i-j) < 2(n-1) < 2n \leq nk$, and hence $LHS \ne RHS$. Hence, we conclude that our assumption must have been incorrect and two queens positioned in this manner can’t lie on same column.

You still need to figure out the diagonal case.

$\endgroup$
2
$\begingroup$

For the diagonal case, split to two proofs - one for each "rotation" of the diagonal line.

When the diagonal line is "from top left to bottom right", then assume for the sake of contradiction we have two queens $i,j$. Then in order for them to be on the same diagonal line, there must be some $k$ where $i+k=j$ and $2i \pmod n + k =2j \pmod n$. Thus both $k=j-i$ and $k=2(j-i) \pmod n$.

Therefore, there must be some whole number $d$ with $k=2(j-i)+dn$. Substitute $k=j-i$ and get $i-j=dn$ and therefore $i-j = 0 \pmod n$. but both $0\le i,j\le n-1$ so we must have $i=j$ and therefore we have a contradiction.

The other "rotation" of the diagonal line uses the same idea.

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