Dependency logic—the famous logic puzzle Cheryl's birthday
Read the excerpt from Wikipedia first,
"Cheryl's Birthday is the unofficial name given to a mathematics brain teaser that was asked in the Singapore and Asian Schools Math Olympiad, and was posted online on 10 April 2015 by Singapore TV presenter Kenneth Kong. It went viral in a matter of days. The quiz asked readers to determine the birthday of a girl named Cheryl using a handful of clues given to her friends Albert and Bernard."
And then the puzzle,
Try to solve the puzzle, it will be worth trying and a lot of fun without any doubt.
You may skip the bit of theory next and skip straight to the solutions section.
Common Logic and Dependency logic based on Relative knowledge
Barebones common logic example
When I apply logic, I apply it on the basis of my knowledge on relevant facts, not on your knowledge or for that matter Rini's knowledge. That is the usual logic analysis that we do, by ourselves.
For example, when I know that "Surya grew up in Kolkata", I can say with confidence, "Surya is from West Bengal". That is elementary logic statement based on my knowledge of the fact that "Surya grew up in Kolkata" and also "Kolkata is in West Bengal". The first part is personal knowledge, and the second part public knowledge and both are considered to be TRUE, at least by me. The important thing here is, I have made a CONCLUSION from two pieces of FACTS. Any of the facts might have been FALSE turning my CONCLUSION also FALSE.
Dependency logic based on relative knowledge
In logic puzzles, all sorts of complications are introduced, naturally. Otherwise there would be no fun.
A special category of complexity is in what we call DEPENDENCY LOGIC.
When I made the statement on Surya, I analyzed the two pieces of processed final facts or statements.
But in Cheryl's puzzle,
You have TWO logical persons Albert and Bernard making "THEIR statements" based on THEIR knowledge and you have to put yourself into their shoes, so to say, and think logically to decipher the IMPLICATION of their statements.
Your logic analysis is dependent on other's logic analysis results. This is DEPENDENCY LOGIC ANALYSIS and so is obviously discomforting and unnatural to us. That's where you have your challenge.
Solution to Cheryl's birthday logic puzzle
For solving any type of difficult logic puzzle, use of logic tables invariably provides great help. We will use here two tables, a Fact table and a Logic status table. The fact table will give you a clear idea of the nature of the information Cheryl had given as well as it will show you the embedded pattern in months and dates in the information given.
The three statements will form the remaining component of the puzzle.
When we analyze and form our conclusions at each stage, the logic status will change in the logic table. The fact table and the statements are the invariants that do not change.
The Fact table: Date-month table
We have put all the 6 unique dates 14, 15, 16, 17, 18 and 19 as columns and four unique months, May, June, July and August as rows. The dates given by Cheryl to her two friends are marked possible dates as "y" against the suitable cells. For example, for 15th May, a "y" is marked against 15 column and May row.
The most important pattern of two unique dates 18th June and 19th May cannot be ignored even at this early stage and so is colored red. This obviously will be the key to the solution.
The Statements: Logic statements
The key fact and the three statements made by Albert and Bernard one after the other make up the second component of the puzzle.
You have to analyze the three components—fact table, statements and logic status table together to arrive at final implication at each stage, all the time moving towards the solution.
The Logic table
In logic table we will record the status of logic analysis after processing implications of each statement. We will simply use the date-month table itself as the logic table.
When a date is proved to be invalid by one of the statements, the corresponding entry in the table will be marked as x instead of y. For invalid month, it will be crossed out. The date and month left after all the three statements are fully analyzed will be Cheryl's birthday.
Result after analyzing Albert's first statement: Stage 1.
At the start, Albert knows the month (you or Bernard do not know it). As he does not know the birthday, and as no month has a unique single date, month can be any of the four (to you or Bernard).
After Albert made his first statement, situation became more clear. As Albert knows now that Bernard does not know the birthday,
The month cannot be May or June.
These two months have dates 18 and 19 not appearing in any other month. If Bernard knew any of these two dates he would also have known the birthday immediately. Albert's knowledge of the month being either July or August, he knows for sure Bernard does not know the birthday. In these two months there is no unique date.
This is perfect reasoning that Albert and you also carry out. Bernard's statement just after this will let you and Albert know what Bernard really knows.
The status of logic table at this stage is shown below.
Result after analyzing Bernard's first statement: Stage 2.
By the first part of his statement Bernard confirms second part of Albert's previous statement. But, significant is Bernard's confirmation that now he knows the birthday.
The date can only be one of 15, 16 or 17 and month July or August.
The date cannot be 14th July, as it appears in both July and August, and as Bernard doesn't know the month, he won't have known the birthday if the date given to him by Cheryl were 14.
At this point Bernard knows the birthday, you don't know it and also don't know what Albert will know after this statement. Fun, isn't it?
The status of logic table is as below.
Result after analyzing Albert's second statement: Final stage 3.
The implication to you that the date must be one of 15, 16 or 17 also was clear to Albert. Only difference was in Albert knowing the month precisely that you didn't know for sure.
If month were August, there would have been two possible dates 15 and 17. Knowing the date, Bernard would have known the birthday also, but not Albert or least of all you.
So when Albert confirmed that he also knows the birthday, it must be 16 and July. For certain.
To Bernard first, then Albert and finally to you the knowledge became clear.
The final logic table is shown below.
As every month has more than 1 date, Albert couldn't have known the birthday. But as he confirmed that Bernard doesn't also know the birthday, the month cannot be May or June. Albert doesn't know the date, but he knows that May and June each has dates 18 and 19 respectively that do not appear in any other month. His knowledge of the month then must be July or August.
Hearing Albert's statement, Bernard confirms that he knows the birthday. He couldn't have done it if the birthday were 14th as 14th appears in both July and August. So the birthday must be one of 15 August, 16 July or 17 August.
When Bernard confirms that he knows the birthday, with this knowledge of possible dates 15 August, 16 July or 17 August, Albert also confirms that now he knows the birthday. As August has two dates 15 and 17, Albert couldn't have known the birthday for sure if he knew the month to be August. He is sure now because his knowledge of month is July and 16 July appears uniquely with no ambiguity or uncertainty for him.
We have carried out a methodical step by step analysis that is suited to solve logic puzzles in general. This approach lays bare all the mysteries of the puzzle and apparently removes the fun in searching for the solution blindfolded in the dark.
What do you think?
Puzzles you may enjoy
Logic analysis puzzles
Logic puzzle, When is Cheryl's birthday