# Birthday Logic Question

**URL:** <https://boards.straightdope.com/t/birthday-logic-question/717622>\
**Category:** Factual Questions\
**Created:** [April 14, 2015, 5:31am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622 "2015-04-14T05:31:35Z")\
**Posts on this page:** 20\
**Page:** 6

<div class="post-metadata">

**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\
**Post date:** [April 15, 2015, 1:41pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/101 "2015-04-15T13:41:15Z")

</div>

> [@leahcim](#):
>
> I’d seen a version of this problem done more mathematically before, where a mathematician, M, thinks up two whole numbers, a and b, between 3 and 90-ish. To one other mathematician, P, he tells the product ab, and to the other, S, he tells the sum a+b.
> 
> P says, “I don’t know what the numbers are”.  
> S says, “I already knew that you didn’t know. I also don’t know”.  
> P says, “now I know what they are”  
> S says, “now I know, too”
> 
> What are the numbers?
> 
> I suspect that the current problem is a version of that one adjusted to have less math.

[Here’s a further link](http://en.wikipedia.org/wiki/Impossible_Puzzle) with explanation and solution to the puzzle above, for those interested.

I’m not sure if the birthday puzzle is necessarily related. This type of logic puzzle is fairly common, in my experience, and I suspect much older than 1969 (which is where your puzzle comes from.)

As for how to make them, I assume you’d start with something like my “near-trivial” example above, and build up from there.

---

<div class="post-metadata">

**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\
**Post date:** [April 15, 2015, 3:39pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/102 "2015-04-15T15:39:10Z")

</div>

And there’s no limit on complexity. Here’s one you won’t want to attempt by hand:

~ ~ ~ ~ ~ ~ ~

Dr. Socrates is testing two of his expert logicians, Samuel and Patricia, while Anthony listens on. You are working on a 3-D Sudoku but your ears perk up when you realize Dr. Socrates is presenting a difficult puzzle.

“I’ve picked two different integers and want you two to figure out what they are. I’ll tell Samuel the sum which is positive and no bigger than (mumble). I’ll tell Patricia the product which is larger than the sum.”

Here Dr. Socrates whispers a number in Samuel’s ear and another number in Patricia’s ear. Samuel, Patricia, and Anthony all heard the integer the Doctor imposed as a bound on the sum, but you were still daydreaming and missed it.

Now Patricia says “I don’t know the numbers.”  
Samuel says “I already knew you didn’t; I don’t know them either.”  
Patricia says “I still don’t know the numbers.”  
Samuel says “And still neither do I.”  
Patricia says “Oh? Now I DO know the numbers.”  
Samuel says “And now, so do I.”

Anthony says “Interesting. Patricia’s product was a 3-digit number but, to achieve the same result with a larger 3-digit product, the bound on the sum would have needed to be increased, and the first available such 3-digit product would have been some hundreds bigger than Patricia’s product.”

What was the bound Dr. Socrates mumbled? What were the numbers?

---

<div class="post-metadata">

**Author:** ![Barkis\_is\_Willin](https://avatars.discourse-cdn.com/v4/letter/b/a183cd/32.png) [@Barkis\_is\_Willin](https://boards.straightdope.com/u/Barkis_is_Willin)\
**Post date:** [April 15, 2015, 3:47pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/103 "2015-04-15T15:47:24Z")

</div>

Here’s what they would have said if they fully explained themselves.

Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know too {because I know the month does not contain a unique date, such as May and June}.

Bernard: At first I don’t know when Cheryl’s birthday is, but I know now {because the day is unique to the only remaining months}.

Albert: Then I also know when Cheryl’s birthday is {Because the month I was given only had two possibilities and if the day were 14, Bernard would not have been able to deduce the complete date}.

It must be July 16.

---

<div class="post-metadata">

**Author:** ![Telemark](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/telemark/32/372_2.png) [@Telemark](https://boards.straightdope.com/u/Telemark)\
**Post date:** [April 15, 2015, 3:48pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/104 "2015-04-15T15:48:28Z")

</div>

> [@septimus](#):
>
> What was the bound Dr. Socrates mumbled? What were the numbers?

[http://growingleaders.com/blog/wp-content/uploads/2011/01/my-brain-is-full.jpg](http://growingleaders.com/blog/wp-content/uploads/2011/01/my-brain-is-full.jpg)

---

<div class="post-metadata">

**Author:** ![Buck\_Godot](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/buck_godot/32/6573_2.png) [@Buck\_Godot](https://boards.straightdope.com/u/Buck_Godot)\
**Post date:** [April 15, 2015, 5:34pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/105 "2015-04-15T17:34:03Z")

</div>

> [@malaka](#):
>
> Now that jezzaOZ got it, can we revisit my question: How are these types of questions/problems devised? Are they logical/deductive-reasoning scenarios that are dressed up a bit, or does someone encounter this scenario in real life and realize it makes for a good puzzle? How does someone concoct such a scenario?

Its not too hard, you just decide what statement you want that passes on the information (such as A knows B doesn’t know the date) and then create a set of situations that this information eliminates (singletons in May and June). Then you go on to the next piece of information (B now knows the Brithday) so make two of the dates singletons now that (May and June have been eliminated). etc.

---

<div class="post-metadata">

**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\
**Post date:** [April 15, 2015, 9:08pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/106 "2015-04-15T21:08:01Z")

</div>

In case it wasn’t posted, The New York Times has a good explainer:

> **[How to Figure Out Cheryl’s Birthday (Published 2015)](https://www.nytimes.com/2015/04/15/science/answer-to-the-singapore-math-problem-cheryl-birthday.html)**
>
> A step-by-step explanation of a birthday logic problem making the Internet rounds.

---

<div class="post-metadata">

**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\
**Post date:** [April 17, 2015, 7:34pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/107 "2015-04-17T19:34:17Z")

</div>

There actually are two incorrect answers that at least had some support. Watch [this video](http://www.youtube.com/watch?v=w3Nzkae_TRU) from Dr. James Grime.

Note, they are definitely both incorrect.

---

<div class="post-metadata">

**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\
**Post date:** [April 17, 2015, 8:00pm UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/108 "2015-04-17T20:00:06Z")

</div>

I was thinking some more about this yesterday and I now realize I was wrong. I focused too much on the idea that Albert and Bernard had to figure out Cheryl’s birthday from the statements they were making and I didn’t consider that each of them also had additional information. Reading the puzzle, we don’t know what month Albert was told but of course he does. So it’s possible for him to pinpoint the birthday using both the information he was given by Cheryl and the information he got from the statements.

Short version: I was wrong.

---

<div class="post-metadata">

**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\
**Post date:** [April 19, 2015, 12:54am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/109 "2015-04-19T00:54:12Z")

</div>

> [@septimus](#):
>
> And there’s no limit on complexity. Here’s one you won’t want to attempt by hand:

This is just absurdly difficult.

Without loss of generality, I’ll assume that a\<b for all pairs [a, b].

[spoiler]“I’ve picked two different integers and want you two to figure out what they are. I’ll tell Samuel the sum which is positive and no bigger than (mumble). I’ll tell Patricia the product which is larger than the sum.”

Both the sum and product are positive, so therefore both numbers are positive. Also, since the product is larger than the sum, neither number is 0 or 1 (since 0_N \<= N+0 and 1_N \< 1+N).[/spoiler][spoiler]Now Patricia says “I don’t know the numbers.”

From this, the product cannot be the multiple of two primes (if it were 15, she would know the numbers are [3, 5] (since [1, 15] is out)).

It also can’t be the third or fourth power of a prime. 27 could only be [3, 9]. And 81 could only be [3, 27] ([9, 9] doesn’t work).

I’m probably missing some other possibility here, but I can’t think of one.[/spoiler][spoiler]Samuel says “I already knew you didn’t; I don’t know them either.”

Let’s start with the first statement. If Samuel _already_ knew that Patricia didn’t know the numbers, then it means that whatever the sum is, all possibilities for a\*(S-a) have non-unique representations (i.e., they’re not in the set that I excluded previously). I’m not sure exactly how many pairs that excludes, but we can say that the sum (and the bound) is at least 11: the possible pairs are 2_9=18, 3_8=24, 4_7=28, and 5_6=30, but each of those products have different representations, and had Patricia gotten them she couldn’t have known the answer.

I feel like it must, but I don’t see yet how the second part of the statement gives us any additional information. It means the sum could not have been 5, but we already knew that.[/spoiler]That’s all I’ve got so far. I think it demands a computer program, but I’m not even certain how to structure it. At least not efficiently. In principle, each person has to consider all the possible universes that the others belong to, and this could conceivably include their beliefs about the universes that you belong to, and so on. It seems exponential. But maybe it’s not actually that hard.

At least Anthony’s statement narrows down the possibilities for a brute-force search, though it seems like cheating to take it into account early on.

---

<div class="post-metadata">

**Author:** ![jezzaOZ](https://avatars.discourse-cdn.com/v4/letter/j/a9a28c/32.png) [@jezzaOZ](https://boards.straightdope.com/u/jezzaOZ)\
**Post date:** [April 19, 2015, 5:27am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/110 "2015-04-19T05:27:54Z")

</div>

> [@Dr.Strangelove](#):
>
> Without loss of generality, I’ll assume that a\<b for all pairs [a, b].

Why? That restriction isn’t in the puzzle.

I’m working on a solution and so far have learned about semi-primes and the Goldbach conjecture which are both helpful in winnowing a solution.

I’ve also restricted the product space to under 1000 though strictly I shouldn’t because that bit of information doesn’t come till later. I’m now down to 115 potential products and 250 potential sums. And I have just realised I’ve lost most of my sunny Sunday morning!

---

<div class="post-metadata">

**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\
**Post date:** [April 19, 2015, 5:51am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/111 "2015-04-19T05:51:29Z")

</div>

I may owe to Dopers an apology for wasting their times. But I did warn you …

> [@septimus](#):
>
> And there’s no limit on complexity. _ **Here’s one you won’t want to attempt by hand** _:…

I tend to err with _understatement_ rather than _exaggeration_. And I _did_ write "“won’t want (to attempt)” rather than “may not want.”

> [@Dr.Strangelove](#):
>
> This is just absurdly difficult.

Yeah, I tried to warn you. 😛

Composing logic puzzles has been a hobby of mine for a while – you might even discover my true name if you peruse the 5-star puzzles in _Dell Logic Puzzles_. I don’t know why I composed this particular puzzle and posted it. I think it’s more masochism – it takes effort to compose – than sadism – I really thought the warning would take.

If you really insist on solving it, you might start at the Wikipedia page cited upthread which has a python program (I didn’t – I only program in C), add the two extra loops implied by my slightly more involved construction, and run the program for a range of limits instead of just limit=100. But I’m afraid even pursuing this would still be masochistic…

---

<div class="post-metadata">

**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\
**Post date:** [April 19, 2015, 5:58am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/112 "2015-04-19T05:58:03Z")

</div>

> [@jezzaOZ](#):
>
> Why? That restriction isn’t in the puzzle.

Although it doesn’t state it explicitly, I think we can infer that the order of the numbers is irrelevant. There’s no way to get an ordering from a sum or product, and it would be silly for Dr. Socrates to reject [3, 5] (say) as an answer because the “real” answer is [5, 3]. So I choose numeric order for simplicity in combining equivalent answers.

---

<div class="post-metadata">

**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\
**Post date:** [April 19, 2015, 6:02am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/113 "2015-04-19T06:02:03Z")

</div>

> [@septimus](#):
>
> If you really insist on solving it, you might start at the Wikipedia page cited upthread which has a python program (I didn’t – I only program in C), add the two extra loops implied by my slightly more involved construction, and run the program for a range of limits instead of just limit=100. But I’m afraid even pursuing this would still be masochistic…

Nah, I’m a programmer and writing a search program is not difficult. I’m using Perl. The difficulty is in applying the constraints correctly. But I think I have a line on the answer… maybe. Thanks for the puzzle, at any rate.

---

<div class="post-metadata">

**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\
**Post date:** [April 19, 2015, 6:04am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/114 "2015-04-19T06:04:42Z")

</div>

And after writing a script…

Looks like I didn’t miss anything in my initial conclusion about Patricia. Between 0 and 999, there are 524 numbers which aren’t of the form p, p[sup]3[/sup], p[sup]4[/sup], or p\*q, where p and q are both primes. I get the same number if I just try to count uniqueness directly.[spoiler]Samuel’s first statement seems to give a _lot_ of information. Unless I messed up, the complete list of possible sums he has is the following (for products\<1000):  
11 17 23 27 29 35 37 41 47 51 53 57 59

In other words, for each number _not_ on that list, there is at least one possibility that gives an unambiguous answer. A sum of 12 could have been 5_7=35. 44 could have been 3_41=123. But for the numbers on the list, every single product possibility had some other possible answer.[/spoiler][spoiler]From here, though, something goes wrong with my strategy.

Patricia still doesn’t know the numbers after she’s reduced the list of sums. It must be that the remaining products are still ambiguous given that list. I get the following:  
30 42 60 66 70 72 78 90 102 110 114 120 126 132 150 162 168 180 196 210 264 270 286 300 306 312 322 330 342 364 378 396 408 420 462 540 546 630 660 702

And Samuel still doesn’t know, though it barely helps us–the list of sums has only been reduced to:  
17 23 27 29 35 37 41 47 51 53 57 59

(we eliminated 11 since it only could have been 5\*6=30)

Supposedly, though, Patricia now knows the answer. The only product which has a unique sum is 30 (which appears with a sum of 2+15=17).

But this conflicts with Anthony’s statement later. I think I need to take the bound into account earlier. Maybe try the process for all possible bounds. At least that’s the only way I can make sense of the logic.[/spoiler]

---

<div class="post-metadata">

**Author:** ![jezzaOZ](https://avatars.discourse-cdn.com/v4/letter/j/a9a28c/32.png) [@jezzaOZ](https://boards.straightdope.com/u/jezzaOZ)\
**Post date:** [April 19, 2015, 6:08am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/115 "2015-04-19T06:08:46Z")

</div>

> [@Dr.Strangelove](#):
>
> Although it doesn’t state it explicitly, I think we can infer that the order of the numbers is irrelevant. There’s no way to get an ordering from a sum or product, and it would be silly for Dr. Socrates to reject [3, 5] (say) as an answer because the “real” answer is [5, 3]. So I choose numeric order for simplicity in combining equivalent answers.

But you rejected considering a=b which as you point out in the 81 case has a potential solution [9,9] (as well as [27,3]). Actually there are only 3 numbers in this category 16, 81, 625 that would be excluded as potential products using your rule. The other perfect squares have ambiguous factor sets.

---

<div class="post-metadata">

**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\
**Post date:** [April 19, 2015, 6:19am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/116 "2015-04-19T06:19:57Z")

</div>

> [@jezzaOZ](#):
>
> But you rejected considering a=b which as you point out in the 81 case has a potential solution [9,9] (as well as [27,3]). Actually there are only 3 numbers in this category 16, 81, 625 that would be excluded as potential products using your rule. The other perfect squares have ambiguous factor sets.

The puzzle says:  
_I’ve picked two **different** integers and want you two to figure out what they are._

So [9, 9] is out, and [27, 3] is the same as [3, 27]. And of course [1, 81] is out because 1\*81 is not _larger than_ 1+81. So if the product was 81, Patricia would know for certain that the numbers were [3, 27] based on what Dr. Socrates said to everyone.

---

<div class="post-metadata">

**Author:** ![Blue\_Blistering\_Barnacle](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/blue_blistering_barnacle/32/3386_2.png) [@Blue\_Blistering\_Barnacle](https://boards.straightdope.com/u/Blue_Blistering_Barnacle)\
**Post date:** [April 25, 2015, 12:43am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/117 "2015-04-25T00:43:31Z")

</div>

> [@Little\_Nemo](#):
>
> I agree with all of this.
> 
> But I don’t agree with this.
> 
> It’s true that July 16th is the only date Albert would be able to deduce from the information he has - but he has no reason to assume he has enough information to deduce the correct date.
> 
> It’s possible that Cheryl likes Bernard better than Albert so she carefully gave them information which would reveal her birthdate to Bernard but not reveal it to Albert.
> 
> The solution given would only work if Cheryl had said that she had given the boys enough information for both of them to figure out her birthday. Then Albert would know the problem was solvable and July 16 was the only possible solution.

But Albert was \*\*told \*\*July, \*\*not \*\*August, so that is how \*\*he \*\*knew.

**We** , on the other hand, had to be given that extra piece (that is was solvable by both boys) to determine the exact date.

And we were given that info when they both (somewhat smugly) said they did solve it.

---

<div class="post-metadata">

**Author:** ![Blue\_Blistering\_Barnacle](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/blue_blistering_barnacle/32/3386_2.png) [@Blue\_Blistering\_Barnacle](https://boards.straightdope.com/u/Blue_Blistering_Barnacle)\
**Post date:** [April 25, 2015, 12:50am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/118 "2015-04-25T00:50:42Z")

</div>

> [@Great\_Antibob](#):
>
> Well, I suppose there’s the chance these two are chaotic evil, and they’re just screwing with people.
> 
> But the reasonable thing to do is suppose they won’t lie, reason logically, and are willing to play along with the silly game.

It’s worth noting that these guys never do prove that they really do know the date.

I also don’t believe that you have logically excluded “True Neutral”, wherin they act for their own benefit (that is impressing Cheryl, maybe even getting to first base).

---

<div class="post-metadata">

**Author:** ![kaylasdad99](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/kaylasdad99/32/3398_2.png) [@kaylasdad99](https://boards.straightdope.com/u/kaylasdad99)\
**Post date:** [April 25, 2015, 9:24am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/119 "2015-04-25T09:24:15Z")

</div>

> [@don\_t\_ask](#):
>
> To the OP.
> 
> Let’s say you are playing Bernard’s role. Cheryl tells you the number. If it is 18 or 19 do you now know her birthday?
> 
> So how can Albert be sure that you don’t **already** know her birthday?

> [@kanicbird](#):
>
> Because Albert knows the month which means it can only be the 14, or the 16th. Both of them are repeated numbers in other months, thus Albert knows that you can not know.

But by saying I he KNOWS that I don’t know, he is eliminating May from my list of possibilities. That’s fine, but now he knows I was told 14 or 16. The only way he can truthfully claim to KNOW I don’t know the birthday is if he KNOWS that I was told 14.

Where does he get off claiming to know my number? And if he DOESN’T claim to know that I don’t know the birthday, I’m still stuck wondering if her birthday is in May or July.

So the solution as written fails on the basis of the entirety of Albert’s initial assertion.

---

<div class="post-metadata">

**Author:** ![kaylasdad99](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/kaylasdad99/32/3398_2.png) [@kaylasdad99](https://boards.straightdope.com/u/kaylasdad99)\
**Post date:** [April 25, 2015, 9:34am UTC](https://boards.straightdope.com/t/birthday-logic-question/717622/120 "2015-04-25T09:34:15Z")

</div>

> [@CurtC](#):
>
> I hope it’s OK if I eliminate the spoiler tag at this late time…
> 
> I disagree with this - I don’t see why you say “This eliminates May and June as they are the two months with unique dates.”
> 
> Here’s my analysis: Albert knows the month, Bernard knows the day. Albert knows that Bernard doesn’t know, that rules out the 18th and 19th days because those are unique, and if one of those were it, Bernard would have known right away.
> 
> Bernard knows that Albert has ruled out the 18th and 19th, and we know that with his month information, Bernard now knows the exact date. The only way this can happen is if the month is June, and the only option left for June is the 17th.
> 
> June 17.

Piffle, if you’ll pardon the expression. If the birthday is June 17, Albert was told that the month was June. How, in your solution, did he rule out the possibility that Bernard was told the 18th?

[Previous page](https://boards.straightdope.com/t/birthday-logic-question/717622.md?page=5)

[Next page](https://boards.straightdope.com/t/birthday-logic-question/717622.md?page=7)