Ponder This Challenge - December 2005 - Barring polyominoes from infinite board

Ponder This Challenge:

Puzzle for December 2005.

This month's puzzle is about barring polyominoes from an infinite checkerboard by blocking some of the squares of the checkerboard.  For a fixed polyomino, P, we want to prevent P from being placed on the checkerboard by blocking as small a fraction of the squares of the checkerboard as possible.  Let f(P) be this minimal fraction.  We always assume P is placed so that the squares of P coincide with the squares of the checkerboard.  However P can be reflected or rotated.  For example let
        P = OO
             O
Then f(P)=1/2.  For there are numerous ways of barring P from the infinite checkerboard by blocking half the squares (consider blocking all the squares of one color or every other row or every other column etc).  But on the other hand barring P from a 2x2 square requires blocking 2 squares.  So f(P) must equal 1/2.  Now let
        P = OOO
              O
              O
(the V pentomino).  This month's puzzle is to find f(P).  We do not ask for a proof just for the value and an example of a blocking configuration of that density.

The first 100 people who answer correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

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

  Answer:

  If P is the V pentomino f(P)=4/13.  This can be achieved as follows.  Consider the integer lattice, L, generated by (2,3) and (5,1).  This has density 1/13. The blocking configuration consists of L shifted by (0,1),(0,-1), (1,0) and (-1,0).  This has density 4/13 and it is easy to see it bars P (the V pentomino) from the infinite checkerboard.  See below where we illustrate a 13x13 block where X's denote blocked squares and .'s denote unblocked squares.  This block has density 4/13 and can be used to tile the infinite checkerboard.

          ..X..X...X.X.
          X...X.X...X..
          .X...X..X...X
          X..X...X.X...
          ..X.X...X..X.
          ...X..X...X.X
          .X...X.X...X.
          X.X...X..X...
          .X..X...X.X..
          ...X.X...X..X
          X...X..X...X.
          ..X...X.X...X
          .X.X...X..X..

  This problem was first considered by Golomb ("Polyominoes", Scribner's, New York, 1965, pp 42-45).  Golomb found blocking configurations of density 1/3 which he believed to be minimal.  The above less dense blocking configuration was found by Klamkin and Liu ("Polyominoes on the Infinite Checkerboard", J. Combinatorial Theory Series A, 28(1980), p. 7-16).  A proof of optimality can be found in "Barring Rectangles from the Plane" (Barnes and Shearer, Journal of Combinatorial Theory Series A, 33(1982), p. 9-29).

  ---

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

Solvers

• John Hart (12.01.2005 @10:27:11 AM EDT)
• Eugene Vasilchenko (12.01.2005 @04:27:05 PM EDT)
• Jason Howald (12.03.2005 @09:37:35 PM EDT)
• Kerry M Soileau (12.05.2005 @10:46:21 AM EDT)
• Justin T Miller (12.05.2005 @08:08:53 PM EDT)
• Evgeny (12.06.2005 @01:40:42 AM EDT)
• Vernon W Miller (12.06.2005 @02:05:22 PM EDT)
• Kevin Fan (12.07.2005 @04:11:24 PM EDT)
• Victor Chang (12.08.2005 @03:35:48 AM EDT)
• Daniel Bitin (12.12.2005 @01:58:31 PM EDT)
• Joseph DeVincentis (12.13.2005 @10:49:35 AM EDT)
• Piotr Zielinski (12.13.2005 @09:32:24 PM EDT)
• Menal Guzelsoy (12.14.2005 @12:47:51 PM EDT)
• Huicheng Guo (12.14.2005 @06:57:22 PM EDT)
• Gundars Kokts (12.15.2005 @12:38:56 AM EDT)
• Phil Muhm (12.15.2005 @05:59:41 PM EDT)
• Bertram Felgenhauer (12.16.2005 @06:52:48 PM EDT)
• Dan Dima (12.20.2005 @08:02:40 AM EDT)
• Chuck Carroll (12.21.2005 @12:23:58 PM EDT)
• John G. Fletcher (12.21.2005 @08:28:05 PM EDT)