Listen With Others

Are you sitting comfortably? Then we'll begin

4023: Pentomino Factory by Oyler

Posted by erwinch on 20 March 2009

I found this quite the most enjoyable Listener of 2009 to date and felt disappointed when it came to an end.  It also happened to be one of the most straightforward of puzzles, which just shows that difficulty is not everything. 
I first encountered pentominoes in Martin Gardner’s Mathematical Puzzles and Diversions (1959), which was a Christmas present circa 1966, but it lay forgotten on my shelves until Listener No.3685, Pentad by Tangent (Aug 2002), where we had to arrange the twelve shapes into an 8×8 square that had a 2×2 blocked centre (not a 2×3 hole as it says on the Listener site) with the cross already in place.   This puzzle totally enthralled me and it took five days to solve – I even made my own set of pentominoes.  With Gardner’s book, I went on to look at the rectangles including the most difficult to solve, the 3×20, which has just two distinct solutions ignoring rotations and reflections.  Those took me an absolute age to find but now you can see them in an instant on the Net.  You can also see in an instant that there are no less than 1010 distinct solutions for our 5×12 rectangle here so no point in looking for a shortcut there!
As the title hints, the key to this was factorisation and especially prime factorisation to start.  The 12th shape (B=11) could be placed immediately by finding those products that had eleven as a factor:
Row 1: 1497375000 = 11 × 11 × 11 × 1125000
Row 2: 14701500 = 11 × 11 × 121500
Col 1: 4356 = 11 × 11 × 36
Col 2: 12474 = 11 × 1134
Col 3: 15246 = 11 × 11 × 126
A product with zero at the end indicated multiples of five or ten but the single zero at Col 4 (3150) was too far from most of the zeros, Col 12 (36000), to be connected so must indicate multiples of five with the tens over towards Col 12:
Row 1: 1125000 = 10 × 10 × 10 × 5 × 5 × 5 × 9
Row 2: 121500 = 10 × 5 × 5 × 486
Col 4: 3150 = 5 × 5 × 126
Col 10: 640 = 10 × 64
Col 11: 8640 = 10 × 864
Col 12: 36000 = 10 × 10 × 10 × 36
The 3×3 square where the 1st shape (0) would appear was also clearly indicated so the grid now looked like this: 
Continuing in the SW corner, it was soon apparent that two, seven and nine would appear here in some order with Cols 2, 3 & 4 each containing one seven.
Col 9: 32 = 2 × 2 × 2 × 2 × 2 or 8 × 4 × 1 × 1 × 1 but it had to be the latter since the twos were accounted for elsewhere.
The remaining factorisation of Row 1: 9 = 3 × 3 × 1 and Col 12: 36 = 6 × 6
The initial completion of the grid was then far from a formality but no major problems were encountered.
The final stage was the colouring.  The four colour theorem excludes meetings at a point but the preamble told us that these had to be considered here as is also usual with maps.  The states of Utah, Colorado, New Mexico and Arizona all meet at a point but I know of nowhere on earth where five states do so although it is not inconceivable.  We have no four shapes meeting in our grid so a good starting point is to colour any one shape and then go around it alternately using two other colours.  A fourth colour is needed where a state has no coastline but an odd number of neighbours such as West Virginia with five.  However, our shapes each have a ‘coastline’ so the three colours sufficed:
Usually I have no idea how these numerical puzzles are set but the construction here is beautifully simple and I am able to extend the fun:
Here I looked at a different position for the numbers thinking that having the five-, ten- and two-shapes adjacent might make things more difficult.  In fact it turned out to be easier than Oyler’s grid.  The 7-shape could be entered immediately since we had one seven in row 2 and there is only one shape with that 1,2,1,1 arrangement.  With that as a base I was able to creep slowly to the right.
Would the puzzle have been too easy had twelve been used in place of zero?  Not really, the 11-shape could also be placed immediately but I noticed little difference in difficulty.  With the original puzzle, I had thought that placing the 1-shape could be a problem but you just had to look at the low products such as the 27 for Col 12 here.
Here I used Oyler’s numbers for the shapes except that zero and seven were swapped.  Note that we have to use four colours for the two reasons stated above: four shapes meeting at a point and the 10-shape having no ‘coastline’ with an odd number of neighbours (5), as indeed does the 3-shape. Note also that there are no solutions with the straight pentomino in any column other than 1 or 12.  This was a different sort of puzzle requiring a lot of trial and error using my home-made pentominoes but it did not prove to be too difficult.  I wonder if this is a unique solution?
Skimming through all 1010 solutions on the Net, I got the impression that those with one instance of four shapes meeting at a point occurred with the greatest frequency followed by those with none then two and finally three.  Three turned out to be very rare and the above may be the only one but I did not examine them all too closely.
Final Word
I wonder if we will get to see pentominoes again in the Listener – I certainly hope so. If considered one-sided, the six asymmetrical shapes become two so we have 18 shapes or 90 squares to play with. The five tetrominoes, seven if considered one-sided, could form a puzzle such as the 16-piece jigsaw of a chessboard we had in the sixties – we could never solve it.
Puzzles of this quality are a great recruiter to the Listener cause so many thanks to Oyler and I look forward to his next.
Footnote (added Dec 09)
Here are the two 3×20 solutions:
For me it is rather sad to find these readily available on the Net since I can’t see anyone ever again making their own set of pentominoes to then spend hours searching for the two solutions.
When it came to finding them, I knew that they couldn’t be split into two smaller rectangles so that any straight edge of three squares (1-, 3-, 8- & 12-shapes) would only appear in columns 1 or 20 and therefore the 12-shape must appear at one end. As for the other end, apart from the remaining straight edges, there were some very seductive couplings such as the 1- and 10-shapes – I wasted so much time on these.
Note that the six asymmetric shapes (3, 5, 6, 7, 10 & 11) all show opposite sides for each solution so that it would be possible to make a double-sided jigsaw of the twelve shapes with a different arrangement for each side.  We could have long, thin things such as a train on one side and snake on the other.  I would have just loved to have had such a toy as a child.

3 Responses to “4023: Pentomino Factory by Oyler”

  1. Robert Zara said

    Thanks for the helpful and explanatory blog. This was my first attempt in about 30 years (or whenever The Listener was itself still published) to have a go at a Listener crossword, and I was mildly surprised to find a puzzle with no words at all! I had hoped that one of the patterns in Martin Gardner’s book would be used, but it was not to be. In the end I gave up, but I now see that persistence would have got me there in the end. I am lost in admiration for those solvers who claim to have solved it in 10 minutes (see the discussion on the Crossword Centre message board).

    Perhaps I’ll give it another go in a few years’ time…

  2. […] […]

  3. […] were on the easy side as these things go but this was none the worse for that – shades of Pentomino Factory perhaps.  My only regret is that it is another thirteen weeks or so until our next numbersfest. […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: