{"id":230,"date":"2013-05-23T16:51:35","date_gmt":"2013-05-23T23:51:35","guid":{"rendered":"http:\/\/puzzlezapper.com\/blog\/?p=230"},"modified":"2013-05-23T16:51:35","modified_gmt":"2013-05-23T23:51:35","slug":"a-polyformists-toolkit-practical-topology","status":"publish","type":"post","link":"https:\/\/puzzlezapper.com\/blog\/2013\/05\/a-polyformists-toolkit-practical-topology\/","title":{"rendered":"A Polyformist’s Toolkit: Practical Topology"},"content":{"rendered":"

In polyomino puzzles, we would frequently like to tile the simplest shape possible, and a rectangle usually seems to fit the bill. But sometimes a rectangle isn’t possible. For example, we can never make a 4\u00d75 rectangle with the five tetrominoes. One way to prove this is with a checkerboard parity argument. Four of the 5 tetrominoes must always occupy even numbers of both black and white squares if they are placed on a checkerboard. The T tetromino must occupy odd numbers of each color. Therefore a rectangle must have odd numbers of each color, but any rectangle of size 20 will have colors evenly divided, 10 and 10. A similar argument can be made to show that the 35 hexominoes cannot tile a rectangle.<\/p>\n

\"The
This will never work…<\/i><\/figcaption><\/figure>\n

Rather than give up and accept that we’ll need to find a less elegant shape to tile, we have another option. If we wrap the edges of a 5\u00d74 rectangle around to form a cylinder, (so that the cylinder is 4 squares tall and 5 squares in circumference) tiling is once again possible. To see why this might be so, imagine that you are coloring the squares as in a checkerboard. Once you got back around to where you began, you would find that in order to continue the pattern, you would need to use the opposite colors from those you already used. Note that this would not work if you wrapped the rectangle in the other direction; because the other side has even length, the checkering colors remain consistent.<\/p>\n

\"The
…until we wrap the rectangle into a cylinder.<\/i><\/figcaption><\/figure>\n

There is a video<\/a> by Edo Timmermans showing how a tetromino cylinder can be made with toy magnets. He claims that there are seven distinct tilings of a cylinder with the tetrominoes, and poses an interesting puzzle involving them. A commercially produced cylindrical polyomino puzzle is Logiq Tower<\/a>, designed by Marko Pavlovi\u0107, which uses wooden pentomino-based pieces that form a cylinder together with some other pieces. Because these pieces are inflexible, they lack some of the allowable symmetry actions of free pentominoes.<\/p>\n

A cylinder isn’t our only option. We could give the rectangle a half-twist before connecting the ends; this gives us a M\u00f6bius strip. We could also connect both pairs of sides instead of one; this gives a structure that is topologically equivalent to a torus or doughnut. And then we could add twists to that\u2014 well, at this point it would be nice to be systematic so we can be sure that we’ve found all of the possibilities. One thing to note is that adding more twists doesn’t actually give us more possibilities. A strip with two twists will have exactly the same tilings as a strip with no twists, and in general, a strip with an even number of half-twists will have the same tilings as the no-twist strip, and a strip with an odd number of half-twists will have the same tilings as the M\u00f6bius strip. So for each dimension, we have three options: no connection, connection without a twist, and connection with a half-twist. This gives us the following matrix of possibilities:
\n\"Topologies
\nOnly six possibilities here, not nine, because the ones in the lower left are equivalent to the ones across the main diagonal from them. Note that the M\u00f6bius strip, Klein bottle, and projective plane are nonorientable surfaces, which means that they effectively have only one side.<\/p>\n

An important consideration when working with these is that one-sided polyominoes don’t exist on nonorientable surfaces. With one-sided polyominoes, translation is allowed, but reflection isn’t. However, on a non-orientable surface, translating far enough leaves an object in a reflected state.<\/p>\n

Another consideration is that coloring is harder when we leave the plane behind. On the plane, we have a theorem stating that we never need to use more than four colors to make all of the tiles differ in color from all of their neighbors. On a torus, this may require seven colors. In 2001, Roger Phillips found 18 heptominoes that could tile a 7×7 torus, and sent these tilings<\/a> to MathPuzzle.com. Here’s one: <\/p>\n

\"7-colored<\/p>\n

Depending on the dimensions of the torus, it may be possible for a polyomino to wrap around and touch itself. In a strict sense, this makes any coloring impossible, since we don’t let tiles of the same color touch. However, we can follow a looser standard, and allow self-touching polyominoes in our colored tilings. Patrick Hamlyn found a 3-coloring of a tiling of the 35 hexominoes in 7 3\u00d710 tori using this scheme in 2003:<\/p>\n

\"The<\/p>\n

This problem has no solutions if the tori are replaced with rectangles or cylinders.<\/p>\n

Problems #31-37<\/strong>:
\nThough it seems like a pretty basic problem, if anyone has counted the number of pentomino tilings of cylinders, I am not aware of it. Wrapping the short sides of the 3\u00d720 together should not give any solutions beyond the two obtained by wrapping the solutions on the 3\u00d720 rectangle. That leaves the 3\u00d720 wrapped the other way, and both ways of wrapping the 4\u00d715, the 5\u00d712, and the 6\u00d710 rectangles. <\/p>\n

Problems #38-40<\/strong>: Find the solution counts for the 4\u00d715, 5\u00d712, and 6\u00d710 tori. I don’t know if these are all computationally tractable, but I can hope. (The 3\u00d720 will be the same as the 3\u00d720 cylinder with long sides wrapped together.)<\/p>\n

Even more possibilities for tiling become available when you choose parallelograms with diagonal sides to wrap around, but this post is long enough, so that will have to be a matter for another post.<\/p>\n","protected":false},"excerpt":{"rendered":"

In polyomino puzzles, we would frequently like to tile the simplest shape possible, and a rectangle usually seems to fit the bill. But sometimes a rectangle isn’t possible. For example, we can never make a 4\u00d75 rectangle with the five tetrominoes. One way to prove this is with a checkerboard parity argument. Four of the … Continue reading A Polyformist’s Toolkit: Practical Topology<\/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":[84,107,46,109,10,11,33,106,108],"class_list":["post-230","post","type-post","status-publish","format-standard","hentry","category-recreational-mathematics","tag-a-polyformists-toolkit","tag-cylinder","tag-hexominoes","tag-nonorientable-surfaces","tag-pentominoes","tag-polyominoes","tag-tetrominoes","tag-topology","tag-torus"],"_links":{"self":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/230","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=230"}],"version-history":[{"count":13,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/230\/revisions"}],"predecessor-version":[{"id":396,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/230\/revisions\/396"}],"wp:attachment":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/media?parent=230"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/categories?post=230"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/tags?post=230"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}