Last month we discussed the famous Sleeping Beauty puzzle, which is notorious for producing two entrenched camps that both claim to have the right answer and argue endlessly about which is right. So this month we explore a puzzle whose answer, once you find it, is elegant and completely convincing.

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?

Paul Clarke, a high school student from Ireland, wondered if this problem could be generalized to shapes other than triangles, while retaining the property of being guaranteed to be lucky for some. Paul, who now studies at the University of Cambridge, found that some shapes do not work and some are too complicated. However, some do work if the internal lines are drawn correctly (if there are a correct number of internal lines). Below is one shape Paul found that can be made to work.

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

kinternal lines parallel to each side? (The figure shown has four.)

We encourage readers to try other shapes and see if you can come up with interesting results. For example, can you show that a square with *k* internal lines parallel to each side doesn’t work? You could end up without any winners.

Happy puzzling, and may the insight be with you.

P.S. A few months ago, in the column How to Create Art With Mathematics, we had readers generate beautiful symmetrical patterns based on examples given by author Frank Farris in his book on creating symmetry. Dr. Farris sent me an animated image that he generated by starting with a pentagram with frequencies 2 and -3, and adding in a term with a coefficient of 17 (-17 is one more than a multiple of 6) and an animation parameter. The resulting animation is shown below. I’ve included it here for your entertainment because it does have geometrical figures and dancing, though it is not otherwise related to this month’s problems.

*Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a *Quanta Magazine* T-shirt. ( Update: The solution is now available here.) And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION” (it will not appear online, so solutions to the puzzle above should be submitted separately). *

*Note that we will hold comments for the first day to allow for independent contributions.*

Both questions are about parity:

(1) For each line sung, people could only move from a triangular cell pointing up (denoted by U) to one pointing down (denoted by D), and vice versa. Suppose there are (k-1) internal lines parallel to each side, i.e., a total of k^2 cells, with k(k+1)/2 of U's and k(k-1)/2 of D's. After 13 (odd number of) lines, guests originally in U's winds up in D's and vice versa. So there are at least k(k+1)/2 – k(k-1)/2 = k empty U's, while it's easy to construct an example with all D's occupied. Therefore the minimum number of winners is k, where k=8 in our case and the answer is 8;

