Tag: coloring

Component Colorings II: Diamonds and Triamonds

~ munizao ~ 2 Comments

Here’s a nice coincidence: the numbers of tri-diamonds and di-triamonds are both 9, which is the right amount to tile a regular hexagon of side length 3. And both sets can! Behold the di-triamonds:

3-coloring the triamonds here isn’t hard. The tiling seems to want to have a bunch of points where four triamonds meet, which disrupts chains of forced colors. The challenge is adding more challenges on top of 3-coloring. I suspect that there is no strict 3-coloring of the triamonds. One possibility is a sort of meta-coloring of the di-triamonds where no two di-triamonds with the same color pair may be adjacent. The above diagram doesn’t qualify because there are blue-red di-triamonds touching each other. Problem #60: Find such a meta-coloring.

The diamonds in the tri-diamonds are even easier to 3-color. Enough so that 3-coloring them so each tri-diamond has all three colors (the equivalent of the poorly thought out problem #58 with the tri-dominoes) was no challenge at all. Perhaps there is something to be done with symmetry. Notice that, ignoring color and the tri-diamond outlines, the diamonds in the figure below have an an axis of reflection symmetry. I wonder if, for some tiling, some form of symmetry on the diamonds is possible where colors are included.

The meta-coloring idea above suggests a way to salvage Problem #58. Instead of a three coloring of the dominoes in a tri-domino tiling, we could look for a 4-coloring of the dominoes where every tri-domino contains 3 of the 4 colors, and there is simultaneously a meta-4-coloring of the tri-dominoes where no two adjacent tri-dominoes are missing the same color.

Component Colorings

~ munizao ~ 1 Comment

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 the grid is 2-colorable, with a checker pattern being the 2-coloring.

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.

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:

Moving up to the tri-dominoes, there are 26, which can tile a 12 × 13 rectangle. Problem #58: Find a 3-coloring of the dominoes in such a tiling where each tri-domino contains all three colors. 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.

Four-coloring can 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:

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

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!

Can 3½ Colors Suffice?

~ munizao ~ 2 Comments

The loan seemed like an incredible break. You got back on top of your mortgage, even had enough to put your oldest into a decent private school. And all they asked you to do was solve puzzles.

The puzzles were actually fun, for a while. But they got harder. And when you couldn’t solve them fast enough, the threats started. And that’s how you ended up here, wherever here is, kidnapped, bruised and bloody, on a floor covered with grit and sharp angular tesserae.

There’s a note. Another puzzle. In order to leave, you’re going to have to pick out some of the tesserae and use them to tile a shape. And no two tiles of the same color may touch. Pretty basic.

And then you realize that it’s too dark for you to be sure what the colors of the tiles are.

There’s a real problem with constraining the number of colors in a colored tiling as an additional challenge: our options just aren’t very granular. Literally everything (on a plane, which sometimes we aren’t!) can be 4-colored, a small proportion of things can be 3-colored, and almost nothing that isn’t highly contrived can be 2-colored. If only there were some options in between!

To our relief, and our hero’s consternation, there can be. Observe that we can make a graph with colors as nodes and edges connecting colors that are permitted to touch. For an n-coloring, this is simply the complete graph Kn. But there might be other graphs (we’ll call them color graphs) that produce interesting results. For example, consider this one:

We might consider one color graph to have greater “coloring power” than another if it can be used to color a proper superset of the graphs that the second graph can color. This graph turns out to have a coloring power intermediate between those of K2 and K3.

Here’s a tiling of the 2–5-iamonds colored according to the above graph. (Kadon sells these shapes as its Mini-Iamond Ring puzzle.)

There’s a reason I showed the color graph as a pentagram, even though you could rearrange the nodes into a pentagon and get rid of the crossings. Let’s take a simplified model of color where allowed instances lie on a circle of hues. From the perspective of our hero with color vision reduced by darkness, nearby colors around the circle might be too similar to safely place next to each other.

As we raise or lower the level of light in this dungeon, the minimum distance between colors that can be allowed to be adjacent in a coloring will change. We can make arcs along the circle that correspond to hues that can be legally adjusted to the hue at the center of the arc. Finally, we connect the nodes for the arcs that don’t overlap to make a color graph.

For arc lengths (as a proportion to the circumference of the circle) that are fractions of the form 1/n, we get the complete graph, Kn. But for other rational arc lengths, we get different graphs. Here’s the one for an arc length of 2/5:

What’s nice here is that the reciprocal of the arc length describes the coloring power of the corresponding graph. For the above graph, the reciprocal is 2½, and this does in fact mean that its coloring power is stronger than 2-coloring and weaker than 3-coloring. This type of coloring is called a “circular coloring“, and it extends our usual definition of chromatic numbers into “circular chromatic numbers”. The graphs that are formed by this process are “circular complete graphs”.

Here’s the color graph for a circular chromatic number of 7/2:

This one can also be useful for coloring polyform tilings. Consider this tiling of the 21 5-rects:

It is not 3-colorable, as we can see by starting at the starred pieces and following the colors that are forced until we come to the checkered yellow pieces. But it is “7/2 colorable”!

One nice aspect of this coloring scheme is that we can get balanced colorings of sets that have a multiple of seven pieces. There are undoubtedly balanced 3-colorable solutions to the above tiling problem however, so this isn’t necessarily the “best” coloring possible here. A solution to the following problem might have a good claim to the title though: Problem #57: Find a tiling of the above figure with the 5-rects that has a 3-coloring and a 7/2-coloring such that all 21 color combinations occur exactly once.

Now, you may be grumbling at this point about my title being inaccurate and click-baity, because there are clearly seven different colors here, not three and a half. And certainly, there are for you and I, who have plenty of light to see them by. But for the poor soul toiling with ambiguously colored pieces in my basement some entirely hypothetical dungeon, it really does feel like having somewhere between three and four colors available.

This is just the beginning of a rabbit-hole that can go a lot deeper than this blog post can contain. A curious person might wonder: what about other color graphs? Playing around a bit shows that a lot of different color graphs have the same “coloring power”. For example, any even cycle graph can color exactly the same graphs as K2. If you number the nodes around the cycle, even colors may only be adjacent to odd colors, (and odds to evens) and the even and odd sets of colors can color exactly the graphs that the 2 nodes of K2 can color.

In more standard mathematical terms, what the last paragraph says is that even cycle graphs are homomorphic to K2. Generally, homomorphically equivalent color graphs have the same coloring power. Every graph is homomorphically equivalent to a so called “core”, a minimal graph that captures the information we need for coloring. (In the previous example, K2 was the core.) So we can restrict ourselves to just cores when we’re looking for interesting color graphs.

The circular complete graphs we looked at are cores. Other cores exist, but they don’t fit nicely into the ordering that the circular complete graphs do, and so don’t give us meaningful chromatic numbers. But they could still be fun things to apply to polyform colorings. (Or even problems of actual mathematical import. In 2018, the lower bound of the Chromatic Number of the Plane was improved to 5. Perhaps a unit distance graph with a circular chromatic number of 11/2 could be found, effectively improving the lower bound for an extended version of the problem.)

And that’s all I have for now, although I expect that this won’t be the last time I visit the subject of colorings. Until next time, be well, and beware loan sharks bearing puzzles.

Cell colorings

~ munizao ~ Leave a comment

Most of my previous polyform coloring explorations involve map colorings of complete polyforms, i.e. colorings that adhere to the rule that no two adjacent shapes have the same color. We can color the cells of a grid instead; for example, a checkerboard is a two-coloring of the regular square tessellation, and checkered polyomino tiling problems have a long history. But for this post I want to look at problems where finding a coloring is part of the solution, rather than the coloring being given in advance.

Quite a while back, I used cell colorings for a couple of minimal common superform problems. Below, the cells of the figure on the left have been colored so that each of the 12 pentominoes occurs exactly once containing cells of all five colors. (For the common superform problems in this post, I am copying out the individual pentominoes on the right, to make it easier to see that they have a valid coloring for the problem.)

In the following figure, three colors are used. If a pentomino contains cells of two of those colors, there are 12 different color proportions possible. The figure contains each pentomino exactly once containing two cell colors, and each color proportion occurs once.

Both of these are solutions I found manually, so you may be able to find smaller figures with the desired properties.

With four colors, there are 12 ways to combine them in a 2:2:1 proportion. We could try to find a 4-colored pentomino tiling where we could overlay a second pentomino tiling so that each color combination occurs in one pentomino. The graphic below is the result of a little exploratory noodling. I just picked a tiling at random, and then tried to see how far I could get with overlaying a second tiling without repeating a color combination or using one that is not 2:2:1. Getting 8 on my first try makes me optimistic about a solution existing.

There’s nothing special about 2:2:1, either. Any proportions of the form a:a:b:c will give 12 combinations. (Zeros being implied.) So 3:1:1, or even 3:2 or 4:1 might be possible.

Problem 55: Find a pair of overlapping pentomino tilings of a rectangle where the first is 4-colored, and the second is cell-colored so that all color combinations with given color proportions are present in a single pentomino. And if that’s too easy, is it ever possible to take a solution to this problem, and then 4-color the second tiling so that the first has all of the color combinations?

We can also apply the complete set of color combinations concept to a cell-colored minimal common superform problem. Here’s a 23 cell superform of the pentominoes where each pentomino appears with a unique 2:2:1 color combination. Can you find a smaller one?

And that’s all I have for cell colorings for now. Coloring problems more generally are something I have come back to a number of times, and I expect to have another post or two to say on the subject as I plow through my as yet unblogged polyform material from the last year.

More pentomino coloring problems on torus tilings

~ munizao ~ Leave a comment

Recently I revisited one of my old pentomino coloring problems, modified to apply to a tiling of a torus rather than a rectangle. That worked out well, so I might as well shamelessly continue to mine this vein.

There are 18 one-sided pentominoes. Six of them have reflection symmetry, and the other 12 are 6 sets of mirror pairs. A while back, I asked if there was a tiling with a three-coloring where the 6 with reflection symmetry share a color, and each mirror pair has one pentomino of each of the remaining two colors. Patrick Hamlyn found that there was no rectangle tiling that could be colored in this way, but there was such a tiling of the shape below:

The one-sided pentominoes have area 90, which is the area of a tilted square on a grid:

Problem #47: Find a tiling of a torus with this tilted square as its fundamental domain by the one-sided pentominoes with a three-coloring as described above. If possible, find a tiling with no crossroads.

Another older problem that could be adapted to a torus is the minimal 2-colored packing problem. Here’s my conjectured minimal 2-colored pentomino packing of a rectangle:

(I had forgotten that this was problem #1 on this very blog!)

Problem #48: Find a two-colored packing by the pentominoes of a torus with minimal area.

Obviously, you could just take the rectangular packing above and add a one unit “moat” around it to get a torus with a 14×6 rectangle as its fundamental domain, but surely we can do better.

Complete combination colorings on the torus

~ munizao ~ Leave a comment

I posted previously about my talk at Gathering for Gardner 12 on colorings of pentomino tilings. One unexpected consequence of that is that my work has now been cited in a very prestigious… um… coloring book. Alex Bellos and Edmund Harriss previously collaborated on Patterns of the Universe, a mathematical coloring book for adults, and were looking for material for the sequel. They were attending G4G12, and saw my talk, and thought that they had found some. They wanted to use something like the strict complete combination 3,4-coloring of the pentomino tiling that I showed, but for the purpose of a coloring book page, they needed something with more shapes to color. Could I come up with such?

It seemed to me that the problem called for a pentomino tiling of a torus, which they could use as a wallpaper-like pattern, repeated as many times as they needed. The choice of the particular torus to use is a matter of taste, but I thought it would be nice to maximize the minimum distance between two images of the same point. (I haven’t proven that I succeeded, but it’s close.) In coding the solver for this, I used a shortcut: instead of directly checking whether a given tiling had a coloring of the correct type, I checked whether each pentomino bordered exactly six others. This turns out to be a necessary condition, but not a sufficient one, so I manually checked a few such tilings until I found one that worked. This is the pattern that appears, in user-colorable form, in Visions of The Universe by Bellos and Harriss.

The hexiamonds were the other obvious set of 12 polyforms to try to tile with this coloring scheme. Here, there is one torus with maximal symmetry. Amazingly, my solver found just two tilings where every piece bordered 6 others, of which exactly one had the right coloring properties. Recall that the solution for the pentominoes on the 6×10 rectangle was also unique. It seems incredible to me that this problem type has yielded two instances that were so finely balanced as to be solvable, but only by the barest of margins.

The Happiest and Saddest Tilings

~ munizao ~ Leave a comment

(Tagging under “A Polyformist’s Toolkit”, as I feel that series ought to have an entry on coloring, and this more or less says what I have to say about that.)

At Gathering for Gardner 11 in 2014, I gave a talk about crossed stick puzzles. It was the obvious thing to talk about, since I had been making a lot of interesting discoveries in that area. Unfortunately there was too much good stuff, and I couldn’t bear to trim very much of it out, so I made the classic mistake of going over on time and having to rush the last slides. (G4G talks are generally limited to 6 minutes.) When I was looking for a subject for this year’s talk, there was nothing I felt an urgent desire to talk about. This would be the 12th Gathering for Gardner, and there is a tradition that using the number of the current Gathering, either in your talk or your exchange gift, is worth a few style points. Since I’m a polyformist, and Gardner famously popularized the twelve pentominoes, revisiting some of my pentomino coloring material seemed reasonable.

Finding interesting map colorings is a nice puzzle that we can layer on top of a tiling problem. A famous theorem states that all planar maps can be colored with four colors so no two regions of the same color touch. Since this can always be done, and fairly easily for small maps like pentomino tilings, we’ll want some properties of colorings that are more of a challenge to find. I know of three good ones:

  1. Three-colorability. Sometimes we only need three colors rather than four. For sufficiently contrived sets of tiles we might only need two, but for typical problems that won’t work.
  2. Strict coloring. For most purposes, (like the Four Color Theorem) we allow regions of the same color to touch at a vertex. If we do not allow same colored regions to touch at a vertex, we call the legal colorings strict. Notice that a 3-coloring of polyominoes is strict if and only if it contains no “crossroads”, i.e. corners where four pieces meet.
  3. Color balance. If the number of regions of each color is equal, a coloring may be considered balanced. Conveniently, 3 and 4 are both divisors of 12, so we can have balanced 3-colorings and 4-colorings of pentomino tilings.

The above information would make up the introduction to my talk. It would also, suitably unpacked and with examples, take up most of the alloted time. That left little enough room to show off nifty discoveries. So whatever nifty discoveries I did show would serve the talk best if they could illustrate the above concepts without adding too many new ones. One that stood out was this simultaneous 3- and 4-coloring with a complete set of color combinations, discovered by Günter Stertenbrink in 2001 in response to a query I made on the Polyforms list:

5-omino-6x10-happiest

This is the unique pentomino tiling of a 6×10 rectangle with this property where the colorings are strict. I used it to illustrate 3- vs. 4-coloring by showing the component colorings first, before showing how they combine. To my astonishment, the audience at G4G12 applauded the slide with the combined colorings. I mean I think it’s pretty cool, but I consider it rather old material.

I still wanted one more nifty thing to show off, and while my page on pentomino colorings had several more nifty things, none of them hewed close to the introductory material, and the clever problem involving overlapping colored tilings that I was looking at didn’t seem very promising. Setting that aside, I wrote some code to get counts of the tilings of the 6×10 rectangle with various types of colorings. That gave me the following table:

Total Balanced
4-colorable, non-strict 2339 2338
4-colorable, strict 2339 2320
3-colorable, non-strict 1022 697
3-colorable, strict 94 53

What stood out to me was the 2338 tilings with balanced colorings. Since there are 2339 tilings in total, that meant that there was exactly one tiling with no balanced coloring:

5-omino-6x10-saddest

Notice that the F pentomino on the left borders eight of the other pentominoes, and the remaining three border each other, so there can be at most two pentominoes with the color chosen for the F, and no balanced coloring can exist. A unique saddest tiling balancing out the unique happiest tiling was exactly what my talk needed. Now it had symmetry, and a cohesive shape. Having important examples all using the 6×10 rectangle removed the extraneous consideration of what different tiling problems were out there, and helped to narrow the focus to just the coloring problem. Anyway, I don’t want to go on any more about how awesome of a talk it was, (especially because video of it may eventually go up on the internet, which would show how non-awesome my delivery was) but it was my first G4G talk that I was actually proud of. The slides for the talk are here.

One thing I’m curious about that I didn’t mention in the talk: has anyone else found the saddest tiling before me? Looking through old Polyform list emails, I found that Mr. Stertenbrink enumerated the 3-colorable tilings of various types (essentially, the bottom half of the table above) but not the 4-colorable tilings. From the perspective of looking for the “best” colorings, it makes sense to focus on the 3-colorable tilings, but it meant missing an interesting “worst” coloring.

This is how I roll: Sicherman dice with doubles

~ munizao ~ Leave a comment

Here are a few mostly functionally equivalent things:

2d6x3

The first is a pair of perfectly normal dice. The second is a “Merged d6”, a 36-sided die I bought through a crowdfunding campaign. Each of the sides is labeled with a sum of the results of rolling two normal dice. One of each of the even numbers between two and twelve is colored green. These let you simulate rolling doubles, as is required for games like Monopoly: each roll of two of the same number is represented. (The small print size of the numbers and the fact that it takes a moment to figure out which number is on top make this somewhat less practical than the normal dice, but I collect dice for mathematical interest rather than practicality.)

The blue and green dice are Sicherman dice. They are numbered a bit oddly. One of them has faces numbered 1, 2, 2, 3, 3, 4. The other’s faces are numbered 1, 3, 4, 5, 6, 8. The distribution of sums of die rolls is nevertheless the same as that of a normal pair of dice. In fact, it is the only non-standard numbering for a pair of dice with this property where the numbers are all positive integers.

Unfortunately, Sicherman dice don’t work for games that distinguish doubles rolls. Could we design a version of the Sicherman dice that does work for such games? The specially colored faces of the Merged d6 suggested a direction to take. We might color the faces of the Sicherman dice differently, and call a roll a doubles roll if the colors match. How many different ways are there to color the faces so as to produce exactly one match for every even number between two and twelve?

I posed this question on Google+. Joe DeVincentis found that there are sixteen essentially different solutions, of which two are the most interesting to me for designs that I might be interested in having made at some point:

1 2 2 3 3 4 — 1 3 4 5 6 8

This has the advantage of only requiring three colors, and all of the faces that never match are on the same die. It also has an easy mnemonic that you could use even without coloring the faces: one on low die, odd on high die; four on low die, even on high die. Variations where some subset of the never-matching faces are a different color from the others are considered essentially similar here.

1 2 2 3 3 4 — 1 3 4 5 6 8

Here the colors can be ordered from low to high, and have the same order on each die.

The rest of the solutions follow. For clarity, I’ve colored all of the numbers that never match black even when they exist on both dice. We may define a rule that black is not considered to match itself.

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

1 2 2 3 3 4 — 1 3 4 5 6 8

Chromatic Number of the Plane Is Still Less Than Or Equal To Seven

~ munizao ~ Leave a comment

Well, it was worth a shot.

Not a breakthrough in the CNP problem

The Chromatic Number of the Plane is defined as the number of colors required to paint the plane such that no two points one unit distance apart are the same color. There are very simple figures that demonstrate a lower bound of 4 and an upper bound of 7 for this number. But this is more or less where knowledge of this problem has stood for the last 50 years. (See the Wikipedia page on this problem for more info.)

I didn’t really expect that I could make a breakthrough, given that real mathematicians have given serious thought to this problem and gotten nowhere, but I thought this would be fun to play with. One potentially useful starting point is to consider how much of the plane one single color could cover. A disk of unit diameter is the biggest blob we can make without two points a unit distance apart. (We’ll allow some fudging about the points on the perimeter of the disk.) We can then pack these disks into a triangular array such that the distance between nearby disks in the array is also one unit. (It’s not clear to me whether we couldn’t get a slightly higher proportion of the plane in one color by flattening the parts of the circles that are closest to other circles. But in any case, the packing with circles should be close to the best we can do.)

It was easy enough to make an array of disks in this fashion using Inkscape. I then copied the array five times, gave each of the six copies its own color, and made them all translucent, so that the overlapping areas could be readily distinguished. The point of this exercise is this: if I could find a way to arrange the six arrays of circles so that they completely covered a region of the plane, I would be able to demonstrate the existence of a coloring that uses only six colors. In other words, I would have decreased the upper bound of the chromatic number of the plane by one, which would have been a significant mathematical result. Note that the circles could and would overlap; any areas of overlap would consist of points that could belong to either color in a valid coloring.

As you can see, I failed. The illustration above was about the best I could do. The white gaps represent areas that could not be colored with any of the six colors. Failing here really proves nothing. Even if I could prove that no coloring using disk arrays like these could work, it wouldn’t prove that there wasn’t some other way to partition the plane that would work better. In fact, Ed Pegg found a configuration where the amount of space needed by the seventh color is very tiny indeed, which gives some hope that 6 colors is possible.

If I could prove that this array of circles really represented the greatest possible proportion of the plane that could be taken up by a single color, (which I can’t) I would in fact be able to improve the lower bound of the CNP. If I didn’t make a mistake, the proportion of the plane taken up by the array of circles works out to π/(8·sqrt(3)), or about .227. Since this is less than ¼, that would mean that the total area that could be taken by 4 colors could not cover the whole plane. Part of the problem here is that even if one could show that the array of circles had the highest proportion of the plane of any “nice” arrangement, it might turn out that an actual coloring of the plane with the fewest colors would end up taking the form of interpenetrating fractal foams, where no individual piece has a measurable area.

Polyform Link Roundup

~ munizao ~ Leave a comment

There have been a few recent developments worth noting in the world of polyform puzzles:

Rodolfo Kurchan has posted Puzzle Fun #25. Some good new coloring problems using multiple sets of polyominoes.

David Goodger has been doing some good work on triangular and hexagonal grid polysticks.

George Sicherman is continuing to make advances in the realm of polyform compatibility problems. He also recently posted a catalog of the polypennies up to order 6.

KSO Glorieux Ronse is a school in Belgium that has, over the past decade, conducted a wonderful educational experiment by posting contests based on polyomino problems that could be engaged with by their own students just as much as the world’s puzzle solving elite. (The latter tended to win, of course.) Their 50th contest, which they state was their final one, was held late last year. They solicited the polyform puzzle community for problems to use in the contest and got quite a few, including one from me. No word yet on the results of the contest, (or their previous one for that matter) but the problems there are still pretty interesting.

I’ll be at the 10th Gathering for Gardner (G4G10) this week, and I expect that I’ll come back with quite a lot to think and post about. If you’re going to be there, my talk on Flexible Polyforms has tentatively been scheduled for the Thursday morning session. I hope to see some of you there!

2-coloring Pentomino Packings

~ munizao ~ 2 Comments

I like to collect pentomino coloring problems.

So it should come as little surprise that I was intrigued by the cover of Puzzle Fun 16. Puzzle Fun was a ‘zine produced by Rodolfo Marcelo Kurchan in the ’90s covering a variety of polyomino problems. I missed out on subscribing to it myself, and the Puzzle Fun website languished for a decade after new issues stopped appearing.

A few months ago, Kurchan put the content of all of the back issues of Puzzle Fun online.

Puzzle Fun 16 focused on pentomino packing problems. Packing problems differ from tiling problems in that empty space is allowed, and the goal is to minimize the amount of empty space required. Packing, usefully, makes some kinds of problems possible to solve that would not be solvable as tiling problems.

One such puzzle type is packing polyforms that are 2-colorable, (that is, one can use two colors to color every piece such that no piece touches another of the same color.) This is the puzzle type I saw on the cover of Puzzle Fun 16.

The problem itself was this: Place two sets of pentominoes in the smallest possible rectangle such that no pentomino touches another in the same set. [PF problem #549]

A solution was printed in Puzzle Fun 18:

(Solution by Hector San Segundo.)

I should note that this problem implies strict coloring: pieces are not allowed to touch even at corners. I am more interested in non-strict coloring, which is generally the default in coloring problems, and I am interested in colorings of a single set of pentominoes. (Which all of the problems on my pentomino coloring page are.)

#1: Place a 2-colorable (non-strict coloring) set of pentominoes in the smallest possible rectangle. My best attempt has 65 squares:

Filling out the matrix of variations gives two more problems:

#2: As #1, but with a strict coloring.

#3: As in PF #549, but with a non-strict coloring.

(The following problem in PF 16 (#550) was a variation on #549 minimizing perimeter rather than area, but this is less interesting to me.)

http://www.puzzlefun.com.ar/