Solution: ‘The Problem With Dancing Shapes’

This month’s Insights column featured two puzzles that, at first sight, may seem impossible to the uninitiated. You have to figure out how many cells are guaranteed to be empty on complicated geometrical dance floors having many cells, after what seems like an arbitrary number of rounds in which dancers are free to move from one cell to another each round. The magic ingredient that makes the answers possible is the concept of “parity.” Parity, in general terms, means a property that allows every entity out of a potentially large or even infinite collection to be assigned to one of two separate categories, such as odd or even, light or dark, up or down. Where it can be applied, parity sometimes enables you to make quick, almost “magical” predictions about the properties of solutions of highly complicated problems without actually solving them — even if the solution is highly elusive or impossible to find. Once you know how to apply it, parity-based solutions seem obvious, even trivial. A simple example from elementary arithmetic is the prediction that the product of 56738545 and 389509743 is an odd number. It’s simple, once you think of it. No wonder that parity-based problems are a staple of famous board-based puzzles, including the famous 15-puzzle and peg solitaire, knight’s-move puzzles, and even such things as exotic as imaginary chameleons of three different sexes!

To simplify this month’s Insights problems, all we have to do is find an appropriate way of coloring the shapes shown and voila! It’s literally child’s play.

Question 1:

A dance club has set up a social mixer on a “Lucky for Some!” singles night that is designed to overcome shyness and allow people to find someone interesting. On the dance floor they have marked a giant triangle that has been divided into 64 internal triangular cells as shown in the figure. At the start of the dance, 64 ticket holders are each randomly assigned a cell. Then the emcee plays a popular song whose lyrics are 13 lines long. While a line is being sung, participants have to dance in the cell that they find themselves in. At the end of each line, a drumbeat signals that each dancer must move across one of the lines bordering the cell into an adjacent cell. At the end of the song, the lucky dancers whose originally assigned cells are now empty can choose any partner, and the couple is given drinks on the house. (Thirteen, it appears, can be lucky for some!)

What is the minimum number of winners — the dancers for whom the club will have to buy drinks — if the dancers follow the instructions correctly?

In order to find the right coloring, you have to ensure that there are no neighboring cells of the same color. As you can see, this can be achieved by coloring all the upward pointing triangles light and those pointing downward dark. At the end of each of the song’s 13 lines, every dancer has to switch parity, going from a dark-colored cell to a light-colored cell and vice-versa. After an odd number of rounds, all the dancers that started on light cells will have to be on dark cells, no matter what adjacent cells they chose each time they switched. The number 13 is a red herring here — it could have been any odd number. There are 36 light cells and 28 dark cells, so after every odd round, and therefore at the end of the song, at least 8 light cells have to be empty. Since each of the dancers whose original cells were empty could possibly choose another from this group to have drinks with, the minimum number of winners is 8.

Question 2:

Imagine the same scenario as in question 1, but now the dance floor is marked with a hexagon, as shown. The internal cells may be hexagons or triangles, but the rules of the dance are exactly the same as before: Dance in your cell until you hear the drumbeat, at which time you cross over a line into an adjacent cell.

Again, what is the minimum number of dancers for whom the club will have to spring for drinks at the end of the song, if the dancers follow the instructions correctly? Can you find a general formula for any hexagon having k internal lines parallel to each side?  (The figure shown has four.)

For Question 2 also, the key is to find the right coloring. As shown, the hexagons can be colored light, and the triangles dark. Since there are 19 hexagons and 36 triangles, at the end of the song, at least 17 triangles will be empty. For this problem there was a slight twist in the tail — the kind of twist that math teachers add in order to see which students are really attentive to detail. Since 17 is an odd number, at least one of the partners chosen by the dancers whose original cells are empty has to be someone outside this group. So the club will have to spring for drinks for at least 18 dancers.

For this problem, we also asked: Can you find a general formula for any hexagon having k internal lines parallel to each side?

Here’s the answer from Wiley (slightly simplified):

When there are k internal lines (k must be even), denote m = k/2; there are 6m(m+1) triangles and 3m(m+1)+1 hexagons. The minimum number of empty cells is 3m(m+1)-1.

The concept of parity can be extended and applied to colorings of tiled surfaces of all kinds and Quanta readers considered several such interesting problems: eJ explored the spherical tiling of beautiful, soccer ball-like three-dimensional objects such as icosidodecahedrons; Tom Nichols examined the equally pretty three-colored rhombitrihexagonal tiling; and Gregorio Ortelli asked whether there can be dance floors that have an equal number of light and dark cells but can still force a winner after an odd number of rounds, for which he and Wiley provided elegant examples. Thank you all for the interesting discussions. The Quanta T-shirt for this month goes to Wiley for his solutions and deep insights in this field.

See you next month!