[Math] Is it possible to solve the Zebra Puzzle/Einstein’s Riddle using pure math

mathematical modelingproblem solvingpuzzle

A coworker of mine posted a problem in our local communication software that seems to be a simpler variation of the Zebra Puzzle/Einstein's Riddle. I know how to solve it intuitively, by using elimination. But is it possible to solve these kinds of problems using pure math?

Here is the problem he posted:

Albert and Bernard just become friends with Cheryl, and they want to
know when her birthday is. Cheryl gives them a list of 10 possible
dates. May 15, May 16, May 19 June 17, June 18 July 14, July 16 August
14, August 15, August 17

Cheryl then tells Albert and Bernard separately the month and the day
of her birthday respectively.

Albert: I don't know when Cheryl's birthday is, but I know that
Bernard does not know too. Bernard: At first I don't know when
Cheryl's birthday is, but I know now. Albert: Then I also know when
Cheryl's birthday is.

So when is Cheryl's birthday?

Can I model this problem mathematically in some way, and then solve it using a deterministic approach? I assume that if it is possible with this one, it would also be possible with the Einstein's one.

Best Answer

For a slightly systematized solution consider the following table which is known to both A and B: $$\matrix{&&{\rm B:}\cr &&14&15&16&17&18&19\cr {\rm A:}&{\rm May}&&\bullet&\bullet&&&\bullet\cr &{\rm Jun}&&&&\bullet&\bullet\cr &{\rm Jul}&\bullet&&\bullet\cr &{\rm Aug}&\bullet&\bullet&&\bullet\cr}$$ A is assigned a row, and B is assigned a column of this table.

A's first statement is tantamount to the following: "All bullets in my row have a second bullet in their column." This at once eliminates the May and June rows from consideration, so that the table now looks as follows: $$\matrix{&&{\rm B:}\cr &&14&15&16&17&18&19\cr {\rm A:}&{\rm Jul}&\bullet&&\bullet\cr &{\rm Aug}&\bullet&\bullet&&\bullet\cr}$$ B's statement relates to this reduced table, and its relevant part is tantamount to the following: "In my column there is a single bullet." This eliminates the column 14 from consideration, so that the table now looks as follows: $$\matrix{&&{\rm B:}\cr &&15&16&17&18&19\cr {\rm A:}&{\rm Jul}&&\bullet\cr &{\rm Aug}&\bullet&&\bullet\cr}$$ A's second statement refers to this third table, and is tantamount to the following: "In my row there is a single bullet."

Therefore we now can tell when Cheryl's birthday is.

Related Question