Category: Mathy Stuff
Cheryl’s Birthday: The math question from Singapore
Since a math olympiad question from Singapore went viral a few days ago, there have been lots of explanations cropping up all over the net. I thought I’d chime in with a restatement of the scenario in which the participants, Albert and Bernard, think out loud as they arrive at the answer. Here goes.
Albert and Bernard ask their friend Cheryl when her birthday is. An onlooker observes the interaction.
Cheryl says, “I’m not going to tell you exactly when my birthday is, but I’ll give you all a clue. It’s one of these ten days:
May 15, May 16, May 19
June 17, June 18
July 14, July 16
August 14, August 15, August 17
Now let’s see if you can narrow it down.”
Albert and Bernard realize they have no way of deciding between the ten options, so they ask for another clue. Cheryl says, “OK, I’m going to whisper the month in Albert’s ear and then I’m going to whisper the day in Bernard’s ear. I’m going to ask Albert and Bernard to keep what I tell them secret and not share the information with each other, but maybe they’ll still be able to figure it out?” Cheryl goes ahead and whispers the day in Albert’s ear and the month in Bernard’s ear.
Albert says: “I still can’t tell when Cheryl’s birthday is. She did tell me the month, but within that month — in fact, within all the months provided — there’s more than one possible day it could be. The information Cheryl gave me does allow me to draw one conclusion though: I’m absolutely certain that Bernard doesn’t know when the birthday is either!”
Bernard: “So, Albert, you’re using your knowledge of the month to conclude that I couldn’t possibly know the answer? How can you be so sure of what I know and don’t know?”
Albert: “Well, Bernard, you were only told the day, not the month. The only way you could know the answer from the day alone is if Cheryl had told you 18 or 19. If she had told you 18 you’d know it’s June 18 because that’s the only one of the ten possible birthdays where the day is 18. Similarly if she had told you 19 you’d know it’s May 19. What I’m saying is that I know Cheryl didn’t tell you 18 or 19, therefore I know you have no way of determining the birthday. For any other number besides 18 and 19, you still have several options to choose from, with no way of narrowing it down further. For example if Cheryl had told you 14, you wouldn’t be able to decide whether it’s July 14 or August 14.”
Bernard: “But how do you know Cheryl didn’t tell me 18 or 19? Aha, the only way you could know Cheryl didn’t tell me 18 or 19 is if she told you a month where there are no possibilities on those days. So she must have told you a month other than May or June, which means her birthday must be in July or August. And with that smaller set of options, I now know exactly when it is!”
Albert: “Really, you’ve figured it out? Well then, I can gather that the day must not be 14, because if Cheryl had told you 14 you’d still have no way to decide between July 14 and August 14. Bernard, you yourself ruled out May and June based on what I said before, and now I’m ruling out July 14 and August 14, so the only remaining possibilities are July 16, August 15, or August 17. And considering those three options together with what Cheryl told me, I know the answer too!”
Onlooker: “Albert and Bernard, I’ve been listening to you talk through this whole thing, and now I also know the answer. If Albert narrowed the possibilities down to July 16, August 16, or August 17 and then declared that he knew the answer, I know Cheryl must have told him the month July. If Cheryl had told him August, then Albert would still not be able to decide between August 16 and August 17. So, now we all know Cheryl’s birthday is July 16!”
Rhythmic Tiling Canons
This video provides a visualization of the some of the rhythmic tiling canons described in the paper “Asymmetric Rhythms and Tiling Canons” by Rachel W. Hall and Paul Klingsberg. A rhythmic tiling canon is a composition in which each player repeats the same rhythmic pattern, with each player beginning at a different time. The rhythmic pattern and entry points are crafted so that once all the players have begun to play, there will be exactly one player striking every beat. That’s to say, every beat is covered by one of the players but no two players ever coincide on the same beat. The video illustrates all possible tiling canons where the rhythmic cycle consists of twelve beats and the entrances of the players are equally spaced.
It fascinates me that these rhythms can be derived through a purely mathematical process and yet they sound so good — some of them remind me of various rhythms I’ve heard in musics from the African continent but I’m not well-versed enough to be able to pinpoint a specific region or style. I should add that the rhythms don’t sound good in all contexts: they seem to work best when played on three percussion instruments with distinct timbres. If each voice were played using C in a different octave on a piano, for example, the distinction between voices becomes less clear as the ear tends to hear melodic patterns formed between voices. If the universe is willing, I’ll be posting a follow-up with some original compositions built using these canons as a rhythmic foundation.
Necklace Counting (draft)
The Problem
A combinatorial necklace is an arrangement of colored beads on circle (or circular string). Imagine the necklace is lying flat on a table and you can’t pick it up to turn it over. Two necklaces are considered equivalent if there’s a way to rotate one necklace so that its beads align with those of the other. (Another way to say this is that you could find positions on each necklace so that if you started at those positions and called out the bead colors in clockwise order, the two sequences of colors would be identical.) So, how many distinct 12-bead necklaces could you create if you had an unlimited supply of black and white beads? That’s the problem we’ll address in this post.
I’m interested in such black/white or binary necklaces because they correspond to musical constructs like chord types or scale families. If you want to know, for example, how many distinct chord types there are in 12-tone equal temperament (where a chord type may have any number of notes from 0 to 12), this turns out to be equivalent to the question we just posed about necklaces.
In mathematical discussions of musical chords and scales, when “the necklace question” comes up, it’s usually addressed in one of two ways. Some authors present an exhaustive list of necklaces/chords/scales obtained by brute force (presumably, the author wrote a computer program to generate all 2^12 binary strings and eliminate pairs of strings that represent equivalent necklaces). Other authors point out that you can obtain a count of the necklaces by invoking a piece of mathematical machinery called the Polya Enumeration Theorem. Feed some numbers into Polya’s formula and we learn that there are 352 binary necklaces of size 12.
When I started thinking about necklaces I was looking for something that neither approach seemed to provide: I wanted to gain an intuitive understanding of how the possibilities arise. Where do those 352 necklaces “come from,” and why aren’t there more of them, or fewer of them, for that matter? Presumably, such intuition could be obtained by exploring the inner workings of the Polya Enumeration Theorem, but I was looking for a more direct path, using only elementary mathematical concepts, so I started trying to devise a method that would help me list all the necklaces by hand, without having to explore and eliminate duplicates. It turns out there are a number of algorithms for generating necklaces in the literature, including one due to Fredricksen, Kessler and Maiorana, and more recent work by Cattell, Ruskey, Sawada, and Serra. The method I came up with is different from approaches I’ve seen elsewhere, so I’ve decided to present it here in hopes that the right reader might find it interesting. In this post, I’m not aiming to present it as a general purpose algorithm for enumerating necklaces of arbitrary size (to do this would require some refinement) or to analyze its performance in contrast to the other algorithms — I’m just offering it as an interesting way to generate and/or categorize the possibilities for size-12 necklaces, a way that hopefully provides some intuition into the problem space, and that is amenable to execution by hand for those crazy enough to want to do it. That said, I’d be interested to collaborate with anyone who thinks this approach could be expanded into something more generally useful, or who could point out where it might already have been explored.
Rudi Seitz 