10

I'm reading an interview book called A Practical Guide to Quantitative Finance Interview by Xinfeng Zhou and I cannot make sense of the solution provided by the book, so I really appreciate your advice.

Question: Birthday Problem from Chapter 2:

You and your colleague know that your boss A's birthday is one of the following 10 dates:

Mar 4, Mar 5, Mar 8

Jun 4, Jun 7

Sep 1, Sep 5

Dec 1, Dec 2, Dec 8

A told you only the month of his birthday, and told your colleague C only the day. After that, you first said: "I don't know A's birthday, C doesn't know either." After hearing what you said, C replied: "I didn't know A's birthday, but now I know it." You smiled and said:"Now I know it too." After looking at the 10 dates and hearing your comments, your assistant wrote down A's birthday without asking any questions. So what did the assistant write?

Solution:

Let D be the day of the month of A's birthday, we have D belongs to the set {1,2,4,5,7,8}. If the birthday is on a unique day, C will know the A's birthday immediately. Among possible Ds, 2 and 7 are unique days. Considering that you are sure that C does not know A's birthday, you must infer that the day the C was told of is not 2 or 7. Conclusion: the month is not June or December. (If the month had been June, the day C was told of may have been 2; if the month had been December, the day C was told of may have been 7)

So my doubt is:

Why we can exclude June and December completely? I think we can only exclude June 7 and December 2 since 7 and 2 are unique days. I think my problem is: cannot make sense of the statement in the parenthesis (highlighted in bold above)

Community
  • 1
M00000001
  • 647
  • 4
  • 15
  • 1
    If month-knower had June (Dec), she could infer from the list that C might have 7 (2) and thus the birthday. Then she wouldn't have 'first said: "I don't know A's birthday, C doesn't know either."' – Mats Lind Nov 20 '19 at 10:45
  • Thanks a lot to my friend: demully and Mats Lind, the correct answer is Sep 1. I should have provided the correct answer instead of putting a partial answer, my bad:(I really appreciate your effort for helping me with the question before my interview:) – M00000001 Nov 21 '19 at 02:30

4 Answers4

7

If the birthday would have been in June or Dec there would have been a chance that day-knowing C would have known it, because there are unique possible days-of-months in the list for possible birthdays in those months (Dec 2 and June 7). The only way the month-knowing person referred to as "you" in the problem could know that there is no chance for C, is that the months are neither June nor Dec.

We can exclude Dec and June months only because the month-knowing person tells us C does not have a chance. And again, Dec and June would have given C a possiblity to know. But exactly because the bday is in Mar or Sep, C doesn't initially know for sure.

If day-of-month would have been 7 C knows bday is June 7. If day-of-month would have been 2 C knows bday i Dec 2. Otherwise, C would not know. C could only know if month is June or Dec, it isn't.

Month-knower knows for sure C doesn't know so month is not June or Dec. When month-knower gives this away, we are left with Mar and Sep. Then C says she knows for sure wich she wouldn't be able to if the day was 5 because then she couldn't decide betweeen Mar 5 and Sep 5.

Now we only have Mar 4, Mar 8 and Sep 1 and then month-knower says she knows. And that could only be because the bday is i September 1. So know we all know.

To control the result, assume it is true: Month-knower has Sep, Day-knower has 1. Month knower knows both of them at this point cannot choose between Sep 1 and 5 and hence first said: "I don't know A's birthday, C doesn't know either.´Now, day-knower C replied: "I didn't know A's birthday, but now I know it." C didn't know it at first since it was 1 and thus neither 2 nor 7. Now C knows its neither Dec nor June since Month-knower could initially declare she was sure about C's ignorance. Now C knows the brithday because C knows it is 1 and neither June nor Dec but the only remaing 1-date: Sep 1. After hearing this, month knower knows it is not Sep 5 since that would have made C unsure between Mar 5 and Sep 5 and hence the only remaining Sep-date: Sep 1. Hence she smiled and said:"Now I know it too." The assistant has the same information as we problem solvers have and can thus write Sep 1 on the board.

