Cheryl's Birthday Problem

[TheMawn]

I found this http://www.cnn.com/2015/04/15/living...em-goes-viral/

It was quite fun to solve.


Cheryl is trying to get Albert and Bernard to guess when her birthday is. She gives them 10 dates and they have to figure out which one is her birthday:

May 15
May 16
May 19
June 17
June 18
July 14
July 16
August 14
August 15
August 17

She tells Albert the Month, and Bernard the Day.


Albert: I do not know when Cheryl's birthday is, but I know that Bernard also does not know.

Bernard: At first I did not know when Cheryl's birthday is, but now I know.

Albert: Then I also know when Cheryl's birthday is!


When is Cheryl's Birthday?

[LaurV]

Oh! Don't you dare to start!
I wasted a day to explain to my girls how to solve it and why is easy.

OTOH, I just found out you lost 10 minutes of your life doing this!

[TheMawn]

Originally Posted by LaurV

Oh! Don't you dare to start!
I wasted a day to explain to my girls how to solve it and why is easy.

OTOH, I just found out you lost 10 minutes of your life doing this!

Tee hee. Thanks TJAOI.

Don't worry bud. I can do the explaining on this one. I was able to arrive at both "answers." I sort of got the "bad" one first but I caught myself immediately, fixed it and proceeded to the "good" one (and then went back to finish the bad line of fuzzy logic).

[axn]

July 16

[LaurV]

(intentionally separate post)

I met the next problem ~25 years ago, when I was studying computer viruses (my thesis/papers were about data protection, not related to encryption, but to protecting the data against being destroyed by intention/mistake/viruses/etc, for example; I still have a collection of over 3000 families of computer viruses - over 60k "individuals" - many of them well disassembled and commented, mostly by me, other by colleagues/students of mine, this was way before the internet era. I was one of the first guys in the world to create an antivirus dedicated to find and remove the one-half virus, which at that time was not detectable by mcafee neither by Skulason's F-Prot not Hyponen's F-secure, due to its polymorphic abilities. At the time, Fred Cohen and Leonard Adleman were my heros and idols , and I studied "cooperative viruses" and "hidden channels" of transmitting information between them. With this occasion I met the following problem, told to me by a colleague who - at the time - was a big fan of public key cryptography, at a time when I didn't hear about the subject).

The problem goes like that:

There is a teacher T playing against a team of two students R and S. The students are in a classroom, but can not communicate between them and can not say anything except answering with "yes" or "no" to the teacher's questions as explained below. Everybody hears what the other people are saying. Nobody is cheating nor trying to cheat.

The game setup is like that: the teacher give to the student R a number N and to the student S a number M. Both N and M are positive, nonzero integers, carefully chosen by the teacher. No student knows the other student's number. The teacher writes two numbers A and B on the board, which are visible by both students. Either A or B is the sum of N+M, the other is a random positive integer, carefully chosen by the teacher.

So, the student R knows N, A, B. The student S knows M, A, B. Both of them knows that either A or B is the sum of M+N, but they don't know which. Of course, A is not equal to B, otherwise it makes no sense, is trivial. The teacher selects all 4 numbers carefully.

Then the game starts: The teacher asks one of the students: "Do you know what number your colleague has?". The student can answer only "yes" or "no". If he says "yes", then he MUST say the number. If he is right, the students win. If he miss, the teacher wins. If he says "no", then first turn ends.

The next turn: the teacher asks the other student (copy/paste here): "Do you know what number your colleague has?". The student can answer only "yes" or "no". If he says "yes", then he MUST say the number. If he is right, the students win. If he is wrong, the teacher wins. If he says "no", then turn ends.

And so on, and so forth.

If one student says "yes", then he MUST say the correct number of his colleague, otherwise the teacher wins. If he says "no", then the teacher will ask the other student the same question, and the game continues.

After [Max(A,B)/2]+1 turns of "no" the game ends and the teacher wins.

Question: Is the output of the game deterministic? If so, who wins?

Of course, the teacher can not win "deterministically", because any student can say "yes" any turn, and he has 50% chances to guess the right number. So the game is at least 50% "probabilistic" win for the students. If you said that the teacher has all the information, and the students can not get any new information after each turn, then you are wrong. First, you are wrong because the game can be "won" probabilistically by the students, with at least 50% chances. Second, you are totally wrong: the output of the game is deterministic, the students can always win. Indeed, and contrary to the common sense, the students will always win. The teacher, in spite of the fact that he holds all the keys, has no chance to win.

Of course the students didn't define a strategy of "cheating" before the game started, they never met each other, they are honest and don't cheat, but they are both clever guys, and they are thinking.

How do they win?

------------
Note 1: this is a generalization of the "cheryl" problem; in fact, those month/day dates could be "arranged" a bit, modified in such a way that more than 3 turns be necessary. For those dates, assuming that any number can be used for month, and any numbers for day, (not only 1-12 and 1-31, in fact I don't know if this is really required), the problem can be made so complicate as 9 turns of "i don't know" be necessary to solve it.
Note 2: the connection with data protection? Imagine the teacher is a server, which hold some important information, which is "attacked" by some "student" clients, each knowing some pieces of this information, some even not related, like for example, one student can only read the free space on the disk, other can read the execution times of some process, etc. If they find the right "hidden channel" to exchange the information, they will always "win" against the "teacher".
Note 3: and yes, I had the problem exactly the same way, I knew from the enunciation that the students win (as opposite to be asked "who wins? and how?" and I could find the strategy to win in less that an hour, and my solution was more elegant than the solution presented by my colleague who told us the problem! No joke!
Note 4: My lunch break is over..
[edit: Note 5: This also generalize, somehow, the problems with three philosophers/prisoners and partyhats/painted foreheads.]

[TheMawn]

Oh god it's too much for me. The R knows that S knows that R knows that S knows chains are so hard to keep track of!

[ATH]

1) Albert knows that Bernard does not know (by knowing the date), so it cannot be the 18th or 19th. Since Albert knows this (by knowing the month) it cannot be May or June.
2) From the above Bernard learns it has to be July or August and then he can figure out the birthday, so it cannot be the 14th.
3) Since Albert can pick the birthday out of the last 3 remaining dates by knowing only the month the answer has to be July 16th.

