My last post was about “Cheryl’s birthday puzzle”, which recently became an internet sensation.  I mentioned several additional puzzles in that post and promised solutions; here they are.

Let me begin, though, with a “cryptography” variant of the Cheryl puzzle which was sent to me by my friend and puzzle guru Pete Winkler:

Cheryl’s birthday possibilities are now May 14 or 15, June 15 or 16, July 16 or 17 or August 14 or 17. Albert gets the month and Bernard the day as before, and they both want to find out the birthday.  But Eve, who’s listening in, mustn’t find out.  How can A and B, who’ve never met before (and aren’t cryptographers), accomplish this mission?

Think about it, it’s a fun little puzzle!  [Pete writes in addition: “You can also do this with a cycle of 5 months (10 dates total) but then you need a coin to flip.”]

My Meta-Cheryl Challenge (as revised on April 20) was to come up with a list of dates for which the following puzzle will have a unique solution:

Albert and Bernard have just met Cheryl and want to know when her birthday is.

Cheryl says “I’m not going to tell you, but I’ll give you some clues.” She writes down a list of dates…

“My birthday is one of these,” she says.

Then Cheryl whispers in Albert’s ear the month of her birthday. To Bernard, she whispers the day.

Albert and Bernard think for a minute and the following dialogue ensues:

Albert: I don’t know when Cheryl’s birthday is.

Bernard: I knew that you didn’t know.

Albert: I still don’t know.

Bernard: I didn’t know before you said that, but I know now.

Albert: In that case, I know too.

When is Cheryl’s birthday?

This puzzle has many possible solutions.  Here’s one that works: Cheryl’s list is January 1, February 1, February 2, March 1, March 2, March 3.

After Albert’s first statement, we know that Cheryl’s birthday is not in January.  After Bernard’s first statement, we know her birthday isn’t on the 1st, otherwise she could not have known that Albert hadn’t been told January (in which case he would know).  After Albert’s second statement, we know that Cheryl’s birthday isn’t in February, for otherwise (having ruled out the 1st) Albert would know at this point.  After Bernard’s second statement, we can rule out March 3, because otherwise Bernard would have known Cheryl’s birthday at the very beginning.  This leaves March 2 as the only remaining possibility, which both Albert and the reader can now deduce.

If that wasn’t challenging enough for you, check out these puzzles by Joel David Hamkins.

Let me continue by apologizing to any readers who might have agonized over Martin Gardner’s “Impossible Problem” — unbeknownst to me, that problem really is impossible! Oops.  I retroactively added the following remarks into my original post:

The original Frudenthal problem had the upper bound of 100 instead of 20, and the unique solution is that the two numbers are 4 and 13.  Gardner was presumably trying to simplify the arduous case analysis needed to check that (4,13) is the only solution by noting that both solutions are less than 20.  However, despite the fact that the solutions are less than 20, the problem does not work if we change the upper bound to 20. 

The reason that the puzzle was impossible when bounded between 1 and 20 is that the product of the supposedly correct answers (4 x 13 = 52) would be a uniquely factorable product if , and then it would be immediately clear to P that 52 could only be factored as 4 x 13.  But if , then 52 could also be factored as 2 x 26, so P could not immediately determine that the sum is 17 rather than 28.  However, as soon as S says he is sure P doesn’t know what the two numbers are, then P knows that the sum is 17 rather than 28, since if it was 28 the product could have been 11 x 17 = 187, which would have allowed P to immediately know the two numbers.

If one changes the upper bound from 20 to 100, we more or less get Freudenthal’s original problem which has the unique solution (4,13).  I will briefly explain how one could come up with this answer, and point out a relation to Goldbach’s conjecture.  First, here is Freudenthal’s original problem as formulated by Julian Havel in his book “Impossible!” (but with a new character named Cheryl added by me):

Polly and Sam are friends with Cheryl, who has a history of taunting her friends with difficult logic puzzles.  Cheryl tells them that she is thinking of two integers between 2 and 100 inclusive, and they have to guess the numbers.  Cheryl whispers their product to Polly and their sum to Sam.  The following dialogue ensues:

1. Polly: I don’t know the two numbers yet.

2. Sam: I knew that you didn’t.

3. Polly: I know the two numbers now.

4. Sam: So do I.

What are the two numbers?

Here is a sketch of a solution.  Call the unknown numbers x and y.  The conditions of the problem give us that Without loss of generality, we can assume that .

After statement 1, we know that cannot be of the form or , where and are primes.  For otherwise there would be only one way to factor and Polly would know and .  Thus or with and prime.

