Archive for the ‘Recreational Mathematics’ category

« Older Entries

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.

No comments »

Posted in Recreational Mathematics

Tags:

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.)

No comments »

Posted in Recreational Mathematics, Zapped Puzzles

Tags:

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.)

No comments »

Posted in Recreational Mathematics

Tags:

Symmetry Variations on Binary Words

December 18th, 2012

In exploring the space of crossed stick puzzles, I’ve gone on a tangent into the world of binary words and their symmetries. A binary word is just a string where the “letters” can be one of two symbols; for convenience we’ll use 0 and 1. (The distinction between a “word” and a number in binary is that a word can have any number of leading 0′s, and these are significant.)

The usefulness of binary words in crossed stick puzzle design comes from our ability to encode them in the types of slots used in a piece of a puzzle. For example, my decagram puzzle uses pieces with outer slots that could point down or up, and inner slots that always point up, but could be deep or shallow. We can assign 0 to down and 1 to up for the outer slots, and 0 to deep and 1 to shallow for the outer slots. Then, reading across the slots, we get a binary word corresponding to a given piece. For example, down-shallow-deep-up is 0101.

One benefit of using binary words is that we can enumerate the possible pieces in a puzzle by counting the binary words of a given length, (in this case four). But there is a snag: The piece we called 0101 can be flipped horizontally, after which it would read as 1010. It seems that rather than plain binary words, what we want are the equivalence classes of binary words formed by some symmetry action, in this case, reversing the word. Examining these gives us four symmetrical words that map to themselves upon flipping, and six pairs of words that flip to each other, for a total of ten classes of length four.

Instead of horizontal flipping, we could, if our slots are only using an up vs. down slot scheme, flip them vertically. In terms of the effect on the pieces, this will invert all of the 0′s to 1 and vice versa. This gives us eight pairs of words that flip to each other. We could also allow both horizontal and vertical flipping. In this case there are six classes of words of length four.

At this point, you might want a table with the number of binary words of each type. That way, when you come up with a crossed stick puzzle idea you can look at the table on the row with the number of slots in the pieces, and see if there’s an entry that gives you the number of pieces you’d like. Or you could go the other direction, and look at an entry in the table and try to come up with a good puzzle for that entry. (This is how I designed my Decagram puzzle.)

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

Let’s give it a try using the piece configuration from my last post:



Applying the table to this, there are 12 pieces with 4 intersections (and thus, slots) in that configuration. There are no entries of 12 in that row, so we’re going to have to get creative. There’s a 6 in the Inv. & Rev. column; we can make our (well, my) puzzle have two copies of each piece corresponding to one of those. The intersection points are conveniently symmetrical, which gives us reversibility, and if we use up/down slots, we get invertibility. So now we have a puzzle design.

Of course, there’s one step left, which is making sure that the puzzle can be solved. (Ideally, by a human being of reasonable intelligence devoting no more than a reasonable amount of time.) It is quite possible to develop a design for a puzzle of this type that can’t be solved.

For example, this star of David puzzle, using one set of the invertible & reversible 4 slot pieces, is unsolvable. To see why, look at the relevant binary words, and consider the first and last digits, corresponding to the slots at the six points of the star.

0000
0001
0010
0011
0101
0110

There are three 1′s in the external slots. Inverting a word may change that number by two, or keep it the same. Reversing a word will not change the number of 1′s. Therefore, the number of 1′s must always be odd. But since each intersection in a solved puzzle must have one up and one down slot, there must be exactly six 1′s in external slots in a solved puzzle. Thus, the puzzle is unsolvable. (However, if we had two copies of each piece, we could possibly make two stars of David by swapping pieces between the sets. This gives us a second challenge for the set above. It’s starting to look like a keeper!)

Stepping away from crossed stick puzzles, it turns out that all of the fun things that you can do with binary words can be done with these symmetry variants. And when I think of fun things you can do with binary words, I think of de Bruijn sequences and Gray Codes! But this post has gotten long enough already; that will have to wait for another post.

No comments »

Posted in Recreational Mathematics

Tags:

Crossed Stick Addendum

December 9th, 2012

Here’s another configuration of segments that could work in a crossed stick puzzle:

Conveniently, all of the pieces meet at 60° angles, so if I make a puzzle using this, I won’t need to use a slot design that admits multiple angles as in the one in the previous post.

