Ponder This Challenge - December 2011 - Infinite chess game

Ponder This Challenge:

This month's challenge is by Martin Erickson (thanks).

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.

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

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?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Queens:
  One queen cannot checkmate, even if the Black king is cooperating, since it cannot threaten the king's current location and the eight surrounding squares simultaneously. Two queens can force a checkmate by first closing in on the king in. If, for example, the two queens are on a1 and c1 and the king is on, say, b9, the following moves force a checkmate:

  1. Qa7 Kb10
  2. Qc9 Kb11
  3. Qa11 mate
     So Q = 2.

  Rooks:
  Again, two rooks can not checkmate even a cooperating king; but two rooks can close the king into a single column, and a third rook can then checkmate it.
  So R = 3.

  Bishops:
  There are two kinds of bishops: light-squared and dark-squared. If there are five bishops, then in one of the colors there are no more than two bishops. The king can then stay only on that color and keep avoiding checkmate; up to a single situation: B_K_B, where the black king is either in stalemate, or can move to the other color and immediately back (and thanks for Leon Smith for this comment).
  On the other hand, six bishops can easily close on the king.
  So B = 6.

  Knights:
  Since the knights move quite slowly, even three knights can not follow the king and three knights cannot checkmate.
  So N = infinity.

  1/Q + 1/R + 1/B + 1/N = 1/2 + 1/3 + 1/6 + 1/inf = 1

  No finite number of knights can checkmate the king. However, as some of you noticed, infinitely many knights (even with density zero, if you ignore the 50-moves rule) can be arranged to ensure checkmate.
  For example put a knight in any place where either the X coordinate or the Y coordinate is a perfect square.

Solvers

• Aaron Matthews (11/29/2011 05:32 AM EDT)
• Hari MP (11/29/2011 08:23 AM EDT)
• Dan Dima (11/29/2011 07:55 PM EDT)
• Jan Fricke (11/30/2011 12:26 PM EDT)
• Christopher Marks (11/30/2011 03:32 PM EDT)
• Joseph DeVincentis (12/01/2011 12:29 PM EDT)
• Joshua Gunderson (12/01/2011 06:42 PM EDT)
• Luke Pebody (12/01/2011 07:56 AM EDT)
• Rafael Rabin (12/01/2011 11:00 AM EDT)
• Aviv Nisgav (12/01/2011 01:00 PM EDT)
• Andrew D Kidd (12/01/2011 04:23 PM EDT)
• Chuck Carroll (12/01/2011 08:40 PM EDT)
• Peter and Jenny de Rivaz (12/01/2011 10:12 PM EDT)
• Victor Chang (12/02/2011 05:08 AM EDT)
• Kevin Berk (12/02/2011 07:20 PM EDT)
• Panos Tsikogiannopoulos (12/03/2011 05:51 AM EDT)
• Reinder Verlinde (12/03/2011 12:11 PM EDT)
• Jochen Hoenicke (12/03/2011 05:28 PM EDT)
• Forest Deal (12/04/2011 01:18 AM EDT)
• Shmuel Menachem Spiegel (12/04/2011 04:09 AM EDT)
• Dmitry Litvinenko (12/04/2011 02:53 PM EDT)
• Rajendran Thirupugalsamy (12/04/2011 02:56 AM EDT)
• Gale Greenlee (12/04/2011 09:56 PM EDT)
• Joe Riel (12/04/2011 10:54 PM EDT)
• Leon Smith (12/02/2011 02:28 PM EDT)
• Robin Ryder (12/05/2011 11:07 AM EDT)
• David Greer (12/05/2011 12:14 PM EDT)
• Radu-Alexandru Todor & Andreas Razen (12/05/2011 01:47 PM EDT)
• Ariel Flat (12/05/2011 02:58 PM EDT)
• Walter Schmidt (12/02/2011 03:06 PM EDT)
• Thomas Pensyl & Samuel Thomsen (12/05/2011 07:40 PM EDT)
• Tom Sirgedas (12/05/2011 07:40 PM EDT)
• Anees Shaikh (12/06/2011 05:20 AM EDT)
• Christophe Malherbe (12/06/2011 10:40 AM EDT)
• Wu Chengyuan (12/06/2011 11:12 AM EDT)
• Adam Daire (12/06/2011 02:43 PM EDT)
• Tristan Jong (12/07/2011 01:23 AM EDT)
• Nick McGrath (12/07/2011 12:02 PM EDT)
• Amit Bhatia (12/07/2011 06:40 PM EDT)
• Yaron Gvili (12/08/2011 12:50 AM EDT)
• V.P.Gohil & P.B. Trivedi (12/08/2011 07:24 AM EDT)
• Kipp Johnson & John Brunecz (12/08/2011 08:25 PM EDT)
• Emanuele Natale (12/08/2011 09:39 PM EDT)
• Max Nepokroeff (12/08/2011 10:17 PM EDT)
• Adrian Neacsu (12/11/2011 02:45 PM EDT)
• Chris Kittlitz (12/12/2011 06:22 PM EDT)
• Adrian Kummer (12/12/2011 08:52 PM EDT)
• Thomas Rohr (12/13/2011 04:07 PM EDT)
• Karine Mandervelde (12/14/2011 10:31 AM EDT)
• Chris Lewis (12/14/2011 12:00 PM EDT)
• Deron Stewart (12/14/2011 04:51 PM EDT)
• Liubing Yu (12/15/2011 03:53 PM EDT)
• John Tromp (12/15/2011 04:25 PM EDT)
• Yash Kochar (12/16/2011 05:01 PM EDT)
• Edward Kim (12/16/2011 09:19 PM EDT)
• Subbu Devulapalli (12/18/2011 09:19 PM EDT)
• Jeff Steele (12/18/2011 11:03 PM EDT)
• M Zecevic (12/19/2011 12:41 PM EDT)
• Traian Delca (12/23/2011 10:01 AM EDT)
• Frank Marrs (12/23/2011 10:55 AM EDT)
• Maris Van Sprang (12/26/2011 07:29 AM EDT)
• Shilei Zang (12/26/2011 06:52 PM EDT)
• Sergey Grishaev & Denys Kopiychenko (12/27/2011 09:18 PM EDT)
• Mark Pervovskiy (12/27/2011 09:10 PM EDT)
• Naftali Peles (12/30/2011 03:10 AM EDT)
• Kshitij Gajjar (12/30/2011 07:37 PM EDT)
• Kevin Williamson (12/31/2011 06:51 PM EDT)