Archive for the ‘Recreational Mathematics’ category

World Cup Group Scores, and “Birthday Paradox” Paradoxes

June 23rd, 2014

Here’s an article from the BBC about the so-called “Birthday Paradox” applied to the teams of the 2014 FIFA World Cup. The Birthday Paradox is the term for a common failure of intuition. It’s rather unlikely for two people to share a birthday, and people usually expect it to remain unlikely for any two people in a group of moderate size to share a birthday. In fact, the number of pairs of people grows quadratically, so the probability that there is at least one pair sharing a birthday hits 50% more quickly than people often assume.

It turns out that the tipping point for the size of the group is 23, which is exactly the size of a World Cup soccer team roster. And the teams this year illustrate the balance perfectly: exactly half of them have players that share a birthday. As Ξ points out on the math blog 360, even though 50% is the proportion of teams we would expect to have birthday-sharing-players, it’s actually pretty unexpected to hit the expected value exactly. That might be a “Birthday Paradox” Paradox.

But not the one that I set out to write about! Situations like the Birthday Paradox can come up in all sorts of contexts. Four years ago I noticed an interesting fact: all of the groups in the first round of the 2010 World Cup had different score results. This seemed unlikely to me, but was it really? I’d need to do some more investigation to find out. 2010 was indeed the first time that all of the scores had been different since the World Cup expanded to eight groups in 1998, but there had only been a total of four World Cups to that point, not enough for a good statistical sample.

A bit of background: In the group stage of the World Cup, there are eight groups of four teams; in each group all of the teams play each other in a round-robin mini-tournament. Each team receives three points per victory and one point per draw. The top two teams in each group advance into the next stage, a four round single elimination tournament. (There are tiebreaker rules for determining who advances when the second and third teams tie; I won’t get into those here.)

You can model group results with with oriented graphs: directed edges correspond here to a victory for the team that the edge points away from, and absent edges stand for ties. There are 42 distinct oriented graphs with four vertices, but only 40 different group scores; in two cases the same score can be achieved with two different graphs.

World Cup Group results as oriented graphs

For the sake of mathematical simplicity, let us assume that every game that is played has an equal probability of being a tie, a win for team A, or a win for team B. This makes the problem easier to model at the expense of some realism. In the real World Cup, there are better teams and worse teams, and the teams are seeded into groups such that there is approximately one team belonging to each quartile in each group. (Concerns like geographical distribution may interfere with this ideal.) This means that results with cycles of victories are probably a little less likely in the real world than in our model, as they would require a team that is worse on paper to defeat one that is better. Upsets do happen, but their unlikelihood is what makes them upsets. Additionally, the actual proportion of ties may diverge from 1/3, although this is not in fact a terrible estimate. In 2010, 14 of the 48 group matches were draws.

Complicating matters, the graphs are not equally likely to appear. Notice that a graph with no symmetry (such as the 9-6-3-0 graph in the upper left corner) can occur in in as many ways as there are permutations of the four teams. (There are 24.) At the other extreme, the most symmetrical graph belongs to the group with all ties in the lower right, which can occur in exactly one way. In general, the graphs with more symmetry can be made in a smaller number of different ways. Counting the scores that can be achieved with two graphs, there are 2 scores that can be reached 36 ways, 21 that can be reached 24 ways, 9 that can be reached 12 ways, 3 that can be reached 8 ways, 2 that can be reached 6 ways, 2 that can be reached 4 ways, and 1 that can be reached 1 way. We can check that we’ve got them all by noting that this adds up to 729, or 36, which is the number of different ways six games can go.

I wrote a Python program that found the above counts and then used them to determine the probability that no two groups would have the same score in our model. But before I did that, I wrote another program to simulate the results of a group stage by randomly picking the results of each game. Even though this simulation couldn’t give an exact answer to the problem, I’m glad I wrote it. It was a much simpler program than the one I wrote to get the exact answer, so it was easier to convince myself that it was performing correctly. In the process of writing the final program, I made a number of mathematical and programming errors that led to incorrect results; if I did not have a good idea of the approximate value of the answer, I might have stopped without knowing there was an error.