A related configuration with three intersections per piece can be formed by clipping the outer points of this configuration. Are there any more crossed stick configurations that I’ve missed?

No comments »

Posted in Recreational Mathematics

Tags:

Crossed Stick Variations

December 6th, 2012

In a (somewhat) recent post, I discussed my decagram puzzle that I used for the gift exchange at Gathering for Gardner 10. Of course, I wondered what other puzzles of this type are out there waiting to be found. I’m particularly interested in mathematically elegant puzzles, which for me means ones that use combinatorially complete sets of pieces, that is, sets of pieces where every possible piece for a given scheme is actually present. Rob Stegmann has a page with a listing of similar puzzles, which he calls crossed stick puzzles.

In a crossed stick puzzle like my decagram puzzle, each piece has a number of slots, which are at the same position on every piece, and each slot can be one of a number (typically two) of types. This means that you can assign a code to every piece, which will be a binary string if there are two slot types.

Stegmann’s page also notes the possibility of different slot compatibility schemes: instead of 1 and 0 being compatible with each other and not with themselves, the opposite is possible, although it seems harder to realize physically. (Perhaps magnets might lend themselves to such a scheme.) With three or more slot types, more compatibility schemes become possible.

Thus there are essentially four attributes that describe a puzzle of this type. These are the configuration of pieces in the completed puzzle, the allowable actions that can be performed upon a piece in a given position, (rotation, flipping) the compatibility scheme, and the piece codes that are present.

What viable piece configurations exist? For our purposes, a legal puzzle configuration consists of a number of congruent pieces, which can be represented as line segments marked at their intersection points. Exactly two pieces must meet at each intersection point. (Relaxing that requirement may bear fruit, but it also complicates the physical design of slots in a puzzle.) If there are two intersection points per piece, the situation is not terribly interesting: the pieces must topologically form a loop, and there are an infinite number of ways they can do this. So I’ll restrict myself to configurations where the number of intersections per piece is three or greater.

As my decagram puzzle might suggest, one class of puzzle configurations consists of star polygons. Oskar van Deventer designed a heptagram puzzle, which uses flexible foam pieces to get around the assemblability problem I mentioned in the previous post. It not have a combinatorially complete set of pieces; making up for this, the flexible material does allow the pieces to form a number of different patterns.

Another class of crossed stick puzzle configuration consists of square grid patterns; most of the examples on Stegmann’s page are of this type. Few of them use complete sets of pieces, although “The Fence”, designed by Jean Claude Constantin, has a complete set from which the 1111 and 0000 piece have been removed.

In addition to grids and stars, we can make “broken stars”, where small segments are excised from the center of each of the pieces in a star configuration. Are other puzzle configurations possible?

As you can see, at least one is. In this configuration there are eight pieces. Taking a note from “The Fence”, I used all of the possible pieces except the two where all of the slots are of the same type. (As in the decagram puzzle, the pieces can be flipped horizontally, which means that there are ten different piece types possible before we exclude those two.)

A complicating aspect of this configuration is that intersections may occur at different angles depending on whether the piece is part of the outer square or the inner square. The slot shape I used allows the same slot position to work for both 45° and 90° angles. An unintended consequence of the design of this puzzle is that the pieces can also form an octagram.

I’d certainly be interested in hearing about other piece configurations that could be used in a crossed stick puzzle, if you can come up with any.

No comments »

Posted in Recreational Mathematics, Zapped Puzzles

Tags:

A Polyformist’s Toolkit: Symmetry Variations

May 25th, 2012

It lately occurred to me that there are concepts that I use (and see used by others) in creating variations on polyform puzzles that I haven’t seen explained very thoroughly, and it might be helpful if I used this space for just that purpose.

Some polyomino puzzles using symmetry variations

The first of these is the use of different kinds of symmetry in defining the set of pieces used in a puzzle. (I touched on this in my post on rectangular-cell pentominoes.) Normally, all combinations of rotations, translations, and reflections of a polyomino in a grid are considered to be equivalent. Leaving aside translations for the moment, the possible rotations and reflections of a polyomino are equivalent to the group of symmetries of a square. We can find variations on polyominoes by restricting the allowed symmetries to subgroups of that group. For example, the one-sided polyominoes are the result of allowing only rotations, not reflections. Rhombic cell pentominoes (which Kadon sells) allow 180° rotations, plus diagonal reflections. My Agincourt puzzle allows only reflections over vertical axes, assuming that the arrows are pointing vertically. Notice that it doesn’t matter which direction the arrows point as long as they point in the same direction; this suggests that what we are interested in isn’t symmetry subgroups per se, but classes of subgroups where two subgroups that are related to each other by symmetries of the square are equivalent.

