{"id":1059,"date":"2023-10-17T14:12:27","date_gmt":"2023-10-17T21:12:27","guid":{"rendered":"https:\/\/puzzlezapper.com\/blog\/?p=1059"},"modified":"2023-11-06T05:09:43","modified_gmt":"2023-11-06T13:09:43","slug":"component-colorings","status":"publish","type":"post","link":"https:\/\/puzzlezapper.com\/blog\/2023\/10\/component-colorings\/","title":{"rendered":"Component Colorings"},"content":{"rendered":"\n

Previously<\/a>, I looked at problems concerning colorings of individual cells of polyominoes. These were not map coloring problems, (i. e., problems of giving a set of shapes a limited number of colors so no two adjacent shapes share the same color.) Map coloring the cells of a square grid isn’t very interesting, beyond noting that the grid is 2-colorable, with a checker pattern being the 2-coloring.<\/p>\n\n\n\n

But suppose our polyform components are more complicated than individual cells. For example, the components could themselves be polyominoes. Now component-wise map coloring can be a source of interesting problems. <\/p>\n\n\n\n

Since 4-coloring is always possible, 3-coloring is the usual place to go to when we want a challenge. Given three colors, the di-dominoes can be component colored in 15 ways. (There are 4 di-dominoes, and because the L-tetromino is asymmetrical, there are two ways to color it for each color pair.) Here is a tiling with 3-colored components:<\/p>\n\n\n

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

Moving up to the tri-dominoes, there are 26, which can tile a 12 \u00d7 13 rectangle<\/a>. Problem #58:<\/strong> Find a 3-coloring of the dominoes in such a tiling where each tri-domino contains all three colors.<\/s> Edit: As Bryce Herdt pointed out in a comment, this is impossible, because there are tri-dominoes where all three dominoes surround a square that could not then take any of the three colors.<\/p>\n\n\n\n

Four-coloring can<\/em> be a worthwhile problem, provided that we can find a good additional restriction on color usage. With the 11 heterogeneous di-trominoes, we can restrict ourselves to two colors each for the I and L trominoes. Then we can find a component-wise 4-coloring of the set using those colors:<\/p>\n\n\n

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

Notice that this is a “non-strict” coloring, since two red L’s meet at a vertex. Problem #59:<\/strong> find a strict 4-coloring of the components of the heterogeneous di-trominoes in a 6 \u00d7 11 rectangle. <\/p>\n\n\n\n

There are undoubtedly other fruitful directions to take component coloring. Perhaps there is something to do with poly-polyiamonds, or poly-polyhexes. I would be delighted to see what you can find!<\/p>\n","protected":false},"excerpt":{"rendered":"

Previously, I looked at problems concerning colorings of individual cells of polyominoes. These were not map coloring problems, (i. e., problems of giving a set of shapes a limited number of colors so no two adjacent shapes share the same color.) Map coloring the cells of a square grid isn’t very interesting, beyond noting that … Continue reading Component Colorings<\/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":[9,249,250,252,251],"class_list":["post-1059","post","type-post","status-publish","format-standard","hentry","category-recreational-mathematics","tag-coloring","tag-component-coloring","tag-di-dominoes","tag-di-trominoes","tag-tri-dominoes"],"_links":{"self":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/1059","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=1059"}],"version-history":[{"count":9,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/1059\/revisions"}],"predecessor-version":[{"id":1080,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/posts\/1059\/revisions\/1080"}],"wp:attachment":[{"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/media?parent=1059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/categories?post=1059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/puzzlezapper.com\/blog\/wp-json\/wp\/v2\/tags?post=1059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}