Tag: symmetry

The Pentominoes My Destination

~ munizao ~ Leave a comment

Usually, the pentominoes are the raw material of a problem, not its end point. Here are a couple of puzzles that turn the usual order on its head.

I.

With Gathering for Gardner 12 approaching in 2016, I was looking for things to do with the pentomino theme. (I’ve posted previously about my pentomino coloring talk and what led from it.) I had come up with a puzzle with 12 separate frames, each with space for a pentomino, and two sets of 12 puzzle pieces. Each set was in a different color, and the object of the puzzle was to fill all of the frames with two pieces of the same color. I made a copy out of lasercut wood, and brought it to the Gathering.

At the Gathering’s offsite “garden party” I commandeered a table a little bit away from the main crowd. (I have auditory sensitivity issues that become a problem in loud, crowded spaces.) I set out the pieces and frames, and hoped I would get some takers. I was incredibly lucky that one of them was none other than Richard K. Guy! I tended to be shy at these conferences about approaching the “old guard” who knew Martin Gardner as a peer. We have lost many of them, including Guy, John Horton Conway, Raymond Smullyan, and Solomon Golomb, in the years since this picture was taken. This was my only substantial interaction with Guy, and I’m very thankful to have the memory.

I discovered that a puzzle with multiple frames had very interesting effects on the collaborative dynamics of group solving. Everyone could pick a frame to work on separately, so there was no confusion as to which parts were “owned” by whom. Unused frames and pieces could be picked up by anyone without fear of stepping on anyone’s toes. Sometimes a player would require a piece that was already used in a different frame, and they would ask its owner for it. Everyone was working toward the same final goal, so they would always be willing to share. I saw the same patterns when three different groups worked on the puzzle that day, and I believe that the delineation of responsibilities that emerged from the multiple frames helped all of the players feel ownership of an important role in solving the puzzle.

Here is the set of pieces. The size of each piece is 2½ unit squares. I wanted to have two copies of six different pieces, but that didn’t work, so there are two singletons per set.

Although the puzzle as designed requires two pieces from the same set in each frame, an obvious alternate puzzle would be to have each frame use one piece of each set. I haven’t tried it though, so I don’t know if that challenge is a good puzzle, or even solvable.

II.

I’ve recently been looking for light puzzles with small piece sets that might make good exchange gifts for Gathering for Gardner. Taking the 1½- and 2½-ominoes and giving them every possible choice for marking any of the (full) cells with a square yields 6 pieces, with 5 squares, and an area of 13. Well, 5 squares means I’m going to have to do something with pentominoes. And an area of 13… well, that’s just awkward. But I was inspired by Tick Wang’s Tans Dance, along with other puzzles I saw on the Nothing Yet Designs site where the goal is not to make a particular shape, but to make any symmetrical shape.

And that’s the puzzle. Take these pieces and make a symmetrical shape (either rotation or reflection symmetry is fine) where the blue squares form a pentomino. Now do it again for the other 11 pentominoes. All of them are solvable! Most of them, individually, are not too hard, but with 12 challenges, it should keep someone busy for a few minutes.

What I like about this puzzle is that the symmetry goal makes the squareless pieces relevant, and including the squareless pieces makes the pieces a more complete and elegant set. Will it be my exchange gift for the next G4G? I think it’s too early to say yet. I try to pick an idea at about six months prior to the conference. This tends to give me a timeline where I have plenty of time for design, prototyping, ordering materials, and assembly, with some cushion if my first idea doesn’t pan out. I’ll still be on the lookout for more good light puzzles. After all, having lots of ideas to choose from for one’s exchange gift is the best way to ensure you find a really good one!

(A final aside: you might notice that there are two ways to make a half-omino. You can cut parallel to the grid, as I did for both of these puzzles, or you can cut a square diagonally. For the first puzzle, diagonal cuts were out, because the T pentomino cannot then be split into two 2½-ominoes. For the second puzzle, I considered diagonal cuts first. That version of the puzzle does actually also work, but often, you get to a point where you have the puzzle basically solved, but you have to do some fiddly piece flipping so that the right triangle ends give a symmetric figure.)

Overlay Dice

~ munizao ~ Leave a comment