The end result? The probability of all eight groups having different scores in my model is 393101879398962298880/984770902183611232881, or about .39918. So I was right that all groups having different scores was the less likely case, but wrong to think that it was particularly unlikely. I think a big part of why I was wrong was that I knew about the Birthday Paradox. It primed me to think that no two items in a group sharing a property would be unlikely, in a more general sense than is actually the case. This is the “Birthday Paradox” Paradox that I fell into.

Some puzzles:

Which is more likely to have all different group scores? The men’s World Cup, or the women’s World Cup? The women’s World Cup has had four groups since 1999. (This is a trickier question than it seems, and may illustrate the limitations of the random result model.)

What proportion of ties would maximize the probability that all group scores are different?

We might explore the probability of all group scores being different in various past and hypothetical tournament setups. What if there were more or fewer groups? What if wins counted for two points, as was once the case? What if there were five teams per group? In the cases with four teams per group where there are two different graphs that give the same score, the sets of team records are the same. (For example, in the 7-4-4-1 groups, the records are set of team records for both (expressed as wins-losses-ties) are 2-0-1, 1-1-1, 1-1-1, and 0-2-1.) With 5 or 6 teams, is it possible to come up with a group score that can be formed by two different sets of team records?

(Thanks to Joe DeVincentis, who took up the main puzzle when I posed it on gplus. Also, I should note that the correspondence between World Cup group results and oriented graphs is not original to me; here’s another exploration of the connection.)

A Magic Dart Puzzle

April 16th, 2014

Recently I was looking at the following figure, in the context of trying to find useful configurations to make crossed stick puzzles with:

golden-dart

Now, a four piece crossed stick puzzle seems likely to be rather trivial to solve, but it sparked a question: could there be a good, non-trivial puzzle that uses this dart configuration? I recalled that I had in the past made such a figure with craft popsicle sticks:

magic-dart-blank

This assemblage of sticks suggests some sort of puzzle where there will be some figures printed on the sticks at the intersections between the pieces, and there will be some goal concerning the figures that are showing on the sticks that are on top at the intersections. With four sticks, there are 4! permutations of the sticks, and if each stick can be flipped over or rotated 180°, there are 4!·44 = 6144 possible arrangements of the sticks. (Because we can flip over the entire assembly, there are only half as many physical arrangements of the sticks, but it seems reasonable to consider either side of an assembly to represent a different arrangement, since we will probably want a goal for the puzzle that is only concerned with what is visible on one side.)

In the crossed stick puzzles that I have looked at thus far, the only sites that vary have been the intersections between pieces. However, if we allow rotating the pieces, there will be sites that can either be at intersections or not, depending on how the piece is rotated.

magic-dart-sites

I first toyed with using colored marks at the variable sites, possibly with holes in the pieces that could reveal the color of the piece behind it. However, I made more progress when I turned to the idea of putting numbers at the sites. Since there are eight sites on the two sides of a piece, I thought of putting each number between 1 and 8 on one of them. This suggested to me a puzzle along the lines of a magic square, where the goal would be to make a figure where the sums along the four lines all matched. I noticed that there are exactly four ways to partition the numbers 1 to 8 into two sets of four, such that each set has the same sum (18):

1 2 7 8 | 3 4 5 6 
1 3 6 8 | 2 4 5 7 
1 4 5 8 | 2 3 6 7
1 4 6 7 | 2 3 5 8

That would give me an elegant way to place numbers on each side of the four pieces, but I still needed to find a way to arrange the numbers. The simplest way would be to place them in order from smallest to largest. I wrote a short Python program to output the solutions. Unfortunately, there weren’t any! After that I tried other orderings. (Note: due to a bug in my program, what I previously had here was incorrect.) If we number the sites from smallest to largest as 0 through 3, ordering the sites as [0, 2, 3, 1] gives a single unigue solution:

magic-dart

Ordering the sites as [0, 3, 1, 2] gives four solutions with a magic sum of 18, and four solutions with a magic sum of 17. Notice that magic figures like this have a numerical “reflection” symmetry. Given a solution, you can generally obtain another by replacing every numeral n with 9 – n. This means that the orderings [2, 3, 0, 1] and [3, 0, 2, 1] will behave basically like the orderings mentioned above. Other distinct orderings with solutions are [0, 1, 3, 2] (7 solutions), and [1, 0, 3, 2] (2 solutions).