What are all of the possible variations with different allowed transformations? We can generate a representative subgroup of every class by using some combination of reflection over a particular axis parallel to the grid, a particular diagonal axis, and 90° and 180° rotations. Here’s a chart of the symmetry variations this produces.

  Polyomino Type Reflection Rotation # of Symmetries
Free Either 90° 8
Parallel (a.k.a. Rectangular) y axis 180° 4
Diagonal (a.k.a. Rhombic) x=y 180° 4
One-sided None 90° 4
Oriented Parallel y axis None 2
Oriented Diagonal x=y None 2
Polar One-sided None 180° 2
Fixed None None 1

I chose the above terminology for the types (after keeping “free”, “one-sided”, and “fixed” as established terms) in order to build in some helpful mnemonics. The types with four symmetries have short names. The types with two symmetries have longer names based on the names of the types whose symmetry groups their symmetries are subgroups of. The odd duck here is “polar one-sided”, which is a subgroup of all of the larger symmetry groups, but putting “one-sided” in its name makes the types with two symmetries nicely echo the names of those with four.

Here’s a chart of the number of polyominoes of each type for a given size:

Polyomino Type 1 2 3 4 5 6 7 OEIS #
Free 1 1 2 5 12 35 108 A000105
Parallel 1 2 3 9 21 68 208 A056780
Diagonal 1 1 3 7 20 62 204 A056783
One-sided 1 1 2 7 18 60 196 A000988
Oriented Parallel 1 2 4 12 35 116 392 A151525
Oriented Diagonal 1 1 4 10 34 110 388 A182645
Polar One-sided 1 2 4 13 35 120 392 A151522
Fixed 1 2 6 19 63 216 760 A001168

(The odd entries for the polar one-sided polyominoes track those for the oriented parallel polyominoes exactly for several terms, before eventually diverging. There are 4998 9-ominoes for both, and 67792 polar one-sided, and 67791 oriented parallel 11-ominoes. It seems unlikely that this is a coincidence. Does anyone know why this occurs?)

These types can be realized geometrically by replacing square cells in a planar tiling with cells with the appropriate symmetry. Another way they can be realized is by keeping the cells square and marking them with a figure with the appropriate symmetry. This is essentially what I did by cutting arrow shaped holes in the Agincourt pieces. The latter method allows the possibility of mixing different symmetry types in the same tiling. I don’t believe I’ve seen such a problem before, so let me be the first to fill what may be a much needed gap:

Problem #28: Tile a 6×6 square with the oriented parallel, oriented diagonal, and polar one-sided trominoes. No tromino should touch another of the same type.

With these symmetry subgroup based polyform variations in mind, any type of polyform on a square grid can be transformed into an entire family of polyforms. In particular, polysticks would reward exploration in this light, which does not seem to have occurred yet. A similar analysis to the one above can be made for symmetry based variations of polyiamonds and polyhexes. Bringing translation symmetry subgroups into the picture leads to things like checkered polyominoes. I may get to these in later posts; this one was getting long enough that I needed to wrap it up.

I should note that Peter Esser’s pages on polyforms cover these variations, and that his polyomino solver program can work with any of the 8 symmetry types (but not with mixed types.) (It is, sadly, a Windows binary, but I’ve been able to make it work under Wine on Linux.)

2 comments »

Posted in Recreational Mathematics, Zapped Puzzles

Tags:

Binary System, Decimal Star

April 19th, 2012

If you participated in the gift exchange at the 10th Gathering for Gardner, which was held recently in Atlanta, you would have received one of these in your bag of exchange gifts:


It is common, (but by no means required) for participants to use the number of the conference as a theme in their exchange gift in some way. I considered a ten pointed star with pieces that slot together as a promising shape for a puzzle, and I recalled that there were ten distinct reversible binary sequences of length four. (In this scheme 0011 and 1100, for example, are considered equivalent because they reverse to each other.) This meant that with four slots at intersection points, if there were two possible positions for each slot, (like up and down) there would be exactly ten possible pieces, which would make an elegant puzzle set if I used one of each. Conveniently, the pieces could be flipped horizontally to physically realize the reversal of the string. Inconveniently, the pieces could also be flipped vertically, which would invert the 1′s and 0′s, and lower the number of distinct piece shapes to six. Another problem is that some configurations of pieces could not be physically assembled. If there was a triangle of pieces where each had an up slot followed by a down going around the triangle, there would be no way to fit the third piece in, because it would simultaneously need to be slotted in from above and below.