After the Monomatch dice, I was on the hunt for more ways to make a pair of dice that produce the same distribution as taking the sum of two standard dice. I considered using bitwise binary operations, and then tritwise ternary ops, without success. I also tried putting different operations on one die, and then two operands on the faces of the other die. Again, no luck. Then, considering pipped dice, a thought popped into my head: “Try pipwise operations!”

What would that even mean? Well, we could consider each possible position for a pip to be a locus where a binary operation could be performed, with a pip meaning one, and the absence of a pip meaning zero. After performing the operation on all of the positions, we will simply count the ones in the results, just like we count pips in a normal die roll. As for the choice of operation, OR seemed the most natural, as it would be equivalent to just mentally overlaying the faces of the two dice. With a little trial and error, I found this pair of dice:

Notice that the pip positions are based on an underlying 3×5 grid, and that all of the faces have 180° rotational symmetry. The symmetry makes it easier to align a pair of faces so that they are in the correct position to be overlaid. In order for odd rolls to be achievable, both dimensions of the underlying grid must be odd. (Otherwise, there would be no center pip position that maps to itself by rotation, and pips could only occur in pairs.) The number of pip positions must be at least 12 in order to accommodate the highest roll. Under these constraints, 3×5 is the smallest set of dimensions that gives a workable set of pip positions. Another good set of pip positions uses a grid aligned at a 45° diagonal from the edges of the faces, which allows the minimum number of 13 pip positions to be achieved:

It is not hard to come up with a set of faces using this set of pip positions that works.

Another constraint I set myself was that, as much as possible, I wanted to use pip patterns that looked like the familiar ones. There is a danger here that I did not immediately recognize. When I showed the above diagram on Twitter, someone asked, “What happens if you roll a 2 and a 3? Is that 3 or 5?”

My answer, “Yes, depending on which 3 you roll,” was not sufficient. To this person, the different 3’s were obviously the same, because they would be on standard dice. He had difficulty seeing that a 3 oriented as ╱ 90° didn’t just give a pattern equivalent to a 3 oriented as ╲. The problem seems to be that normally when you see a ⚂, you don’t think about the three pips, but immediately jump to the number, for which ⚂ is just an abstract representation, as much as the numeral 3 is. But here a ⚂ is not just a 3! Here’s the full table of results:

You can count the number of faces for each number of pips in the result to verify that it does indeed give the same distribution as 2d6: one 2, two 3’s, three 4’s, and so on.

In related news, I recently received the laser engraver that I backed a Kickstarter campaign for a year ago, so I plan to make some of the dice designs that I’ve written about, as soon as it gets warm enough that I can operate it outside. Meanwhile, I’ve been assembling shaker dice to sell at Gathering for Gardner 14, which will be this April if it doesn’t get postponed due to Covid for a fourth time.

A Pocketful of Pentapennies

~ munizao ~ Leave a comment

We can think of two connected unit coin configurations (or polypennies) as being equivalent if we can transform one into the other by reflection and/or sliding coins without changing which coins are adjacent. (Coins may not overlap.)

There are 13 pentapennies. A tiling with fivefold rotational symmetry may be possible, but I haven’t been able to find one. (This is problem #27.) However, I recently found a way to tile a figure with fourfold rotational symmetry with them:

Since I’ve had trouble with five symmetries, you’d think ten would be out of the question. But I found a repeating pattern on the plane with ten symmetries that can be tiled with the pentapennies:

Notice that there are five translation symmetries. Reflecting the pattern on a vertical axis gives five more symmetries. This pattern uses the wallpaper group cm. (Conway orbifold symbol: *×) We could also try to find a tilable pattern with the same amount of symmetry using the wallpaper group p2. (Conway orbifold symbol: 2222)

Problem #45: Find a tiling of the pentapennies on a repeating pattern on the plane that has at least as many symmetries as the one above, but a different wallpaper group. I don’t think going above 10 symmetries is possible, but I’d love to be surprised.

Stop! In the name of Octagons!

~ munizao ~ Leave a comment

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

~ munizao ~ Leave a comment

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

More Fun with Binary Words: De Bruijn Sequences

~ munizao ~ 2 Comments

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

Symmetry Variations on Binary Words

~ munizao ~ Leave a comment

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.

A Polyformist’s Toolkit: Symmetry Variations

~ munizao ~ 3 Comments

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

Polypennywise

~ munizao ~ Leave a comment

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.