Dustin IngramWriting — Speaking — Github — Twitter
When Is Cheryl's Birthday?April 15 2015
The Problem #
A certain viral “math” problem is currently taking the internet by storm. It goes as follows:
Albert and Bernard just met Cheryl. “When’s your birthday?” Albert asked Cheryl.
Cheryl thought a second and said, “I’m not going to tell you, but I’ll give you some clues.” She wrote down a list of 10 dates:
May 15, May 16, May 19 June 17, June 18 July 14, July 16 August 14, August 15, August 17
“My birthday is one of these,” she said. Then Cheryl whispered in Albert’s ear the month — and only the month — of her birthday. To Bernard, she whispered the day, and only the day. “Can you figure it out now?” she asked Albert.
Albert: I don’t know when your birthday is, but I know Bernard doesn’t know, either.
Bernard: I didn’t know originally, but now I do.
Albert: Well, now I know, too! When is Cheryl’s birthday?
The Solution #
The solution hinges on repeatedly finding unique (or non-unique) days and months from the set of potential dates. While it doesn’t require any incredible math skills, it does require some good deductive logic. Once you understand what the trick is, it’s easy to arrive at a solution. To verify the solution I came to, I decided to implement the problem in Python (although, really any language would do).
TL;DR: The entire script is available as a gist here.
First, let’s make a simple class to represent our Date:
class Date: def __init__(self, day, month): self.day = day self.month = month def __repr__(self): return "(%d, %s)" % (self.day, self.month)
Then we’ll add all of the ten dates Cheryl proposed:
dates = [ Date(15, 'may'), Date(16, 'may'), Date(19, 'may'), Date(17, 'jun'), Date(18, 'jun'), Date(14, 'jul'), Date(16, 'jul'), Date(14, 'aug'), Date(15, 'aug'), Date(17, 'aug'), ]
Next, we’ll write two utility functions which remove dates with non-unique days (or months) from our list of dates:
def remove_duplicate_days(xs): return [x for x in xs if sum(1 for d in xs if d.day == x.day) == 1] def remove_duplicate_months(xs): return [x for x in xs if sum(1 for d in xs if d.month == x.month) == 1]
Note: I realize these are inefficienet n^2 algorithms, and that I should be
collections.Counter, but I’m just trying to keep it simple and
Albert knows the month, Bernard knows the day. Albert does not know when Cheryl’s birthday is, but he knows Bernard doesn’t either. This means that the the month of Cheryl’s birthday is not a month with a unique day.
Select the months which have a unique day:
months_with_one_date = [date.month for date in remove_duplicate_days(dates)] # >>> ['may', 'jun']
Remove the dates which has a month which has a unique day:
dates = [date for date in dates if date.month not in months_with_one_date] # >>> [(14, jul), (16, jul), (14, aug), (15, aug), (17, aug)]
Now, since Bernard knows the day, if it is unique, he knows the answer. He says he knows the answer, so the day must be unique.
Remove the dates which do not have a unique day:
dates = remove_duplicate_days(dates) # >>> [(16, jul), (15, aug), (17, aug)]
Now, since Albert says he knows the answer too, so the month must be unique.
Remove the dates which do not have a unique month:
dates = remove_duplicate_months(dates) # >>> [(16, jul)]
Only one date remains: July 16th.