I solved both of these problems at once by changing the inner slots to all face the same direction, and to have shallow vs. deep as their two possible states instead of up and down. Now the ten pieces can be divided into two pentagonal configurations that are connected by their outer slots, and connect to each other by the inner slots. Because every triangle in the star contains the two inner slots of a piece, the triangles are all assemblable. The pentagons must also be assemblable, because there are only four pieces with up and down outer slots, so one side of the pentagon must have two slots pointing the same direction, and that side may be placed last. And because the direction of the inner slots is forced, only horizontal flipping is allowable. Here’s a photo of an assembled puzzle, along with an unassembled set of pieces:

Mathematical niftiness aside, is this a good puzzle? I think so. It has a fair number of solutions, but neither so many that you can easily stumble upon one without applying any strategy to solving the puzzle, nor so few that you have to spend a lot of time engaged in trial and error. Let me know if you have one of these and need hints for solving it.

In an upcoming post, I’ll discuss some variations on this type of puzzle.

No comments »

Posted in Recreational Mathematics, Zapped Puzzles

Tags:

Polyform Link Roundup

March 25th, 2012

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!

No comments »

Posted in Recreational Mathematics

Tags:

Polypennywise

February 26th, 2012

Here are the pentapennies and tetrapennies tiling a figure with 6-fold rotational symmetry:

For a while I’ve been trying to find a tiling of a figure with 5-fold symmetry using just the pentapennies. It feels like it should be doable, but I haven’t had any luck so far. Maybe you will? Call that problem #27. As with the polycircles in my last post, I decided to stack the deck in my favor by adding smaller pieces to the tiling set. This tiling contains 85 pennies: 65 from the 13 pentapennies and 20 from the five tetrapennies. With polypenny tilings you can either use a pattern with a penny in the center, or you can leave the center open. With a penny in the center, the remaining number of pennies is divisible by six. This is nice not only because we get a little more symmetry, but also because the configuration of six pennies around the central penny is strongly connected, which means that we have more flexibility in where the polypennies can go in that region.

Unfortunately, although seven is also a divisor of 84, seven pennies don’t fit around a central penny, so this is probably as good as we can do for symmetry. Although if we went to hyperbolic geometry, seven pennies could fit perfectly around a central penny after all. But, for now at least, I’ll save my pennies and not spend them irresponsibly at non-Euclidean exchange rates.

No comments »

Posted in Recreational Mathematics

Tags:

Polycircles

January 23rd, 2012

A while back, (before I started this blog) I was exploring polyforms using unit-radius circles as their base cell type, which I called “polypennies”. We can think of these as “flexible” polyforms: since connections between the circles can occur at arbitrary angles, we consider two polypennies to be equivalent if we can continuously move the circles around each other without changing which circles are adjacent. (As with other polyform types, rotations and reflections are also considered equivalent.)

The pentapennies

I called these polyforms “polypennies” rather than “polycircles” because “pennies” captured the equal size of the cells. (ETA: I forgot that I raided the word from the term “penny graph,” which has been used as an alternative to “unit coin graph” to describe the adjacency graph associated with a particular configuration of non-overlapping unit radius circles.) I also knew that eventually I would want to get to polyforms made of circles of arbitrary size, for which I was reserving the term “polycircle”. Well, it happens that I’ve been invited to Gathering for Gardner 10, where I plan to give a talk on flexible polyforms, so eventually is now.

For polycircles with cells of arbitrary size, another dimension of flexibility is required. Two polycircles are equivalent if they can be made congruent by continuously expanding or shrinking the circles without changing adjacencies, in addition to applying the transformations allowed with polypennies. This extra flexibility means that, in addition to the polycircles that are equivalent to polypennies, there are some polycircles that could only be formed by placing circles into spaces where they wouldn’t fit if all of the circles were forced to be the same size.

As with other flexible polyforms, elegant tiling puzzles for the polycircles can be produced by attempting to maximize the symmetry of the configuration to be tiled. Here’s an example, with fourfold rotational symmetry, of a tiling puzzle containing all of the polycircles of order 1 through 4:

