There’s a popular problem circulating this last day or two, having appeared in Singapore’s Math Olympiad. As someone who grew up doing extracurricular math competitions, it was cool to see one getting so much attention, even if it was incorrectly claimed in some places to be a problem from a normal elementary school math test. I’m sure there are a million websites explaining solutions by now, but here’s my version as requested by a friend who wanted to see what I meant when I said that I found a solution by drawing a graph. 🙂
For anyone who hasn’t seen the problem, it goes like this:
Person C tells the month of their birthday to person A and the date (number) of their birthday to person B. The two are also told that the birthday is one of the following:
- May 15, May 16, May 19
- June 17, June 18
- July 14, July 16
- August 14, August 15, August 17
After that, the two begin applying reasoning without giving away their secret information (the month and date respectively) to each other:
- A says “I don’t know when C’s birthday is, but I know that B doesn’t know either.”
- B says “I didn’t know C’s birthday at first, but I know now.”
- A says “Then I know too.”
Our job is to find out what C’s birthday is. Nothing A or B says here is a lie, and they are perfect reasoners, meaning that they don’t ‘miss’ anything – at any given time they know everything they could possibly know based on the information they have been given.
So let’s solve it. First we will draw a graph of the 10 possibilities which are listed, before we start trying to use the hints. We connect A to all the months and B to all the dates, and a month is connected to a date if and only if it’s one of the 10 possible birthdays. You could do this with only the middle two columns, but I added A and B because it helps me remember that A secretly knows the actual month (and views the graph from left to right) while B secretly knows the actual date (and views things from right to left). The way this graph works is that the existence of a path A -> (some month X) -> (some day Y) -> B means that the combination of month X and day Y hasn’t been eliminated as a possibility. The graphs I draw will be graphs of public knowledge: it’s what we the silent observers know at each point in the story, and at any given time A and B will each know everything that we do in addition to their secret extra information (the month in A’s case, the date in B’s). A and B make their public statements by combining the current public information with their secret information to reason out new facts.
(By the way, these graphs are drawn in XMind, which I am enjoying a lot lately for brainstorming, organizing thoughts, and even stuff like planning out the structure of a paper.)
Now we will consider our first piece of information, that “A knows that B doesn’t know.” We’ll look at this one piece at a time, beginning with the simpler information that “B doesn’t know”, which we can take as fact because in this problem no one is lying or making logic errors. Looking at the graph from B’s perspective, which dates would cause B to know the full answer right off the bat?
Okay, so it can’t be the 18th or 19th because that doesn’t match A’s claim that B doesn’t know. But hold on, how is it that A knows this?
A date of 18 or 19 would be a giveaway for B, and the only way A would know for sure that B doesn’t have an easy out like this is if A’s month is one which isn’t connected to any of these ‘easy out’ numbers. So A’s month can’t be May or June.
Now we’ll clean up the graph by eliminating these months and dates and their connections, and then we’ll look at the next piece of information: “B didn’t know before, but knows now”. The first piece of information, that “B didn’t know before”, doesn’t add anything new. It just confirms to us that A was right when they claimed B didn’t know, and it’s probably only included in the problem so people don’t go down the wrong track by thinking this is one of those ‘figure out who’s lying’ problems. The important information here is that the current public knowledge graph plus B’s private info about the date is sufficient for him to determine the answer.
B knows, which means that looking from right to left, B can walk from the B node to their number and then know which month to walk to from there. This can’t happen if B’s number is 14, so the 14th as a possibility conflicts with B’s claim and can be eliminated. We remove the node, simplifying the graph again, and consider the final piece of information which is that A now knows the answer as well.
A, knowing the month and the current state of public information, is now claiming that they too know the answer. That means that, looking from left to right, A can walk from the A node to their month and then know which date to walk to from there. This can’t be true if A’s month is August because they would still be torn between two options, Aug 15 and Aug 17. Therefore August as a possibility conflicts with A’s claim and can be eliminated.
The updated public knowledge graph is:
I could’ve removed these numbers when I removed August but I didn’t want anyone to think I was doing magic. We can clean up the orphaned nodes and we will get a graph containing only one path which represents the only possibility not yet eliminated. That’s our answer! Good job!