Mats Lind
  • 1,402
  • 9
  • 16
  • How does "you" not knowing allow C to deduce anything? "You" might know the day was 4, 1 or 8. In which case, it is still possible for it to be June or December. "Your" ignorance is only meaningful in excluding 2 or 7 (not Jun/Dec), I think. This is the information C needs to clear up his uncertainty. If it was information about any month other than June, I don't see how he could work it out (given still multiple options in the other months). Or maybe I'm just being really, really thick ;-) – demully Nov 20 '19 at 10:08
  • Please try to work it out from Sep 1 following the information flow in the problem. Where do you see a conflict? – Mats Lind Nov 20 '19 at 10:14
  • Lord knows I might have this wrong... but if it was Sep1, then I can't see how C/M can infer this from "your"/D's ignorance. C/M would know it was Sep; but how would your/D's ignorance tell C/M it was the 1st vs the 5th. That's the bit I can't get. – demully Nov 20 '19 at 10:46
  • See my edit of the answer where I added the control – Mats Lind Nov 20 '19 at 11:05
  • Thank you @MatsLind, I really appreciate your detailed explanation. I'm much more clear now:) Sorry for I didn't put the correct answer (provided by the interview book already but I cannot make sense of it), my bad:( – M00000001 Nov 21 '19 at 02:37
3

This is about the difference between mutual knowledge and common knowledge: https://en.wikipedia.org/wiki/Mutual_knowledge_(logic)

Each person has incomplete knowledge. But they don't know anything about the state of the other's information. Learning this is new information.

D knows day but not month.
M knows month but not day.
Both know the nature of what the other knows.
But they do not know if the other has the answer or not.
Both then confirm their uncertainty to each other.

If the day was 2 or 7, then D would have been able to work out month.
So he is telling M that the day is not 2 or 7.
So M knows that the day must then be 1,4,5 or 8.

If the month was Mar, Sep or Dec, then M would still not be able to work out the birthday by eliminating the 2s and 7s.
But he can (because eliminating these from the month he knows gives him the answer).
He tells D he knows the answer.

D can now work it out. He knows that M would still be uncertain if Mar, Sep or Dec. The fact M's worked it out means it must be June. D already knows the day, of course.

The assistant doesn't need to know either the day or the month. He can work out from D's ignorance giving M the answer that it is not a 2 or 7 (else D would have known in the first place). Then when M's realisation gives D the answer, he know's it's June (else if Mar, Sep or Dec, then M would still be unsure). If June and not the 7th, it must be Jun4.

demully
  • 5,071
  • 7
  • 22
  • But it says in the question that "Conclusion: the month is not June or December"? – Mats Lind Nov 20 '19 at 08:50
  • And it looks like it is M that starts doing the telling in the problem. Is it D that starts to tell in your solution? – Mats Lind Nov 20 '19 at 09:42
  • As put, the problem starts with the statement that neither the narrator (M in my case) nor C (D in mine) knows. Whoever said it, I think, is irrelevant. It's the statement of mutual ignorance that gives C/D the information necessary to deduce. Unless I'm missing it, no other day other than Jun4 is consistent with the process of the elimination of uncertainty here. – demully Nov 20 '19 at 09:59
  • If it is June, how then can M immediately conclude that D does not know? – Mats Lind Nov 20 '19 at 10:05
  • It's when D tells M he doesn't know, then M can know that D would know if it was a 7. The fact D doesn't know means that it's not a 7. M already knows it's June, so it must be June 4. If M was told a different month by the boss, he could not work it out. He can only work it out if it was June. – demully Nov 20 '19 at 10:10
  • Doesn't D tell M "I didn't know A's birthday, but now I know it."? – Mats Lind Nov 20 '19 at 10:12
  • Thank you @demully, I really appreciate your detailed explanation and the useful link. It is really great to know the basic knowledge behind it, sorry for I didn't provide the correct answer (which was given by the interview book) to this question, my bad:( – M00000001 Nov 21 '19 at 02:35
0

I think the proper answer would be Mar 4. Let me explain:

  1. "You" know that colleague C knows the day, but C still does not know the birthday. -> Hence we can eliminate Jun 7 and Dec 2.

-> We have 2x Day 1, 4, 5, and 8

  1. "You" proclaim that neither of you knows the birthdate.

  2. Thus, colleague C now knows that "You" still cannot pick out the correct date (given the information from (1.) ) -> Hence it cannot be June 4.

  3. Having now eliminated June 4, leaves us with only 1x Day 4: Mar 4.

  4. (4.) Prompts C to exclaim that he now knows, from the information alone that "You" didnt know in (2.)

-> Hence it must be Mar 4. The deduction that C does not stand a chance at knowing prompts us to discard Dec is pure speculation.

quh86
  • 1
  • the correct answer is Sep 1. – lehalle Apr 17 '22 at 03:36
  • 1
    The crucial point is that "You" speak before C can give away any information. C hasn't spoken yet. So by saying "C does not know", you give away that it can't be June or December, because these are the only months for which C could possibly know the birthday. There is no speculation on this part. – Martin Georg Haas Apr 20 '22 at 19:23
0

Here's something that made it click for me, maybe it will help someone else.

Dates again for convenience:

Mar 4, Mar 5, Mar 8

Jun 4, Jun 7

Sep 1, Sep 5

Dec 1, Dec 2, Dec 8

One key thing to notice is to break down the first statement by "Me":

I don't know A's birthday, C doesn't know either.

It conveys two things:

  • C doesn't know the real birthday

  • I don't know the real birthday

Let's break each down:

  • C doesn't know the real birthday: If this is true, then it can't be a birthday with a unique date, so it's not June 7th or Dec 2nd.

  • I don't know the real birthday: How can I know for sure that C doesn't know the real birthday? Well I know the month. If I were told the month were December, then the options are Dec 1, Dec 2, Dec 8. In which case, C could know the real birthday, which violates the bullet point above. So I can't have been told December is the month. Same logic goes for June.

Once we've eliminated June and December, if C knows it, then it has to be a unique day in March or September, so it has to be Sep 1st.

JoeVictor
  • 113
  • 5