This was not a hard puzzle to solve, once I came up with a configuration to tile that would work. Adding smaller pieces is a time-honored trick for making polyform puzzles easier; I put in the 1- through 3-circles because I was failing to make any headway with the 4-circles alone. The extra dimension of flexibility was helpful in that one can generally resize the circles to touch more neighbors than is possible in polypenny puzzles, which tend to end up with a number of cells with only two neighbors. On the other hand, the 4-circles with a circle inside the gap between three others in a triangle were trickier to deal with than any of the 4-circles that are equivalent to 4-pennies.

Can we do better than the above? I think fivefold symmetry may be possible.

Problem #26: Find and solve a tiling puzzle for the 1-, 2-, 3-, and 4-circles with fivefold rotational symmetry.

2 comments »

Posted in Recreational Mathematics

Tags:

Children of Julia Sets

August 23rd, 2011

Here’s a pretty specimen I found while playing with a bit of code I wrote to produce quadratic Julia sets:

If you know your Julia sets, you might be thinking something odd is going on here.

If you don’t, here’s a quick primer.

Pick a complex constant c. Then for every point z in the complex plane, create a sequence with the following recursive definition:

z0 = z
zn+1 = zn2 + c

This sequence will do one of two things. Either it will zip away from 0 and eventually go indefinitely far away, or it won’t. (It could converge to a single point, or alternate between a few points, or bounce around chaotically. It doesn’t matter.) The points where the sequence sticks around near zero form a quadratic Julia set. There are other kinds of Julia sets, defined using different formulas. But the kind of Julia set you will most commonly encounter is this one, and henceforward I will use the term Julia set to refer to this kind of Julia set.

Julia sets are fun to play with because they are fractals, with infinite levels of detail and self-similarity. Some Julia sets form a single connected blob:


Julia set for c = .3 + .2i

Other Julia sets form dusts, where any region that appears to be in the set is actually divided into separate disconnected regions, and these regions are themselves divided, ad infinitum:


Julia set for c = .7 + .33i

I should note that I’m cheating here slightly. A dust isn’t actually much to look at. Although it contains an infinite number of points, the probability of an individual point being in a dust-like Julia set is 0, so if I were plotting it properly, there would be nothing to see. What I’m actually plotting for each point is a level of grey on a scale from 0 to 255 (the latter being black) corresponding to the number of iterations it took for the sequence to escape beyond a given bound. The use of a grayscale gives dusts a more organic look, which I rather like.

Every Julia set is either a dust or a blob. The famous Mandelbrot set effectively catalogs this aspect of Julia sets. For every possible constant c, one checks only the behavior of 0 in the Julia set for that constant. If 0 escapes to infinity, we have a dust, otherwise we have a blob.  Near the boundary, the blob thins into increasingly narrow filaments, but it remains in a single connected piece until the boundary is crossed, and the blob shatters into a dust. The Mandelbrot set contains all of the constants that give “blob-like” Julia sets.


The Mandelbrot Set

Getting back to my first image in this post, you can now see why I said there was something odd about it. That fractal is not a single blob; there are many disconnected parts. But it also isn’t a dust; there are filled solid regions. So it can’t be a proper Julia set. But it does have a Julia set “feel” to its self-similarity. So what’s going on?

The answer is that instead of using a single constant at every step of iterating the sequences for each point, as one would for a proper Julia set, I alternated between two constants. In fact, the two constants I alternated between were precisely the constants for the blob and dust I showed above. Thus it is perhaps unsurprising that the “child” of a blob and a dust would show characteristics of each: those characteristics were in its “genes”.

Alternating between the two constants in the opposite order gives the following:

Looks like the same basic pattern as before, but with two big connected bits instead of one. Notice that in this one the center point (z=0) is outside the set, while for the other one it was inside the set. Since this is the point that would tell us if we had a blob or a dust in a normal Julia set, it feels appropriate that it can go either way depending on the order here.

Here’s the Python code that produced the last image: 

from PIL import Image
size = 400
im = Image.new("RGB", (size, size))
c = [.3 + .2j, -.70 + .33j] #j is i in python
for x in xrange(size):
    for y in xrange(size):
        z = x * (4.0 / size) - 2 + (y * (4.0 / size) - 2) * 1j 
        i = 0
        while abs(z) < 4 and i < 256:  
            z = z ** 2 + c[i % 2]
            i += 1
        im.putpixel((x,size-y-1), (255-i,255-i,255-i))