I’ve only started looking into how I could physically produce such a puzzle. Custom printed and die cut PVC looks promising; I think the marginal cost of a piece would come to under 10¢; the real problem would be in the setup cost, and in the unlikelihood of minimum orders of less than 500 for each piece being feasable.

As an aside, once I was looking at those partitions of the integers 1-8 into eight subsets with equal sums, the obvious thing to do with them was to make a 4×4 “magic square” where each of the subsets occurs once as a row or column. Here’s one where the diagonals also have a sum of 18:

magic square of partitioned subsets

This seems like the sort of idea that would have to have been looked at before, but I have no idea how to find out where it may have been previously discussed.

Stop! In the name of Octagons!

March 29th, 2014

In the spirit of the flexible rhombic cell polyominoes that I posted about previously, here’s a hexiamond tiling of eight triangular segments squashed into an octagon:

hexiamonds in an octagon

Of course, octagons can also be used as base cells for polyforms. In fact, any regular polygon (and quite a lot of other things) can be used in this way, but octagons are special. They don’t tessellate the plane by themselves like equilateral triangles, squares, and hexagons, but they do form a semi-regular tessellation of the plane along with squares. This makes polyocts behave fairly well; you won’t be able to tile something convex and hole-free with them, but you can tile something that’s reasonably symmetrical at least. For example, here’s a tiling of the 1-, 2-, 3-, and 4-octs:

polyocts-2

That’s not the most symmetry that polyocts are capable of, (full octagonal symmetry is possible) but it’s the most we’re going to get with this set of pieces. See this page by George Sicherman for some figures with full symmetry that can be tiled with various individual polyocts.

Some Contributed Solutions

October 2nd, 2013

I’ve had a few solutions sent in recently, so I wanted to share them with you all.

First, Abaroth noticed that my rhombic-cell pentomino tiling had just enough space to fill out into a five pointed star if the tetrominoes were also included:

tetra-penta-star

But that was just the beginning! He then proceeded to produce an entire collection of tilings with these pieces, which he calls flexominoes. One problem that can come up in tilings of this sort is that if there is a vertex with three rhombi around it, a polyomino containing all three rhombi has an ambiguous identity, since there is more than one way to “unglue” the polyomino at that point. I contributed an ambiguity-free solution to one of the patterns Abaroth found:

flexomino-8-star

Speaking of rhombuses, Abaroth has been investigating color-matching puzzles using rhombic tiles. His puzzle page has more interesting material on color matching puzzles and symmetrical polyhex tilings.

Next up, George Sicherman sent in a symmetrical tiling for the flexible tetrarhombs:

tetrarhomb-gs-sol

What’s interesting here is that although the outline of the tiling is symmetrical, the pattern of the cells isn’t. The lesson here is that being able to trade off some cell-level symmetry for more pattern-outline symmetry can give us a little variety in our choices of what we can tile.

Finally, Bryce Herdt provided a de Bruijn sequence of invertible length 5 binary words. (That is, a cyclic sequence where each word occurs once as a substring.) Since he did so in text format, I made a visualization:

debruijn-invert

Flexible polyrhombs

September 11th, 2013

From time to time, a pentomino tiling still manages to surprise me.

pentomino tiling with 5-fold dihedral symmetry

Normally, the largest number of symmetries you can make a pentomino tiling have is eight, the number of symmetries of the square. For example, we can tile an 8×8 square with the corner cells removed. (If we leave the plane for other topologies like cylinders and tori we can get more.) However, it’s a basic principle of flexible polyform tilings that we can generally try to squeeze one more repeated unit around the center of a rotationally symmetric tiling. So I did.

But my starting point for this was not the pentominoes. In my Hinged Polyform post, I discussed polyforms where the connections between pieces could occur at arbitrary angles. Conversely, we could look at polyforms where the shapes of the individual cells could contain arbitrary angles. If we assume that all of the edges are the same length, there is only one possible triangle, so polyiamonds in this scheme aren’t interesting. Rhombuses are the simplest example of cells where the angles can vary. Since they have only one degree of freedom per cell, they are reasonably tractable. The flexible tetrarhombs include flexible versions of the five tetrominoes in addition to the three shapes in blue below:

