IBM Research | Ponder This | December 2005 challenges
Skip to main content

Ponder This

December 2005

<<November December January>>


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 webmaster.

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

  

Challenge: 12/01/2005 @ 09:00 AM EST
Solution: 01/03/2006 @ 09:00 AM EST
List Updated: 01/03/2006 @ 09:00 AM EST

People who answered correctly:

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)


Attention: If your name is posted here and you wish it removed please send email to the webmaster.