im.save("julia6.png")

No comments »

Posted in Recreational Mathematics

Tags:

HEY, A BOGUS 9

July 8th, 2011

Dave Harper’s Polyomino Patterns page has some good stuff, looking at patterns of connections between squares in polyominoes, and processes of “integration” and “differentiation” on polyominoes. He enumerates all the possible patterns of connections of the cells in a 2×3 rectangular hexomino that make a connected whole. (There are ten.) These could also be considered as polysticks that touch all six vertices in a 2×3 lattice. The polysticks on a 2×3 lattice are precisely those that can be represented on a 7-segment LED, hence my presentation of them below:

It might be nice to have some puzzle using these. So here is one! Fill in segments on the figure below so that each of the ten patterns above is represented on a 7-segment LED shaped subsection of the figure.

Reflections and rotations of the patterns are considered equivalent. There are 13 7-segment LED shaped subsections of the figure, so three of them either can have other patterns, or can be duplicates.

Are there any other puzzle grids that would make for a puzzle using these patterns that is as good or better than this one?

4 comments »

Posted in Recreational Mathematics

Tags:

Maximal Irreducible Contiguous Covers

April 28th, 2011

A cover of a set of polyforms is a shape (or set of shapes) into which each member of the set could fit. Mostly I’ve looked at problems involving minimizing the size of a cover. This problem goes the other direction.

A reducible cover is one where a cell can be removed and the remaining figure is still a cover. An interesting problem then is to find an irreducible cover in a single piece that is as large as possible. (Why a single piece? Well, without specifying that, the largest irreducible cover will simply be all of the shapes in the set in separate pieces.) Here’s a (conjectured) maximal irreducible contiguous cover (MICC) of the pentominoes:

The above solution has been on my polyomino cover page for a while. Here are a couple of new results, (still just conjectured since I found them by hand rather than exhaustive computer search, and I am not able as yet to prove they are maximal.)


An MICC (?) of the hexiamonds


An MICC (?) of the pentaedges (shown in two copies for clarity)

Between these solutions, we see some patterns emerging. Certain polyforms are in some sense distinctive: they have features that do not occur in other polyforms in the set. This makes it easy to make a large cover that includes exactly one copy of them. Other polyforms end up serving a connective function. For example, there are quite a few occurrences of the L pentomino in the first figure, so removing a cell will never make the cover cease to include an L. By using a few pentominoes as many times as possible in this connective function, more pentominoes are left over to occur singularly.  In some cases multiple polyforms that occur only once are forced to overlap, so we don’t get their full number of cells to add to the cover, but we do get a few. This is shown with the outlined hexiamonds above. In the case of the pentominoes, we have one cell where two T pentominoes overlap; since these are the only two T pentominoes in the figure, the cell can’t be removed from the cover.

Problem #25: Find maximal irriducible contiguous covers of anything and everything! This problem ought to yield interesting results for any kind of polyform you can throw at it.

One final note: It was slightly unfortunate that I chose the word “cover” to represent a concept in polyforms when it already had an unrelated meaning in graph theory; it’s even more problematic now that I’m using graphs themselves as polyforms. It appears that in graph theory, the appropriate term is “common supergraph”. I could use “common superform”, although one problem is that polyforms, unlike graphs, are generally not allowed to be disconnected, and for some problems (though not this one) we want sets of polyforms that aren’t connected to each other. Perhaps “common superformsets” in that case, as ugly as it sounds.

No comments »

Posted in Recreational Mathematics

Tags:

Pentaedges

April 10th, 2011

In graph theory, a graph is a set of vertices along with a set of edges that each connect exactly two different vertices. As a polyformist, it seems natural for me to ask, can we make interesting sets of polyforms out of them? We usually require polyforms to be connected, and we usually look at sets of all polyforms of size n, for some positive integer n. One obvious possibility would be to use sets of all connected graphs of n vertices. But these quickly grow to unwieldy numbers; additionally, they suffer from the problem that once n hits 5, some graphs are non-planar, or impossible to represent in a plane without crossings. This would restrict any search for elegant figures to use in tiling problems with them.

Alternatively, we could look at sets of connected graphs with n edges, which I will call polyedges. There are no non-planar n-edges until size 9. There are 12 pentaedges, the same as the number of pentominoes, and I hope to show that this is a versitile and interesting set of polyforms.


The 12 pentaedges