pentaflexirhombs

The flexible pentarhombs include the flexible pentominoes, the 18 forms that can be derived by adding a single red cell to one of the blue forms above, and the six additional forms in green. (I may well have missed some.)

It may be possible to find a good flexible tetrarhomb tiling, but I haven’t yet managed it. And 36 pentarhombs is too many for me to handle. If only there were some subset with a better number of pieces for a puzzle, something like the 12 pentominoes.

Oh. Right. (And that was more or less the thought process that led to the tiling above.)

Hinged Polyforms

August 30th, 2013

Here’s a tiling of the nine hinged tetriamonds:

hinge-iamond-2

Hinged polyforms meet at corners rather than edges as in regular polyforms. The corner connections, like hinges, are flexible: two hinged polyforms are equivalent if it is possible to turn one into the other by swinging the hinges at the vertices, in addition to rotating and reflecting the whole pieces. Hinge angles that cause two cells to lie flat against each other are disallowed, as it isn’t possible to visually distinguish which side of the edge has the hinge. In some cases, hinges may be “locked”, with angles that are completely determined by the geometry of the piece. (For instance, when three cells meet around an equilateral triangle.)

With the above piece set, it is possible to realize all of the pieces using a small set of angles for the individual triangles. Other sets may be trickier to work with.

Here are the hinged tetrominoes:

hinge-4-ominoes

Can a symmetrical tiling be found for these? Problem #43: Find one.

Constellations

August 22nd, 2013

I made a presentation on flexible polyforms at the last Gathering for Gardner, but there were some polyform types that I didn’t get to, since I hadn’t yet come up with any good problems for them. One odd sort of polyform, which I am fancifully calling a constellation, can be obtained from configurations of points on the plane. We can consider two sets of points on the plane to be distinct if the pattern of collinearity among the points is different. Because every pair of points defines a line, the lines with only two points are, in a sense, not interesting; only the lines with three or more points need to be considered when determining whether two constellations differ. It seems reasonable to consider the order of points on a line to be significant; this gives us three different 5-point constellations with a pair of three point lines that meet at a point. There are 7 5-point constellations in all. Here’s the first tiling puzzle solution I found for them:

constellation-5-5

One rule for constellation tiling puzzles that I like is to disallow any point from one constellation from falling directly between two points in another constellation. This keeps the constellations more compact, and adds a little challenge to the puzzle. I like to get as much symmetry as possible in one of these flexible polyform tilings, so I decided to try for one with 7-fold symmetry. This was a little harder, but eventually I found the following tiling:

constellation-5-7

Where can we go from here? If I’ve counted right, there are 21 6-constellations. Of these, 7 can be formed by adding one independent point (a point on no line of 3) to each of the 5-constellations. The full set seems a little too big to solve by hand, but if we exclude the ones with independent points, a puzzle with the remaining 14 seems more manageable. (We may also want to exclude the 6-constellation with two separate lines of three points. With that one excluded, the remaining 13 6-constellations all can be formed from connected groups of lines with 3 or more points.)
constellation-6-set

The 14 6-constellations with no independent points.

Problem #42: Find a tiling of 6-constellations with 6-fold dihedral symmetry. Either the set of 13 or the set of 14 will do. Even more symmetry is even better.

Crossed Sticks: Compatability Variations

August 19th, 2013

So far, the crossed stick puzzles I’ve designed have been limited by the two-dimensional nature of designing for lasercut materials. But 3D printing presents another option for puzzles that can’t be formed from flat pieces.

One new area to explore is connector compatibility variations. In most of the puzzles we’ve looked at thus far, there are two types of connectors or slots, ups and downs, or deeps and shallows, and each type matches the opposite. Suppose instead we wanted two types of connectors where each matches itself rather than the other type. It can’t be done (as far as I can tell) with lasercut slots, but it can be done! My first 3D printed puzzle prototypes are shown below:

3d-protos

