Two players (White and Black) are playing on an infinite chess board (extending infinitely in all directions).

First, White places a certain number of queens (and no other pieces) on the board.

Second, Black places a king on any unoccupied, unattacked square of the board.

Then, both players take turns moving until Black is checkmated.

What is the minimum number of queens White needs to force a checkmate?

Answer the same problem if White starts with rooks instead of queens.

Do the same for bishops and knights.

Let $Q, R, B$, and $N$ be the minimum number of queens, rooks, bishops, and knights, respectively. What is the sum $1/Q + 1/R + 1/B + 1/N$?

  • 26
    $\begingroup$ I think you should state in the question that this is the IBM December 2011 'Ponder This' problem. You should also reconsider the 'very intresting' tag in the title, since interestingness is rather subjective. Finally, I don't think that any of the tags 'logic', 'probability-theory' or 'probability-distributions' are appropriate for this question. $\endgroup$ – Chris Taylor Dec 20 '11 at 11:32
  • 8
    $\begingroup$ I posted an answer (edited with correction by Sp3000), but decided to delete it in light of the contest. What a fun problem! $\endgroup$ – JDH Dec 20 '11 at 14:06
  • 2
    $\begingroup$ Is it really appropiate to post this kind of question (contests/challenges) here? $\endgroup$ – leonbloy Dec 23 '11 at 4:24
  • 1
    $\begingroup$ A link about paper co-authored by JDH that is out today in arXiv titled mate-in-n of infinite chess is decidiable may illuminate? $\endgroup$ – Sniper Clown May 18 '12 at 0:41
  • 2
    $\begingroup$ Mahmud: The paper is about a general decision problem, you could (almost) use it to solve automatically this problem. The solution is now available at domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/… $\endgroup$ – sdcvvc May 18 '12 at 0:46

Queens. Two queens suffice, as pointed out in the comments of Sp3000.

Rooks. Three rooks suffice, by trapping the black king between two walls, and then using the third rook to slowly close the gap between the walls. If the black king approach a rook, simply move it on the same file but further away. Two rooks do not suffice, since there is no check-mate position with two white rooks and a black king.

Bishops. Six bishops suffice, with three of each color. White can use a pair of bishops to form a wall, and thus with two pairs white can trap the black king between two walls, which gradually close and deliver checkmate with the fifth or sixth (whichever color is needed). If the black king approaches a bishop, simply move it away on the same diagonal. Five bishops do not suffice, since the black king can simply stay on the color having at most two bishops of that color, and there will always be a square available, since double check will not arise.

Knights. No finite number of white knights will suffice in this game. To see this, observe first that two white knights do not suffice, since one cannot set up a check-mated position. Now, suppose white places finitely many knights on the board. Black need only place his king on a file completely to the right of those pieces. Black's strategy is simply to move steadily to the right (that is, his every move should involve a rightward horizontal movement). Since knights move at most two units to the right, white will not be able to keep more than two knights in the vicinity of the black king, and indeed, will not be able to bring two knights so close. With one knight, to be sure, white can move at double speed and catch up to the black king; but to bring two knights close to the king, each would have had to move at a greater than one unit to the right speed, which is not possible. Finally, notice that with infinitely many knights, we can fill up the board almost completely, leaving only a few empty spots, and easily set a trap for black this way.

Conclusion. So we have $Q=2$, $R=3$, $B=6$ and $N=\infty$, giving $$\frac{1}{Q}+\frac1R+\frac1B+\frac1N=\frac12+\frac13+\frac16+\frac1{\infty}=1.$$

  • $\begingroup$ I deleted my comments earlier but two queens suffice: i42.tinypic.com/2i8ztrq.jpg :) $\endgroup$ – Sp3000 Dec 20 '11 at 13:57
  • $\begingroup$ I cast the third vote to undelete this post since the contest's results are published (linked in the comments to the question), so there seems to be no harm in making this answer available to everyone. $\endgroup$ – t.b. Feb 9 '13 at 12:25

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.