CUNY Math Challenge Blog

Solutions, Resources, Further Information & Discussion

Posts Tagged ‘polyomino

Round 4: Problem 5 Solution

with 2 comments

Tricoloring

Tricoloring

This is a nice tiling problem in disguise. Let’s ignore the letters and symbols for now and just work with a blank 5×8 board. The 3×1 rectangular pieces are like straight triominoes that we will use to try to tile the board.

Essentially, our problem now is the following: with 13 triomino(e)s, how many different places can we place a monomino on a 5×8 board.

Tricolor the board as shown. Note that we now have 13 red squares, 13 yellow squares, but 14 black squares. Therefore, the monomino must be placed on one of the black squares. However, the monomino cannot be placed on just any black square. A monomino can only be placed on a black square if there is no way to flip our coloring so that the square in our original coloring is no longer black. Flipping the coloring disqualifies every black square besides those 2 on the third row.

We can verify that in fact we may place a monomino on either of these two squares by showing a tiling (try it, it’s trivial). Therefore we conclude that a monomino can only appear on one of these 2 squares. Plugging in these 2 black squares into the original board / cake, we see that on these two squares are the ‘2’ and the ‘9’ of ‘2009.’ These are the only two possible remaining pieces.

Advertisements

Written by Administrator

April 27, 2009 at 00:05

Round 1: Problem 1 Solution

with one comment

There has developed a set of terminology to describe these objects. These tiling objects have been named polyomino(e)s (as generalized forms of dominoes), or in this specific case, pentomino(e)s. This specific arrangement is usually referred to as the F-pentomino, for its resemblance to the letter F (all of the pentominos are named after the letters they look like, though I’d agree that this one is a bit of a stretch).

With that in mind, there are a number of useful sites with information on pentominos and plane tilings. I won’t list all of them because they are relatively easy to find, but dmoz.org links to a whole directory’s worth of sites dedicated to polyominos. It can be found here. Of particular interest is Gerard’s Polyomino Solution Page, with more than 60 polyomino puzzles and solutions.

For our purposes, however, this problem should not pose too much difficulty beyond simply trying out various rotations of the tiles. There’s a simple solution with fewer pieces; an example can be found at the NGfL here (warning: PDF) along with solutions for all of the other pentominos. I’ll link to a nice larger solution as well because, well, I like the colors.

One point of confusion for this problem is that tilings of the plane (or tessellations as they may be called) do not need to be regular (rectangular). In fact there are only three polygons that form regular tessellations. See the page at MathWorld for further info. Rather, the critical point here is that the shape formed can be attached to itself at any end (including top and bottom), meaning that we could continuously attach replications of the shape to itself to tile an infinitely large area.

Please post any comments, corrections, interesting points, or alternate solutions that you may have found in the comments!

Written by Administrator

March 16, 2009 at 00:00