Consider connectors made of pairs of studs and holes as in the the puzzle on the left side of the image above. When we flip and rotate a piece with this type of connector in order to join it at right angles with another such piece, the studs on each piece match the holes on the other. But this only works when the two connectors have the same orientation. When a connector with a vertical stud pair is matched with a connector with a horizontal stud pair, both pairs of studs end up at the same position, so the connectors can’t join. We can call this connection scheme the same-match scheme, as opposed to the other-match scheme.

With diagonal pairs of studs and holes, (as on the right side above) flipping the piece swaps the positions of the studs and holes instead of keeping them in place. This means that the resulting puzzle will use the standard compatibility matrix. Initially, this may seem disappointing: after all, this is just the puzzle we could get without using stud and hole blocks. But in fact this setup allows us to use both compatibility schemes! If we place both layers of pieces so that the studs face the same direction, we have a puzzle using the same-match scheme.

It should be pretty clear that these two schemes are the only viable connection schemes for two connection types. When we move to three connection types, things get a little more complicated. It will help to represent a connection scheme as a graph, where the vertices represent connection types, and compatible types are connected by an edge. Since self-compatibility is possible, the graphs may contain loops from one vertex to itself. Here are the graphs for the two binary connection schemes:

2-compats

One example of a ternary connection scheme can realized with lasercut slots. Let the three slot types be deep, middle, and shallow, where middle depth slots match themselves, and deep and shallow match each other. Here’s the graph for that scheme:

3-compats-1

The advantage of working from graph representations of connection schemes is that we can come up with the graphs first, and then worry about how we will physically realize a puzzle using that scheme later. So let’s just doodle some promising three-vertex graphs:

3-compats-all

Some constraints become apparent at this point. First, there can’t be a vertex with no edges, because that would represent a connection type that can’t connect to anything, and its presence would immediately render a puzzle unsolvable. Vertices that connect to everything (including themselves) are also problematic. Such a connection type doesn’t add to the challenge of a puzzle, and if all vertices had this property, the puzzle wouldn’t be a puzzle at all. I’m inclined to remove graphs with this kind of vertex from consideration for the time being, allowing that I may be wrong, and interesting puzzles using this kind of vertex may indeed be possible.

Another problem that can occur is that vertices may be indistinguishable. For example, consider this graph:

3-compats-indist

Both the rightmost and the leftmost vertex in this graph are connected only to the center point. What this means in practice is that it doesn’t matter whether a connector has the leftmost vertex type or the rightmost vertex type; the connectors will behave exactly the same. But if this is so, there is effectively no difference between this connection scheme and the other-match binary scheme. For the connector types in a scheme to be distinguishable, each must have a different neighbor set.

A quality of a connection scheme that may be desirable is balance. Consider the following graph:

3-compats-unbalanced

The rightmost vertex only connects to one vertex, while the others both connect to two. Now imagine a puzzle that uses equal numbers of all three connector types, as we have typically done so far. Since we need all rightmost type connectors to match something, we have to use up all of the middle type connectors for this purpose. This means that the leftmost type connectors must all match themselves. Since no leftmost type connectors can match middle connectors, we find ourselves effectively using the three-height slot scheme. This doesn’t mean that this scheme is entirely unviable, but our piece sets are going to have to look a little weird to make it work. For the moment we will mainly concern ourselves with balanced schemes, where each vertex has the same degree. (That is, they are connected to the same numbers of vertices.)

Another consideration that will be important is the density of the graphs. This quantity is the ratio of the degree of the vertices (or the average if the scheme is unbalanced) to the total number of vertices. The density will have an effect on the difficulty of the puzzle and the number of solutions, since a high density means that if we randomly distribute connections, each connection has a high likelihood of being valid.

The following are the “good” ternary connection schemes under the above constraints.

3-compats-viable

The schemes in the top row have density ⅓, and those in the bottom row have density ⅔.

I could keep going about how we could realize some of these schemes in 3D printed puzzles, and I could get into quaternary schemes, but longpost is already long, so I’ll save this for later.

A Ten Piece Triangular Grid Puzzle Configuration

June 24th, 2013

Here’s a configuration that I found while doodling a few weeks ago:

hex-10

At the time, I was thinking of the 12 piece puzzles I found using the triangular grid; this configuration could be an easier challenge for that puzzle set that wouldn’t use all of the pieces.