(2) Similar to (1), but U corresponds to a triangular cell (no matter whether it's pointing up or down) and D corresponds to a hexangular cell. 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 winners is abs(3m(m+1)-1), where abs is used to cover the case of k=m=0. For k=4, m=2 and the answer is 17.

By the same principle, the disparity for some solids (alien civilisations on planets, rather than dancers in a room?): octahedron=0, cuboctahedron=2, rhombicuboctahedron=2, icosidodecahedron=8, rhombicosidodecahedron=2, if I counted correctly.

Answer to Question 1:

At a minimum, there will be 8 vacant triangles, so the club will have to give 16 free drinks.

Explanation:

There are only a certain number of triangles that any particular dancer can end up in after 13 lines of song. In particular, a dancer can only end up in a triangle that is an odd number of triangles away from his or her starting position.

For this reason, the dancer in the lower left hand corner has only 28 potential end destinations (it is easier to count if you convert the diagram into a graph where each vertex represents a triangle and each edge represents a shared edge between two triangles).

These 28 potential end destinations are also the potential end destinations of any dancer whose starting position is adjacent to any of the end destinations. This consists of the rest of the 64 triangles, so in total there are 36 dancers each of whom share the same 28 potential end destinations [1].

Likewise, we can consider each of the 28 dancers who started the event at any of the 28 potential end destinations mentioned above. Their potential end destinations are the triangles which served as the starting positions for the 36 dancers mentioned above. Thus, there are 28 dancers who share the same 36 potential end destinations [2].

Either [1] or [2] can be used to solve the problem. For [1], since there are 36 dancers with 28 potential end destinations, there must be at a minimum 8 end destinations that have more than one dancer. Since there is one triangle for each dancer, that would leave 8 triangles vacant.

For [2], since there are 28 dancers who share the same 36 potential end destinations, and no other dancer has any of these 36 potential end destinations, then 8 potential end destinations must be vacant.

Wiley, thanks for pointing out the issue of parity. For (1), then, another way is to say empty cells can be minimized if everyone ends up above (for "down cells") or below (for "up cells") where he started. The last row of up cells don't have cells below, so the minimum will always be the square root of the cell total (i.e. sum of consecutive n odds is n^2).

For (2), I wonder if we lift Wiley's restriction that k must be even. If k is odd, you only get triangles which seems allowed based on the question. In any case the minimum would be zero since you'd have concentric hexagonal paths around which dancers can travel, never needing to leave a cell empty.

I quote Wiley for the very precise answer to the two puzzle questions. In general, though, simple parity arguments are not enough. This dancing floor for instance has as many white as black cells:

https://twitter.com/us_ius2/status/699280308877840384

(sorry to link a tweet of mine, I came up with no other way to post an image)

but (at least) two of the four corner cells will be empty after the first line.

I could not find such an example for a triangular dance floor (with #black cells = #white cells but with no forced winners for some odd number of moves). Maybe this is impossible on a symplectic dance floor? Any idea how to prove this?

For a square with k internal lines parallel to each side, if k is odd then the number of cells is (k+1)^2, which is even. The parity argument doesn't work in this case. The dancers could just walk around in a circle in the "ring" of the square they are in. In that circumstance every cell is filled after every step.

James M., what do you mean by the parity argument doesn't work in this case? If k is odd then the number of squares is even, and (if you color the dance floor like a chessboard) the number of light squares is equal to the number of even squares. The argument in Wiley's answer says (proves…) that minimal number of winners after an odd number of rounds equals abs(#light cells – #dark cells) = 0, which is the correct answer (in more general settings *equals* has to be substituted by *equals at least* – because "while it's easy to construct an example with all D's occupied" from Wiley's comment is not true in general).

Gregorio,

Here are some thoughts of your problem (I don't have a solution):

Consider the dual graph, i.e., each triangular cell represents a vertex; two vertices are connected only if the two corresponding triangles share one same edge. The setup is that:

(a) there are even total number of vertices;

(b) the graph admits a two-coloring;

(c) there are three vertices with degree of 1, for the rest, either 2 or 3.

(a) and (b) imply that this is a balanced bipartite graph. If only one line of the song is played, the situation of no-winner is equivalent to the problem of finding a perfect matching. I believe Hall's theorem is relevant here, which basically states that every set of vertices that belong to either partition needs to have enough adjacent vertices (the necessity is a simple counting argument but it's nontrivial to see why this would be the only obstruction to a perfect matching).

With the theorem, it's fairly straightforward to construct such a graph satisfying (c), but the difficulty seems to be how to check whether it's isomorphic to a tiling of a triangle…

One can easily extend this to general graphs that correspond to different planar tilings, replacing (c) with other constraints due to various cell shapes; or (b) doesn't need to hold, for which one might need to take a look at Tutte theorem. (Note playing more odd number of lines is essentially adding more edges to the graph, which facilitates a perfect matching)

The parity argument works for a square with an even number of lines parallel to each side. This produces an odd number of rectangles. If the rectangles formed in this way are colored black and white in a chessboard pattern, then the numbers of black and white squares differ by one (say a white one), and Riley's argument produces one as the minimum number of lucky winners.

It is clear that dancers starting on a down-pointing triangle are at a disadvantage in the game of question 1. How could they improve their chances of winning? Since a dancer on a D triangle ends up on a U triangle, there is no move she can make that affects her outcome. She could, however, negotiate with the dancers on neighboring triangles, offering not to end on their originally assigned triangles, if they promise the same to her.

The parity argument also works with the rhombitrihexagonal tiling (https://en.wikipedia.org/wiki/Rhombitrihexagonal_tiling). The ratio of hexagons, triangles and squares in this tiling is 1:2:3. Since hexagons and triangles are bordered only by squares, each dancer with visit a square every other move. Consider a single hexagon in this tiling, surrounded by 6 triangles and 6 squares. This results in 7 hexagons+triangles and 6 squares. If an adjacent hexagon is added and its surrounding ring of triangles and squares is completed, parity remains unchanged. So every pattern of this type will result in a minimum of one lucky winner.

@Gregorio Ortelli,

Thank you for the interesting pattern you posted. I've reproduced it here:

As you mentioned, two of the four corner cells will be empty after the first line.

The following may not be exactly what you are looking for, or maybe you are looking for tilings with more constraints, but here's a triangle with 5 white and 5 black cells that has the same property.

One of the two cells on the two white cells on the left will also be empty after the first line.

It seems to me that once we abandon the constraint of internal equally spaced parallel lines, there are lots of possibilities.

Cheers!

P.S. ( 4:57 pm) After posting this, I realized that the constraint I missed was “no forced winner for some odd number of moves.” No, this tiling does not satisfy that. So your challenge is still open.

Correction:

The triangle tiling I posted last time does satisfy the condition “no forced winner for some odd number of moves” just as Gregorio's does. The black and white halves of the diamond shape can exchange 3 people in every round after the first and then repopulate the three surrounding cells on the last round.

So the only difference between Gregorio's pattern and the triangle pattern is that the former is symmetrical, while the latter is not.

Incidentally I have since found a counter-example as below. Note although this is not explicitly stated by Gregorio, I have always assumed that the configuration needs to be a triangulation, which requires the cells to meet edge-to-edge and vertex-to-vertex.

[img]http://i.imgur.com/mbl6hQy.png?1[/img]

@Pradeep: this is quite an ingenious construction, but what I was trying to solve was the problem with the additional constraint described by Wiley (the configuration needs to be a triangulation). But I am not knowledgeable in graph theory / this kind of stuff and the formulation I had in mind was a lot more cumbersome (you have to cut the triangle only with straight lines – not half-lines).

@Wiley: nice and actually simple (it always looks easy when you see it :)). Also thx for the reference to Hall's theorem, which I did not know and is quite interesting.

Now the challenge is to extend the construction to a dancefloor with:

i) #dark squares = #light squares

ii) forces winners after 13 rounds

@Gregorio,

Your goal to extend these kinds of constructions to 13 rounds is ambitious. I conjecture that all such constructions will only have forced winners for round 1 and no other round, and this may be provable.

Informally I think that something like the "diamond shape" with adjacent dark/light triangles that are surrounded by three triangles of the opposite colors, seen in mine and Wiley's tilings seem to be necessary to force first round winners in a triangulation with equal dark and light cells. As I pointed out last time, this configuration allows the two adjacent triangles to exchange three people indefinitely for every round after round 1, and repopulate the surrounding triangles including each other in the final round. So forced winners after round 1 are not possible.

I'd love to proved wrong 🙂

How about two large (finely-subdivided) triangles of opposite colouring, "pointing" at each other, connected by a sufficiently-long line of triangles. So a kind of dumbbell shape. I'll post a picture later if that description made no sense.

@Pradeep: the proposal for the challenge extension was actually done tongue in cheek :).