After statement 2, we know that is not a sum of two primes.  Otherwise, Sam could not be sure that Polly isn’t yet able to determine and .  The Goldbach conjecture is known for all even positive integers up to some very large bound; in particular, every even number (which is the maximum possible value of ) is a sum of two primes.  Thus must be odd and is not prime.   Similarly, cannot be of the form with prime.

Let be the set of all pairs satisfying the above restrictions.  (This can be found by hand by someone really patient, or easily by a computer.)

From statement 3, we deduce that Cheryl’s product must appear exactly once in the list of numbers of the form where .  Let be the set of pairs for which there does not exist with but .

From statement 4, we deduce that Cheryl’s sum must appear exactly once in the list of numbers of the form where .  Let be the set of pairs for which there does not exist with but .

It turns out (by a brute-force search) that   It’s quite cool that there’s a unique solution, but it’s unfortunate that proving it requires such a large case analysis.  The latter is probably one reason that Cheryl’s birthday problem has now achieved a level of popularity that Freudenthal’s problem never did.  (The internet and social media might also have something to do with it.)

As for The Case of the Playful Children, here is the solution published by The American Mathematical Monthly:

And now for the puzzles about knights and knaves.

1. Once upon a time I visited an island inhabited only by knights (who always tell the truth) and knaves (who always lie).  I came across two inhabitants resting under a tree.  I asked one of them “Is either of you a knight”?  He responded (with either a yes or a no), and I knew the answer to my question.  Is the person to whom I addressed my question a knight or a knave, and what is the other one?

Solution (from Raymond Smullyan’s “What is the Name of This Book”, Puzzle #36): Suppose the speaker — call him A — had answered “Yes”.  Could I have then known whether at least one of them was a knight?  Certainly not.  For it could be that A was a knight and truthfully answered “Yes”, or it could be that both of them were knaves, in which case A would have falsely answered “Yes”.  So if A had answered “Yes” I would have had no way of knowing.  But I told you that I did know after A’s answer.  Therefore A must have answered “No”.  If A were a knight, he couldn’t have truthfully answered “No”, so A is a knave.  Since his answer “No” is false, there must be at least one knight present.  Hence A is a knave and the other inhabitant is a knight.

2. I wanted to know the answer to the Great Question “Why is there something instead of nothing?”, so I went to the two High Priests of the island.  They made the following statements:

First Priest: I am a knave, and I don’t know why there is something instead of nothing.

Second Priest: I am a knight, and I don’t know why there is something instead of nothing.

Then one of the two High Priests, who did in fact know the answer to the Great Question, said “There is something instead of nothing.”

What did I conclude from all of this?

Solution (from Raymond Smullyan’s “What is the Name of This Book”, Puzzles #156, 157):  The first priest couldn’t be a knight; he must be a knave.  Hence his statement is false, which means that he does know the answer to the Great Question.  The second priest’s response tells us that he is either a knight who doesn’t know the answer to the Great Question or a knave.  Since the priest who said “There is something instead of nothing” did in fact know the answer, that priest must have been a knave.  So the statement “There is something instead of nothing” is false, and we conclude that nothing exists. However, if nothing exists, there could not have been a priest who made the statement at all.  Thus the island does not exist — and in fact cannot exist!

3. Suppose that you visit a (different) island and come across three natives, one each from a tribe of knights, a tribe of knaves, and a tribe of natterers (who answer every question randomly).  You do not know which native is from which tribe.  There are two boxes in front of you, and you know that one is full of gold and the other is full of poisonous gas, but you don’t know which is which.  You are permitted to ask two yes-or-no questions, each question being directed to just one of the three natives.  How can you get the information you need to open the correct box?

Solution (from Peter Winkler’s “Mathematical Mind-Benders”, pp. 93-95): You need to be sure that the second native you query is not the natterer.  This is necessary because you’re not going to know the right box after the first question, and if the second responder is random you might not learn any more.  On the other hand, this objective is sufficient, because you can then use the traditional one-native query as your second question: namely, something like “If I were to ask you whether this box [pointing to one] is full of gold, would you say yes?”  To attain the objective, you’ll need to ask Native A something about Native B or Native C, then use the answer to choose between B and C.  Here’s one that works: “Is B more likely than C to tell the truth?”  Curiously, if A says “Yes” you pick C, and if he says “No” you pick B!  If A is the knight you want next to query the companion who is less likely to tell the truth, namely the knave.  If A is the knave you want the more truthful of his companions, namely the knight.  Of course, if A is the natterer it doesn’t matter which of B and C you turn to next.