Recently a puzzle that asked the birthdate of Cheryl got popular with the answer of July 16, in which Bernard and Albert have to figure out.
The first step to the solution was to rule out the whole months of May and June because both these months contain unique dates that would give the answer right away.
What I don't understand is that while we rule out these two unique dates is necessary, but why do we need to rule out all the other dates of May and June?
Is it really valid to rule out the entire month simply because it contains the unique date?
So what if the answer was May 15 or May 16 instead? What is so invalid about May 15 and May 16?
I thought if we rule out the unique dates, retaining May 15 and May 16 is still valid. But why is it not valid? I thought ruling out the entire months of May and June because they both contain unique dates (as well as non-unique dates that may remain valid) is simplistic filtering.
Will Bernard and Albert know?
I don't understand.
If the dates were...
May 15 16
June 17
July 14 16 21
August 14 15 17
How would the answer differ? The right answer (July 16) would not be the right answer.
In my opinion, even if the dates of May 15 and May 16 are retained, Albert can STILL be sure Bernard does NOT know the date is 19, or else Cheryl would not need to tell her date separately, because Bernard would know right away. Thus by right May 15 and May 16 are still valid options.
The Answer to End All Questions About Cheryl's Birthday
In the initial problem, the reader is unaware of Cheryl's birthday. Albert and Bernard also begin with only the information they are told in secret.
Below, I will describe the knowledge that each Albert, Bernard, and the reader has of the birthdate, exploring all of the possible birthdates that Cheryl might have.
Initial State
Albert is told a month. Depending on the month that he is told, he knows the birthday belongs to one of the following dates:
May: 15, 16, 19
June: 17, 18
July: 14, 16
August: 14, 15, 17
Bernard is told a day. Depending on the number he is told, he knows the birthday belongs to one of the following dates:
14: July, August
15: May, August
16: May, July
17: June, August
18: June
19: May
Independently, Albert has already narrowed down the list of dates to at most 3 based on the month he was told. Similarly, Bernard has narrowed them down to at most 2 based on the day that he was told. They are both immediately able to throw out the remaining dates without further instruction, however the reader of the puzzle does not yet have any information, and therefore must be still considering all 10 dates. All of these initial possibilities are known to everyone involved since the reader is able to deduce the relationships given just the initial list.
First Statements
Albert and Bernard are both aware of the possibilities open to each other as they both knew the initial list of dates.
There is no month that only has one day, so we know the first part of Albert's statement is always:
Albert: I do not know Cheryl's birthday...
Let's consider what Albert's first statement is in each of the four month scenarios by expanding the month-day relationship using Bernard's initial possibilities.
May
15: May, August
16: May, July
19: May
If Bernard was told "19", then he might know because there is only one possible month associated with it. The second part of Albert's statement for May is:
Albert: ...but Bernard might know.
June
17: June, August
18: June
If Bernard was told "18", then he might know because there is only one possible month associated with it. The second part of Albert's statement for June is:
Albert: ...but Bernard might know.
July
14: July, August
16: May, July
There is no day in July that is only in July, so if Bernard was told either of the two days in July, he would not be able to deduce Cheryl's birthdate without more information. The second part of Albert's statement for July is:
Albert: ...and neither does Bernard.
August
14: July, August
15: May, August
17: June, August
There is no day in August that is only in August, so if Bernard was told any of the three days in August, he would not be able to deduce Cheryl's birthdate without more information. The second part of Albert's statement for August is:
Albert: ...and neither does Bernard.
If we consider the possibility of Bernard speaking first, he will say the following when told one of 14, 15, 16, or 17:
Bernard: I do not know Cheryl's birthdate.
To which Albert responds
Albert: I already knew that (see "...and neither does Bernard."); or
Albert: I didn't know that (see "...but Bernard might know.").
In this case, we now proceed to the second statements with the knowledge that Albert has just provided us.
Or Bernard says:
Bernard: I know Cheryl's birthdate.
To which Albert responds
Albert: So do I (May, June).
Note that it is impossible for Bernard to initially state that he knows Cheryl's birthdate without more information if Albert were told July or August. They do not say any more statements here as they both have uniquely identified the birthdate. It is important to note that in these cases, the reader of the puzzle cannot deduce the birthdate.
Second Statements
Albert has finished his first statement in one of two ways: "but Bernard might know" and "neither does Bernard". Let's consider how the affects Bernard's perception:
Albert: ...but Bernard might know
This indicates Albert was told May or June (since those are the only two scenarios in which he would say this). Bernard's table now becomes:
14: impossible
15: May
16: May
17: June
18: June
19: May
Now for every day that Bernard was told, he unequivocally knows Cheryl's birthdate.
Bernard: I now know Cheryl's birthdate.
If he was told 18 or 19, he would have already known the birthdate as discussed in the first step and he would instead say:
Bernard: I already knew Cheryl's birthdate.
Albert: ...and neither does Bernard
This indicates that Albert was told July or August (since those are the only two scenarios in which he ends his first statement this way). Bernard's table now becomes:
14: July, August
15: August
16: July
17: August
18: impossible
19: impossible
If Bernard was told 15, 16, or 17, he can now uniquely identify Cheryl's birthdate. He could not have been told 18 or 19 if Albert finishes his first statement in this way.
Bernard: I now know Cheryl's birthdate.
In the event that Bernard was told 14, his second statement becomes:
Bernard: I still don't know Cheryl's birthdate.
Third Statements
Bernard has said one of the three following statements: "I now know Cheryl's birthdate", "I already knew Cheryl's birthdate", or "I still don't know Cheryl's birthdate". Let's consider the negative case first:
Bernard: I still don't know Cheryl's birthdate.
There is only one case that Bernard would have said this (if he were told 14), so now Albert's table appears as such:
May: impossible
June: impossible
July: 14
August: 14
Now Albert knows both the month and day. His final statement is:
Albert: I now know Cheryl's birthdate.
However, neither Bernard or the reader is given enough information at this point to decide on the date. Only Albert can know if Bernard is told 14.
Bernard: I already knew Cheryl's birthdate.
This immediately tells Albert the birthdate, too, as he could have only said this when Albert began with but Bernard might know (stemming from May or June):
May: 19
June: 18
The uniqueness here allows Albert to decide:
Albert: I know Cheryl's birthdate.
However, the reader is unable to choose between May and June. Only Albert and Bernard can know in this scenario, the reader is left in the dark.
Bernard: I now know Cheryl's birthdate.
The remaining statement by Bernard must now also be considered with Albert's first statement in order to narrow the decisions:
Albert: but Bernard might know. (May, June)
Bernard: I now know Cheryl's birthdate.
Albert's table then becomes:
May
15: May
16: May
19: impossible
Had Albert been told May, he would be unable to decide between 15 and 16. Albert and the reader are unable to deduce the date in this scenario; only Bernard can know.
Albert: I still don't know Cheryl's birthdate.
June
17: June
18: impossible
Had Albert been told June, he is left with one possibility: June 17. The reader can also deduce this date (description in the conclusion below).
Albert: I now know Cheryl's birthdate.
Albert: and neither does Bernard. (July, August)
Bernard: I now know Cheryl's birthdate.
Albert's table then becomes:
July
14: impossible
16: July
Had Albert been told July, he is left with one possibility: July 16. The reader can also deduce this date (description in the conclusion below).
Albert: I now know Cheryl's birthdate.
August
14: impossible
15: August
17: August
Had Albert been told August, he would be unable to decide between 15 and 17. Albert and the reader are unable to deduce the date in this scenario; only Bernard can know.
Albert: I still don't know Cheryl's birthdate.
Conclusion
In the scenarios noted above where the reader cannot deduce the answer, the original puzzle is unsolvable. Albert and Bernard may still be able to know the date in some of the described cases, but the reader cannot.
In the other two, July 16 and June 17, the reader can deduce using the information provided by Albert and Bernard. The statements made by the pair leads to a single possibility. I have included the scenarios in which the statements are spoken in order to guide the reader without requiring scrolling up to re-read my earlier arguments:
Albert: but Bernard might know. (May, June)
Bernard: I now know Cheryl's birthdate. (15, 16, 17)
Albert: I now know Cheryl's birthdate. (June 17)
A unique date is now indicated by Albert.
Albert: and neither does Bernard. (July, August)
Bernard: I now know Cheryl's birthdate. (15, 16, 17)
Albert: I now know Cheryl's birthdate. (July 16)
A unique date is now indicated by Albert.
The paths provided by the statements made by the two guessers uniquely identifies only July 16 and June 17 to the reader. Any other birthdate cannot be deduced by the reader.
The original puzzle follows the path indicated above that leads uniquely to July 16, so this is how we can determine the answer to the original puzzle.
Note: if the initial list of dates is altered, the statements made by Albert and Bernard must also be altered, even when Cheryl's birthdate stays the same.
Epilogue
The above dissertation is describing one-to-one and many-to-one relationships between the birthdates and the statements made by Albert and Bernard. If we define the statements made by the pair as:
$X_1$: Bernard doesn't know.
$X_2$: Bernard might know.
$Y_1$: Bernard already knew.
$Y_2$: Bernard now knows.
$Y_3$: Bernard still doesn't know.
$Z_1$: Albert now knows.
$Z_2$: Albert still doesn't know.
We can now describe the resultant paths ($R_n$) for each date:
May 15: $X_2 + Y_2 + Z_2 = R_1$
May 16: $X_2 + Y_2 + Z_2 = R_1$
May 19: $X_2 + Y_1 + Z_1 = R_2$
June 17: $X_2 + Y_2 + Z_1 = R_3$
June 18: $X_2 + Y_1 + Z_1 = R_2$
July 14: $X_1 + Y_3 + Z_1 = R_4$
July 16: $X_1 + Y_2 + Z_1 = R_5$
August 14: $X_1 + Y_3 + Z_1 = R_4$
August 15: $X_1 + Y_2 + Z_2 = R_6$
August 17: $X_1 + Y_2 + Z_2 = R_6$
Collating these results and writing them in the opposite direction:
$R_1$: May 15, May 16
$R_2$: May 19, June 18
$R_3$: June 17
$R_4$: July 14, August 14
$R_5$: July 16
$R_6$: August 15, August 17
Here, we see that $R_1$, $R_2$, $R_4$, and $R_6$ are all many-to-one relationships. In a many-to-one relationship, the reader of the puzzle cannot deduce Cheryl's birthdate. In the one-to-one relationships ($R_3$ and $R_5$), Cheryl's birthdate can be accurately concluded.
The following are also true (as can be deduced within this epilogue, but as have also been shown in the main body of the above answer):
$R_1$: Both Albert and Bernard know the birthdate, but we do not.
$R_2$: Both Albert and Bernard know the birthdate, but we do not.
$R_3$: Albert, Bernard, and we all know the birthdate.
$R_4$: Albert knows the birthdate, but Bernard and we do not.
$R_5$: Albert, Bernard, and we all know the birthdate.
$R_6$: Bernard knows the birthdate, but Albert and we do not.