But it could also make a good puzzle in its own right. We can use exactly the same slot scheme here as in the decagram puzzle. That puzzle used deep/shallow slots, (pointing the same direction) at the inner slot positions, and up/down slots at the outer positions. There are ten such pieces, which can be flipped horizontally but not vertically. Outer slots always connect with outers, and inners with inners, and the inner connections are bipartite, so it ought to work.

Ups and Downs (and Deeps and Shallows) revisited

June 21st, 2013

hexcross

I would like to be able to report that I have produced a successful prototype of the crossed stick puzzle I described in a previous post. But I cannot. This photo is a lie. There are two configurations for this puzzle, for which I intended to use two copies of each of the six possible pieces with up/down binary slots:

hexcross-both

I say “intended to” because the puzzle appears to not be possible to solve. Specifically, the 0110 piece is rather intransigent for the configuration on the left, and it doesn’t seem possible to fit two of them in without changing the piece set. Which is indeed what I did to put together the solution shown at top. For the configuration on the right, 0101 is the problem piece.

Problem #41: Are there sets of pieces that can be assembled into both of the above figures? It would be ideal if all 6 possible pieces are present in at least one copy. (I’d have explored this manually, but for the other reason this prototype was a failure: the material was too thick for the width of holes I used, and a number of pieces snapped in the process of trying to assemble the above. So I am not able to test out whether I can make two different configurations with any piece set without running out of intact pieces.)

In crossed stick puzzles, we like for solutions to be “assemblable,” meaning that there is no cycle of pieces where each has a downward facing slot connected to the next piece and an upward facing slot connected to the previous piece. (If there were, there would be no piece you could place last.) The assemblability condition implies the existence of a partial ordering among the pieces, where the pieces are ordered according to which ones are “on top” of other pieces. It follows that that there must be at least one piece with all slots pointing up and one piece with all slots pointing down.

It turns out that the Star of David puzzle using a single set of these pieces, which I proved was unsolvable due to a clever parity argument, is also unsolvable because it has only one 0000 piece. (Likewise, the dual Star of David puzzle using two sets of pieces, which I proposed in order to get around the parity problem, is also unsolvable, because that would require four 0000 pieces.)

An alternative to the up and down slot scheme is the deep and shallow slot scheme, where all slots point the same direction on each piece. This scheme bypasses assemblability issues entirely, but it has another problem: because upward and downward pointing pieces may only connect to each other, the configuration they form must be bipartite. It turns out that a lot of interesting configurations aren’t! Here are the configurations possible on a triangular grid with 12 pieces with three equally spaced slots:

