{"id":30,"date":"2010-03-17T16:39:06","date_gmt":"2010-03-17T21:39:06","guid":{"rendered":"http:\/\/puzzlezapper.com\/blog\/2010\/03\/pentomino-cover-cycles\/"},"modified":"2013-05-15T16:43:15","modified_gmt":"2013-05-15T23:43:15","slug":"pentomino-cover-cycles","status":"publish","type":"post","link":"https:\/\/puzzlezapper.com\/blog\/2010\/03\/pentomino-cover-cycles\/","title":{"rendered":"Pentomino Cover Cycles"},"content":{"rendered":"

What’s the smallest shape into which any of the 12 pentominoes can be placed? I call this old chestnut the “minimal pentomino cover<\/a>” problem, and I’ve spent a lot of time working on a number of variations on it. For the purpose of introducing and illustrating the basic problem to my dear readers, I wanted to use an animated GIF file showing all of the pentominoes in turn being placed on a minimal cover. <\/p>\n

An aesthetically pleasing way to cycle through the pentominoes would be to move one square at a time. This is in fact possible:<\/p>\n

<\/p>\n

A couple of variations on the problem of finding such a cycle suggest themselves:<\/p>\n

#9<\/b>: Minimize the total distance the squares move per cycle. The taxicab metric<\/a> seems to be more sensible and simpler than Euclidean distances here. I made no attempt to do any minimization in the above solution, so I’m sure there is room for improvement. <\/p>\n

#10<\/b>: If you gave every square in the pentominoes a distinct color, and kept the color the same when a square moved, you could keep track of where the squares end up at the end of a cycle. During the cycle illustrated above, two pairs of squares switch places. Is there a cycle of single-square moves through the pentominoes that ends with each square in the same place it began?<\/p>\n

Notice that the central square can never move, because the only pentomino placement without the central square is one of the P pentomino, for which the only valid square movements turn it into a U pentomino. It would need movements to two different pentominoes to be part of a cycle.<\/p>\n

For both of the above problems, the other 9 square pentomino cover would also be a valid substrate:<\/p>\n

<\/p>\n

Since this one has no immobile squares, another problem using it may be solvable:<\/p>\n

#11<\/b>: Find a cycle where the permutation of the squares from one cycle to the next is cyclic<\/a> (in the second sense in the linked article.) That is, successive iterations of the cycle will eventually take each square in a pentomino to all of the other positions in that pentomino.<\/p>\n

\n

Some very good news: I’ve been invited to the 9th Gathering for Gardner<\/a> conference in Atlanta later this month. The Gathering for Gardner is an invitation-only conference  held in honor of Martin Gardner, who brought recreational mathematics to a generation through his columns in Scientific American. That generation was not my generation, but it was impossible to miss his imprint on later writers, and I’ve picked up used copies of several of the collections of his columns. A large proportion of the names on the spines on my recreational mathematics bookshelf are represented among the invitees, so this will be really special for me.<\/p>\n","protected":false},"excerpt":{"rendered":"

What’s the smallest shape into which any of the 12 pentominoes can be placed? I call this old chestnut the “minimal pentomino cover” problem, and I’ve spent a lot of time working on a number of variations on it. For the purpose of introducing and illustrating the basic problem to my dear readers, I wanted … Continue reading Pentomino Cover Cycles<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[23,10,39,22,11],"class_list":["post-30","post","type-post","status-publish","format-standard","hentry","category-recreational-mathematics","tag-cover-cycles","tag-pentominoes","tag-polyform-change-paths","tag-polyform-covers","tag-polyominoes"],"_links":{"self":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/30","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/comments?post=30"}],"version-history":[{"count":4,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/30\/revisions"}],"predecessor-version":[{"id":227,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/30\/revisions\/227"}],"wp:attachment":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/media?parent=30"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/categories?post=30"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/tags?post=30"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}