(The term polyedges is used in some sources to refer to what are more commonly referred to as polysticks, i. e. connected sets of segments in a (typically square) lattice. However, I have need of a term, and polyedge seems so clearly the right one that I feel justified in repurposing it.)

In making tiling problems for polyedges, we treat them like polysticks, allowing polyedges to meet at a vertex but not allowing edges to overlap between forms. Now, one important problem remains: what graphs should we use as patterns for them to tile? We are unconstrained by geometrical considerations, which in the case of polyominoes, for example, pull us toward making rectangles. But we can still use symmetry. Not only are highly symmetrical graphs particularly elegant, but symmetry can narrow the space of solutions; since polyedges are very flexible, this is probably desirable. It will help that the total number of edges in the set is 60, a number with many factors, which should help in our search for symmetrical patterns.

Here are the pentaedges tiling 4 copies of K6, the complete graph (all vertices are connected) with 6 vertices:

This pattern has a truly dizzying amount of symmetry. Every permutation of the vertices in a complete graph maps the graph to itself. There are 6! = 720 such mappings (or automorphisms) for each K6. Since we can permute all four copies independently, on top of which we can arbitrarily reorder the copies themselves, the full pattern has 7204 · 4! = 6,449,725,440,000 automorphisms.

On the other hand, it’s non-planar, and we might want to tile some planar patterns. One highly symmetrical planar pattern with 60 edges is a pair of icosahedra. I show them squished onto a plane for clarity below, but as graphs they’re still equivalent to the 20-sided dice that role-playing gamers use.

Notice that I used 6 colors to distinguish the pentaedges in the figure above. In fact, I had to, since each of the pentaedges touches each of the others within each icosahedron. We could instead try to minimize the number of colors required.

Problem #22: Tile a pair of icosahedra with the pentaedges using only 3 colors, with no two pentaedges of the same color meeting at a point. (It may help to know that there must be 11 vertices where the degrees of the vertex for each adjoining pentaedge are 2, 2, and 1, 7 where they are 3, 1, and 1, and 3 where they are 3 and 2. This can be obtained by counting the total number of vertices of each type in the 12 pentaedges and setting up a system of equations; I won’t get into the details here, but I’ll put them in a comment.)

The pattern above has 28,800 automorphisms. It’s not the most symmetrical planar pattern possible. A set of 4 pentagonal dipyramids has 3,840,000 automorphisms. After finding the other tilings in this post, I got lazy wanted to let others join in the fun, so I’m leaving the problem to you:

Problem #23: Tile a set of 4 pentagonal dipyramids with the 12 pentaedges.

With polysticks, we often like to forbid solutions from containing points where two polysticks cross. We can do the same with polyedges, if we set up the pattern properly:

Notice the trick I played with the pentagonal (or 5-cycle) pentaedge at the bottom of the figure, putting the 5-star pentaedge inside it. In the previous problem, we couldn’t tile the icosahedra without any crossings, because one pentaedge contains a 4-cycle, which can only be placed on an icosahedron with an edge connecting two opposite corners, and the pentaedge containing this edge must cross the 4-cycle. Can we find a pattern where the pentaedges containing 4- and 5-cycles can both enclose one or more other pentaedges, so that the pattern contains only triangular faces and can still be tiled without crossings? Here’s a candidate that can be inscribed on a cube; in this case it seems clearer to show the cube in an unfolded state than to squish it as we did with the icosahedra.

Problem #24: Tile the above figure with the pentaedges. (Keep in mind that in the unfolded version, the edges that fold together count as a single edge. The pentaedges that are already placed are just for illustration, and can be placed differently in a solution.)

To make it a bit easier to communicate solutions or new problems you find, I’m providing source svgs (made in Inkscape) for some of the images above. They contain copies of the relevant patterns in plain black, which can be turned into a solution by recoloring the edges.

Problem #22 (Icosahedra)
Hexagonal figure
Problem #24 (Cube with triangles)

This post expands on material at my non-blog. Theoretically, I’m using this blog to write more exploratory material in the service of the non-blog, where I intend to collect it in a more digested form. However, lately I’ve been more poaching the non-blog for material to use here, and I haven’t gotten around to updating the non-blog as I mean to. Nevertheless, if you like what you’ve been seeing here, you should check it out, as it contains most of my polyform discoveries from the ’00s.

6 comments »

Posted in Recreational Mathematics

Tags: