{"id":941,"date":"2023-01-03T19:48:29","date_gmt":"2023-01-04T03:48:29","guid":{"rendered":"https:\/\/puzzlezapper.com\/blog\/?p=941"},"modified":"2023-02-12T06:02:16","modified_gmt":"2023-02-12T14:02:16","slug":"rescued-by-flexible-polyominoes","status":"publish","type":"post","link":"https:\/\/puzzlezapper.com\/blog\/2023\/01\/rescued-by-flexible-polyominoes\/","title":{"rendered":"Rescued by Flexible Polyominoes"},"content":{"rendered":"\n

See the previous Flexible Polyomino <\/a>post here.<\/p>\n\n\n\n

One unfortunate lesson that you quickly learn about tiling problems involving a full set of (free) n-ominoes is that the pentominoes are the only really nice set. Monominoes through trominoes are trivial. And tetrominoes and hexominoes have checkerboard parity problems. Here’s an example. Suppose we wanted to tile a figure containing five copies of a 6\u00d77 rectangle with the hexominoes. (It might be a 30\u00d77 rectangle, or a 35\u00d76 rectangle, or something more fanciful.) <\/p>\n\n\n

\n
\"\"<\/a><\/figure><\/div>\n\n\n

These rectangles (suitably checkered) have an odd number of both black and white squares, and since an odd times an odd is odd, so do five of them. But 11 hexominoes are “even” (they will always cover an even number of both black and white squares) while 24 are odd (they cover an odd number of squares of each color.) Since an even number times an odd number must be even, there must be an even number of squares of both colors in both the even and odd hexomino subsets, and thus also in the full set. So our figure is impossible to tile.<\/p>\n\n\n\n

But flexible polyominoes come to our rescue. This figure, formed from five of the above rectangles with a little distortion, can<\/em> be tiled with hexominoes!<\/p>\n\n\n

\n
\"\"<\/a><\/figure><\/div>\n\n\n

Why does it work? Well, consider what it would mean to checker the underlying cells. There is a cycle of five cells around the center. If you color one of the cells white, then as you go around the center, the next cells would be black, then white, then black, then white again. But the following cell would be the one where we started, and it would have to be black! So you can see that whenever we have an odd cycle of cells, we can’t have a consistent 2-coloring, and the checkerboard parity argument above no longer applies.<\/p>\n\n\n\n

Note that there’s no magical property of flexible polyominoes involved here, just the presence of an odd cycle. The following figure has no odd cycle, so checkerboard parity applies, and it turns out to be untileable with the hexominoes.<\/p>\n\n\n

\n
\"\"<\/a><\/figure><\/div>\n\n\n

Checkerboard parity problems can only occur with sets of even-sized polyforms. Our next odd size is the heptominoes, but here a new problem emerges. One of the heptominoes has a hole:<\/p>\n\n\n

\n
\"\"<\/a><\/figure><\/div>\n\n\n

Thus every heptomino tiling must either incorporate a hole or omit the holey heptomino. Either solution is inelegant. Flexible polyominoes rescue us once again!<\/p>\n\n\n

\n
\"\"<\/a>
Solution by Edo Timmermans<\/figcaption><\/figure><\/div>\n\n\n

The holey heptomino is there, but the hole is not. Can you find it?<\/p>\n\n\n\n

Once you move to the octominoes and beyond, “opening” a holey polyomino can require breaking a connection between cells, so we’ll stop here. But the 9-iamonds, like the heptominoes, have a single holey piece where the hole is pinched together with disconnected “fingers”. <\/p>\n\n\n\n

Problem 54<\/strong>: Tile this figure with the flexible 9-iamonds. There are 160 9-iamonds, which brings us into the zone where we’d want a pretty efficient solver in order to make headway. <\/p>\n\n\n

\n
\"\"<\/a><\/figure><\/div>\n\n\n

This gets us through most of the 2022 Flexible Polyform Renaissance material that I wanted to post, but there is still enough for a brief coda, which I hope to complete soon.<\/p>\n","protected":false},"excerpt":{"rendered":"

See the previous Flexible Polyomino post here. One unfortunate lesson that you quickly learn about tiling problems involving a full set of (free) n-ominoes is that the pentominoes are the only really nice set. Monominoes through trominoes are trivial. And tetrominoes and hexominoes have checkerboard parity problems. Here’s an example. Suppose we wanted to tile … Continue reading Rescued by Flexible Polyominoes<\/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":[66,127,128,231,46,17],"class_list":["post-941","post","type-post","status-publish","format-standard","hentry","category-recreational-mathematics","tag-flexible-polyforms","tag-flexible-polyrhombs","tag-flexominoes","tag-heptominoes","tag-hexominoes","tag-polyiamonds"],"_links":{"self":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/941","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=941"}],"version-history":[{"count":2,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/941\/revisions"}],"predecessor-version":[{"id":967,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/941\/revisions\/967"}],"wp:attachment":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/media?parent=941"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/categories?post=941"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/tags?post=941"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}