(Did I miss any?

(Did I miss any?)

Only two of these configurations are bipartite. They can be made with a double set of 6 pieces with a deep/shallow slot scheme. Here are a couple of prototype lasercut puzzles in these configurations:

minihexcross

But what about the rest? Is there some way we can change our piece set to be able to make them? If we allow the middle slot to take all four possible combinations of up/down and deep/shallow, while the outer slots are deep/shallow and, as before, point the same direction, the resulting set should be more flexible in the configurations that can solve. (Conveniently, there are twelve such pieces.) Any subconfiguration with a cycle formed by an odd number of pieces that is connected only by outer slots is still impossible to solve. Therefore the configuration with the triangle shown in brown is still impossible. But the others should still be solvable.

(As I was finishing off this post, another set of pieces to use with these configurations occurred to me. We can make a set of pieces where each piece has exactly one deep, one middle, and one shallow shot, and the slots can occur in either direction and any order. As before, there are twelve such pieces. Can they be assembled into all of the above configurations?)

3.8.24

May 27th, 2013

A regular 24-gon, octagon, and triangle together form one of the 17 ways (called vertex figures) to surround a vertex with regular polygons. This vertex figure can’t do anything nice like tile the plane. You can surround the 24-gon with octagons and triangles, but then you have gaps that can’t be filled with regular polygons, and you have to stop.

24-8-3-rose

Or, instead of stopping, you could take that 24-gon surrounded by octagons and triangles, and surround it with 12 more 24-gons surrounded by octagons and triangles, overlapping in an elegant sort of way:

24-8-3-doodle

And then, instead of stopping there, you could surround that whole thing with more copies of that whole thing…

But sometimes art is where you stop.

Hat tip to John Baez, who brought up the 3.7.42 vertex figure in a Google+ post.

A Polyformist’s Toolkit: Practical Topology

May 23rd, 2013

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×5 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.

The tetrominoes, and a 5×4 rectangle.

This will never work…

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×4 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.

The tetrominoes tiling a 5×4 cylinder a cylinder

…until we wrap the rectangle into a cylinder.

There is a video 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, designed by Marko Pavlović, 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.

A cylinder isn’t our only option. We could give the rectangle a half-twist before connecting the ends; this gives us a Möbius 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— 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öbius 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:
Topologies for polyomino tilings
Only 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öbius strip, Klein bottle, and projective plane are nonorientable surfaces, which means that they effectively have only one side.

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.

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 to MathPuzzle.com. Here’s one:

7-colored 7-omino torus

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×10 tori using this scheme in 2003:

The 35 hexominoes in 7 3×10 tori, 3-colored

This problem has no solutions if the tori are replaced with rectangles or cylinders.

Problems #31-37:
Though 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×20 together should not give any solutions beyond the two obtained by wrapping the solutions on the 3×20 rectangle. That leaves the 3×20 wrapped the other way, and both ways of wrapping the 4×15, the 5×12, and the 6×10 rectangles.

Problems #38-40: Find the solution counts for the 4×15, 5×12, and 6×10 tori. I don’t know if these are all computationally tractable, but I can hope. (The 3×20 will be the same as the 3×20 cylinder with long sides wrapped together.)

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.

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

May 6th, 2013

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.

Three More Crossed Stick Puzzles

March 28th, 2013

Since I last posted about crossed stick puzzles, I’ve come up with three new ones. Here’s one of them:

This one nicely fills one of the spots in the binary word table. There are eight pieces with three slots apiece; if we use binary shallow/deep slots, there are exactly eight possible pieces, because the pieces won’t be flippable vertically or horizontally within the puzzle.

The principle behind this piece configuration can be used to make other configurations. You can take any line segment, together with a center point, reflect the segment across an axis passing through the center, and create images of the original and reflected segments over successive rotations around the center to make configurations with rotational (indeed, dihedral) symmetry. However, because the pieces wouldn’t generally be horizontally flippable, (are there exceptions?) this only produces puzzles with combinatorially complete piece sets when the number of pieces is a power of two, and only 8 and 16 make reasonable numbers of puzzle pieces. In fact, I’d argue that the ideal range of numbers of pieces for a puzzle of this type is between 8 and 12, with a penumbra extending to about 6 and 16 in which puzzles will still be interesting to some solvers, but not as many. This necessarily constrains the quantity of viable puzzle configurations to a number that is finite, and may indeed be quite small.

But if the math keeps the number of possible puzzles down, inventing new ways to skirt the constraints we’ve set for ourselves can create new possibilities. Witness the following configuration:

Here the slots are ternary: intersection points can have slots that are ⅔ of the width of the piece (pointing up or down) or they can have two slots ⅓ of the width of the piece, pointing both up and down. Where three pieces intersect, one of each of these three slot types must be present. Three piece intersections are harder to work with than regular intersections. I’m pretty sure there is no finite configuration on the triangular grid containing all pieces of the same size with all intersections being three piece intersections.

So we have to fudge. This configuration looks like it has two kinds of three slot pieces, because three of the three slot pieces intersect at a two piece intersection. The trick is that the slot on the two slot pieces at the two slot intersection has a special, single ⅓ width slot, so that it can match the regular slots on the three slot pieces. Nicely, there are exactly three possible two slot pieces with one slot of this type and one regular slot.

In this scheme there are ten three slot ternary pieces, when both horizontal and vertical flipping is allowed. Since there are only nine three slot pieces in the configuration, one piece must be excluded. In fact, our hand is forced: the excluded piece must be the one that has all three slots of the double ⅓ width type. This is because the total number of double ⅓ width slots must equal the number of three piece intersections, which is nine. Before excluding that piece, there is one double ⅓ width slot in the two slot pieces, and 11 such slots in the three slot pieces. Well, if we can’t have a combinatiorially complete set of pieces, the next best thing is a combinatorially complete set minus the most exceptional member, which we could argue that this piece is, on account of it being the only piece with both horizontal and vertical reflection symmetry.

Finally, two configurations for the same piece set:

The configuration on the left was one that I implied in this post. If we use shallow/deep binary slots, we have pieces that can be flipped horizontally but not vertically. There are six of these and twelve pieces in the configuration, so we can use a double set of these as our piece set. As an extra bit of good fortune, there is a second configuration that uses these pieces.

I’m currently getting prototypes of the last two of these lasercut, so I hope to be able to show off the results soon. (I came up with the first one after I put in the order, so it will be a while before I get around to making a prototype of it.)

More Fun with Binary Words: De Bruijn Sequences

January 1st, 2013

In the previous post, we explored symmetry variations on binary words in the context of crossed stick puzzles. Now I want to look at some ways to play with sequences of these binary words. For reference, I’ll recap the table of numbers of different binary words of various types and lengths from that post. As before, swapping 1’s and 0’s with each other gives equivalent invertible words, and turning words backwards gives equivalent reversible words.

You’ll notice some new columns in this version of the table. Cyclic words remain equivalent over any number of cyclic shifts or moves that take every digit but the last down by one place and put the last into the first place. You can think of the digits as black and white beads on a necklace, where the necklace stays the same however you rotate it. The cyclic property can be combined with invertibility and reversibility; reversing a cyclic word is equivalent to “flipping over” the necklace.

Length Fixed Invertible Reversible Inv. & Rev. Cyclic Cyclic Inv. Cyclic Rev. Cyclic Inv. & Rev.
1 2 1 2 1 2 1 2 1
2 4 2 3 2 3 2 3 2
3 8 4 6 3 4 2 4 2
4 16 8 10 6 6 4 6 4
5 32 16 20 10 8 4 8 4
6 64 32 36 20 14 8 13 8
7 128 64 72 36 20 10 18 9

One classic puzzle involving binary words is to find a necklace where every possible word of a given length is present exactly once exactly once as a substring of the necklace. These necklaces are known as De Bruijn sequences. For example, here’s a De Bruijn sequence of length 4 binary words:

Since we have a bunch of variations on binary words, we can look for De Bruijn sequences of each of them. Neither the cyclic nor the reversible words will make proper De Bruijn sequences. Consider the length 3 word 000. There can’t be another 0 on either end of that, because that would make a second instance of 000 in the sequence. So there must be a substring of 10001 in the sequence. But that gives instances of both 001 and 100 which are equivalent to each other both as cyclic and reversible words. The same reasoning applies to longer words.

However, you can make improper, non-cyclic De Bruijn sequences. For example, 00010111 is an improper De Bruijn sequence of the reversible length 3 words. For the reversible length 4 words, even an improper De Bruijn sequence is impossible. (Try to make one, if you are wondering why.) Problem #29 is to find an improper De Bruijn sequence for the reversible words of length 5.

The invertible and reversible length 4 words do have an improper De Bruijn sequence: 000011010. And with plain invertible words, proper cyclic De Bruijn sequences are again possible. Here’s a De Bruijn sequence of the invertible words of length 4:

Problem #30: Find a De Bruijn sequence of the invertible words of length 5.

Unlike polyform puzzles, De Bruijn sequences are considered a topic for respectable mathematics, which means that they are well studied, and therefore it can be assumed that anything written here is well known by those who know such things. Still, they are fun to think about, and have real world applications. For example, in the study of Sanskrit poetry, a mnemonic based on the nonsense word yamātārājabhānasalagā has been employed. In this word, the syllables correspond to the names of three syllable feet, (like anapests and dactyls in western poetry) and the three syllable segment starting with a given syllable has the same stress pattern as the foot denoted by that name. (The syllables with macrons are stressed and the others are unstressed.) If you truncate the last two syllables, the stress patterns “wrap around” to create a proper De Bruijn sequence.

And I still haven’t gotten to Gray Codes. Well, I’ll get to that in a later post. Unless I get distracted and never get back to it, which is a real possibility.

(Sources: Wikipedia on Sankrit Prosody and De Bruijn Sequences, and Professor Stewart’s Cabinet of Mathematical Curiosities by Ian Stewart.)