Is it possible to solve the Zebra Puzzle/Einstein's Riddle using pure math?

Question

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.

Answer 1

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.

Answer 2

I'm on a brief break so forgive any mistakes or any lack of utility, but here is an attempt to apply some formalization to the problem.

Let $X$ and $Y$ be two sets. In this case let $X = \{ x | x \text{ is a possible month} \}$ and $Y = \{ y|y \text{ is a possible day} \}$. Then the choices Cheryl gives is $Z \subset X \times Y$. Lets also say an answer to the problem is exactly one $(a,b) \in Z$. A solution exists if at most Two Parties A and B can figure out the answer.

We can say something about a solution existing by looking at a function $S_y: Y \to 2^Z$ where $S_y(a) :=\{(x,y)| y=a \text{ where } (x,y) \in Z\} $. A similar function $S_x: X \to 2^Z$ where $S_x(a) :=\{(x,y)| x=a \text{ where } (x,y) \in Z\}$. Basically the set of all pairs in $Z$ that share the element $y$ or $x$.

1) It should also be noted here that for any $(a,b) \in Z$ then $S_x(a) \cap S_y(b) = (a,b)$ since $S_x(a) \cap S_y(b) = \{(x,y)| x = a \wedge y = b \text{ where } (x,y) \in Z\}$

We can look at the cardinality of a these sets to determine if a solution even exists.

Let

$\phi_y: Y \to \mathbb{N}$ where $\phi_y(y) = |S_y(y)|$.

$\phi_x: X \to \mathbb{N}$ where $\phi_x(x) = |S_x(x)|$

2) From 1) We can show that if $\phi_y(b) > 1$ and $\phi_x(a) > 1$ then $S_x(a) \neq S_y(b)$ since $|S_x(a) \cap S_y(b)| = 1$

Now lets say we construct a $Z$ for our riddle.

A trivial solution $(a,b) \in Z$ exists if either $\phi_x(a) = 1$ or $\phi_y(b) = 1$. Trivial in that Party A or Party B will know it is the birthday since either $S_x(a)$ or $S_y(b)$ contains one element, the solution.

To guarantee a solution

For Party A to not know but know B doesn't know that implies that: $$|S_x(a)| > 2 \wedge \phi_y(y_i)> 1, \forall (x,y)_i \in S_x(a) $$ Then for B to know after this information implies $$\exists (x,y)_i \in S_y(b) \text { s.t. } \phi_x(x_i) = 1$$ which one of these is a solution, particularly: $$\exists! (x,y)_i \in S_y(b) \text { s.t. } \phi_x(x_i) = 1 \quad \wedge \quad \exists!(x,y)_i \in S_x(a) \text { s.t. } \phi_y(y_i) = 1$$

This is more of a verification that a solution exists for a riddle of this form. It may be interesting to generalize to any amount of parties and set of values $\prod_{i \in I} X_i$.

Gotta cut out for now, but i'll check back to see if anyone notices anything foolish.

Answer 3

You are confusing two different types of problems.

Cheryl's Birthday Problem is not a variation of the Zebra Problem.

In the Zebra Problem, you are given just one big list of statements. In the Cheryl's Birthday Problem, you have two independent agents/players (Albert and Bernard), with two separate states of knowledge.

The Zebra Problem is a classic homework for students in their first year of Computer Science, usually in the context of Prolog. See list of possible solutions here: http://rosettacode.org/wiki/Zebra_puzzle.

My solution linked by grand_chat (Here) explicitly takes care of multiple states of belief of different players. The elimination is not the most interesting part, more interesting is to give some precise meaning to statements of the type "A knows that B doesn't know", which is done using Aumann's model of information. This is not needed in the Zebra Problem, because there we have one single global state that contains all the information we have.