For a triangular dancefloor -and this is in fact what we were talking about- I think you are right in conjecturing this to be impossible. For more complicated shaper, however, this should be possible, see

[img]http://i.imgur.com/edUWDrK.jpg[/img]

where the obstruction survives for 3 rounds. By adding more and more branchings one should in the end get a shape where the obstruction survives 13 rounds.

@Gregorio,

Very nice! I guess it's my turn to say, "Ingenious construction!"

I am speculating that the intuition behind "no such solution exists for a triangle with 3 or more odd number of rounds" is that there are only 3 corners that could be arranged to have degree of 1, i.e., only adjacent to one other cell. However, I did manage to find a counter-example for 3 rounds as below.

I have broken the graph into two parts so it's easier to visualize. We only need the bottom part of the configuration to prove that there exists forced winner after 3 rounds.

[img]http://i.imgur.com/mpWGXeM.png[/img]

[img]http://i.imgur.com/NxaxZ7H.png[/img]

Part (2) is the configuration when you zoom in the green triangle of part (1). There are two more white cells than black cells in (2), while it's contrary in (1). Note the configuration within the rhombus (surrounded by dotted lines) in (2) is isomorphic to the bottom half of (1).

To complete the proof, we only need (1) by noting that the bottom 5 black triangles can only be reached by the 4 white cells in (1) after 3 steps (i.e., Hall's theorem).

I don't know if there exists simpler configuration for 3 steps and whether this could be generalized to more rounds.

@Wiley

Congratulations! Very nicely done. Is 3 the limit? Or can it go further? It'll be interesting to find out…

@Wiley and Gregorio,

I am very happy to see my conjecture proved false. It seems to me that it might be straightforward to extend Wiley's ingenious model to extend the limit of rounds for forced winners indefinitely. So it seems that the "holy grail" we set ourselves of finding a nil parity triangulation having a forced winner after 13 rounds is within reach.

Wiley's construction has three elements:

1. At the base, a region with an excess of cells of one type relative to the other. By extending the number of rows, this imbalance can be increased to any number.

2. Near the vertex there is a mirror image of the base, that restores the parity imbalance.

3. Between the two is a "tunnel" or "bottleneck" that only allows dancers to percolate slowly from one imbalanced region to the other. The length of this tunnel can be made as long as needed to allow equality to be achieved only after the desired number of rounds.

Perhaps this is the kind of structure that eJ was referring to in his post.

I don't know if such a result is described somewhere in the graph theory or recreational mathematics literature. If not, Wiley, if you would like to work up this result, I'd be honored to set up a collaboration email group. Maybe Gregorio and others might be interested in joining as well 🙂

Believe I have found enough components to generalize the pattern to all odd number of rounds. Here is an illustration for 5 rounds, which hopefully sketches as well the proof by induction.

[img]http://i.imgur.com/FycLY0u.png[/img]

From n=3 to n=5:

Part (1) is straightforward (top row):

Insert one more row in the bottom orange trapezoid and one more row between the orange and green. The existence of a forced winner is established by considering the bottom 9 black triangles, which can only be reached by the 8 white ones after 5 steps.

Part (2) needs two components (bottom row left):

The orange rhombus is isomorphic to the orange trapezoid of part (1), except the color inversion which balances the number of white cells vs black ones;

The blue-shaded triangle is the hairy part, for which one needs a color-balanced triangulation with 3 black triangles on the bottom edge. The configuration I found requires two-step induction: Bottom row center is the case for n=5, which shows how one grows from 1 black triangle on the bottom edge to 3; Bottom row right is the case for n=7 and from 2 to 4.

If you use the logic above to construct the n=1 case, it yields a 10-cell configuration which has more cells than the 8-cell one in my previous post. This means potentially one might be able to simplify the construction above.

> Perhaps this is the kind of structure that eJ was referring to in his post.

Yes, here's the "dumbbell" I described back then: http://i.imgur.com/QC1bGHC.png

@Wiley

I think there may be a problem with the generalization that you described in your last post.

The blue-shaded triangle that you have shown in detail for the n=5 and n=7 cases shares an edge with a dark triangle, and therefore at least one of its two sides needs to an entire edge of a light triangle.

Here is a simpler way to achieve color-balanced triangulations for the two cases, if I have done the triangulation correctly.

Image link

The formula for the number of triangles for forced winners for rounds >1 seems to be (

n^2+10n+9)/2 which correctly gives 24 for 3 rounds and 42 for 5 rounds. This formula over-estimates the n=1 case as 10, but that may be because the triangulation is easier in this case — the blue triangle is essentially unnecessary.For n=13, we would need 154 triangles.

Pradeep,

Yeah, messed up with the additional constraint. Thanks for the correction.

No matter whether it is surprising that such a solution exists, I am glad there is a logical way to construct these configurations rather than brute-force search.

@Gregorio Ortelli,

This is a special gift for you, the person who first dared to imagine it: A triangulation of a triangular dance floor with 154 cells (77 light and 77 dark) that has a forced winner after 13 rounds (based on the method developed by Wiley, with my modification).

Image link

The base part of the triangle (up to and including the dark cell pointed out at right) has 8 rows of dark (36 cells) and 7 rows of light cells (28). At the vertex of the triangle is a color-reversed isomorphic mirror image of this with 36 light and 28 dark triangles. In between is a color-balanced region of 13 pairs of alternating light and dark cells (26) giving a total of 64+64+26=154 cells, as predicted by the formula (n^2+10n+9)/2 where n is the upper limit of all odd rounds with forced winners.