[TheMawn]

Actually though I think I can see where the problem is going even if I have a hard time following it through...

I had tried this with larger numbers and I ended up with a 7-chain of You know that I know that ... so I'm starting over with smaller, easier numbers...

My number is 6. Your number is 8. The Sums are 10 and 14.

I know your number is either 10 - 6 = 4 or 14 - 6 = 8. I have you narrowed to TWO.

If your number is 4, you have me narrowed to 6 or 10. If you number is 8, you have me narrowed to 2 or 6. I know that you have narrowed me to THREE. (Of course you ACTUALLY have me narrowed to 2 but I don't know this).

If my number is 2, I have you narrowed to 8 or 12. If my number is 6, I have you narrowed to 4 or 8. If my number is 10, I have you narrowed to 0 or 4. In other words, I know that you know that I have you narrowed to FOUR.

The thing here is the rules say that 0 is not allowed. I think this is where we stop. There's a clear pattern here:


I know that you have either 4 or 8. (note the difference of 4 here and in the sums, that is easy)

I know that you know that I have either 2, 6 or 10. (note this is +/- 4 from my actual)

I know that you know that I know that you have either 0, 4, 8 or 12 (+/- 4 from 2 lines ago again).


From here everything collapses: 0 is not allowed, and that result came from me possibly having 10. If I actually had 10, I would immediately know you had 4. Because I didn't know this, that means I don't have 10.

So if I say "I don't know" this tells you that I don't have 10 and I know this as well. So now I know that have me narrowed to only 2 numbers. You actually knew from the beginning I had 2 or 6 and now I know this as well.

If you narrowed me to 2 or 6, it's because you had 8.


In general, it looks like we build a "staircase" of A's and B's by adding rows and columns (+/- |A-B|) to a matrix until we hit or pass 0. Then using the very difficult to parse "I know that you know that I know that you know" we slowly grind away at the edge of the matrix until we reach the answer.

[Jayder]

I was introduced to this problem by this video from James Grime (frequently featured on Numberphile): https://www.youtube.com/watch?v=w3Nzkae_TRU