Cheryl’s Birthday Problem

This problem is an absolute classic in creative usage of modus ponens, and I’m definitely not its originator.

Problem 1. Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gives them a list of 10 possible dates:

May 15, May 16, May 19
June 17, June 18
July 14, July 16
August 14, August 15, August 17

Cheryl then tells Albert and Bernard separately the month and the day of her birthday respectively.

Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard doesn’t know too.
Bernard: At first I don’t know when Cheryl’s birthday is, but I know now.
Albert: Then I also know when Cheryl’s birthday is.

When is Cheryl’s birthday?

(Click for Solution)

Solution. The key phrase to parse is the phrase “I don’t know”. We know that Albert is given the month and that Bernard is given the number.

Lemma 1. Albert will know Cheryl’s birthday if and only if given his month, there is one and only one possible date number.

Lemma 2. Bernard will know Cheryl’s birthday if and only if given his date number, there is one and only one possible month.

Both lemmas are of the form $p \leftrightarrow q$ .

Now, we parse Albert’s first sentence:

I don’t know when Cheryl’s birthday is
I know that Bernard doesn’t know too

Albert is given one of the four options: May, June, July, or August. He says “I don’t know when Cheryl’s birthday is”, so that by Lemma 1, his month has multiple date numbers. This phrase doesn’t reveal much, but the next one does.

Albert says “I know that Bernard doesn’t know”. By Lemma 2, Bernard’s date number can be matched by more than one month. If, however, his numbers are 18 or 19, then each of these numbers can only match one month, a contradiction:

$(18 \lor 19 \rightarrow c) \rightarrow \neg(18 \lor 19).$

Therefore, Bernard’s date numbers cannot be 18 or 19, and we are left with the following possibilities:

May 15, May 16
June 17
July 14, July 16
August 14, August 15, August 17

If Albert was given either May or June, then 18 or 19 are Bernard’s possibilities. This can be phrased as the conditional proposition

$\text{May} \lor \text{June} \rightarrow 18 \lor 19.$

Since $\neg(18 \lor 19)$ , modus tollens yields

$\neg (18 \lor 19) \rightarrow \neg(\text{May} \lor \text{June}) = \neg \text{May} \wedge \neg \text{June}.$

Thus, Albert was not given May nor June, leaving us with the following possibilities:

July 14, July 16
August 14, August 15, August 17

Now, we parse Bernard’s sentence:

At first I don’t know when Cheryl’s birthday is
But I know now.

Bernard says “At first I don’t know when Cheryl’s birthday is”. This means by Lemma 2, prior to Albert’s sentence, Bernard’s number can correspond to multiple months, but after Albert’s sentence, Bernard’s number can correspond only to one month. If Bernard was given the number 14, then there are still two possible months, a contradiction:

$(14 \to c) \to \neg 14.$

Thus, Bernard was given either 15, 16, or 17, and we are left with the following dates:

July 16
August 15, August 17

Finally, we parse Albert’s second sentence:

Then I also know when Cheryl’s birthday is.

If Albert was given August, he will still be uncertain. Since he is certain, Albert must have been given July:

$(\neg \text{July} \to c) \to \neg(\neg \text{July}) = \text{July}.$

Therefore, Bernard was given 16.

Therefore, Cheryl’s birthday is July 16.

To summarise the argument, the premises yield:

$(\text{May} \lor \text{June} \lor \text{July} \lor \text{August}) \wedge (14 \lor 15 \lor 16 \lor 17 \lor 18 \lor 19)$
$18 \lor 19 \to c$
$\therefore (\text{May} \lor \text{June} \lor \text{July} \lor \text{August}) \wedge (14 \lor 15 \lor 16 \lor 17)$
$\text{May} \to 18\ \text{possible} \to c$
$\text{June} \to 19\ \text{possible} \to c$
$\therefore (\text{July} \lor \text{August}) \wedge (14 \lor 15 \lor 16 \lor 17)$
$14 \to c$
$\therefore (\text{July} \lor \text{August}) \wedge (15 \lor 16 \lor 17)$
$\text{August} \to c$
$\therefore \text{July} \wedge (15 \lor 16 \lor 17)$
$\therefore \text{July} \wedge 16$