Mr Tan’s Birthday Puzzle

I have come across an interesting logic puzzle from my newsfeed. Here is the puzzle.

Ben and Mark are students of Mr. Tan. Mister Tan’s birthday is on $N/M/1970$ and both of them know that Mr. Tan’s birthday is one of these 10 dates.

Mr. Tan tells Ben the value of $M$ and tells Mark the value of $N$ . Then Mr. Tan asks them, “Do you know when is my birthday?”

Ben says,”I don’t know, but I can ensure that Mark doesn’t know too.”

Mark says,”Initially I don’t know, but I know it now.”

Ben says,”Oh, then I know it too.”

Base of the dialogue and the dates given, can you figure out which date is Mr. Tan’s birthday?

When I first read this puzzle, I remember again the Muddy Children puzzle, back when I was undergraduate students. These two puzzles has one common property: they require the reasoning about knowledge. And what could be more powerful than using logic to reason about knowledge! The question remains: which logic to reason about knowledge?

Well, if you are a logician, philosopher, or theoretical computer scientist, you might have encountered the course of Modal Logic. We can use Epistemic Logic, a variant of Modal Logic, to reason about knowledge. And that is what we are going to use to solve this puzzle.

Epistemic Logic

As usual, when we learn about logic, we need to know two things: the language and its meaning. The language is the syntax, and its meaning is the semantics. The following Backus Naur Form (BNF) formalises the syntax.

Letter $p$ denotes an atomic proposition, $p \in \Phi$ , and $A$ is an agent, $A \in \mathcal{A}$ .

Anyone with a basic knowledge of logic must have known that the connective $\neg$ is read as “not”, the connective $\wedge$ is read as “and”, and so on. Two new connectives in the formal syntax are $\Box$ and $\Diamond$ . The formulae $\Box_{A} \varphi$ is read as “agent $A$ believes that $\varphi$ is true”, and formulae $\Diamond_{A} \varphi$ is read as “agent $A$ considers it is possible that $\varphi$ is true”.

To define its semantics, we need another mathematical structure called state model. The state model for the Epistemic Logic is a triple

where

$S$ is a set, or usually called the set of all possible worlds,
$\xrightarrow{\mathcal{A}}$ is a relation over $S$ , such that $s \xrightarrow{A} t$ means that the agent $A$ considers the state $t$ is possible at the state $s$ ,
$\| \cdot \|$ is a labelling function which maps from the set $\Phi$ to the power set $\mathcal{P}(S)$ . It assigns to each atomic proposition, a set of states in which the atomic proposition is true.

Here is the semantics of the Epistemic Logic.

Using the Epistemic Logic to solve the puzzle

To solve this puzzle, we build a state model first. Here is one possible solution.

In creating the state model, I list all the possible birthdays. We have two relations, with which I colour them red and blue. We also assume that there are blue and red arcs from a state to itself.

Ben’s relations are coloured with red, while Mark’s with blue. For example, if Mr Tan’s birthday is $4/3$ , then Ben could only know that Mr Tan’s birthday is March, but not the day. Therefore, Ben would consider $5/3$ and $8/3$ are possible, and we draw red arcs from $4/3$ to these two states. Likewise, Mark could only know that Mr Tan’s birthday is on the fourth day, but not the month. Thus, Mark would consider state $4/6$ is possible and, hence, we draw the blue arc from $4/3$ to $4/6$ .

The next step is to define the set of agents, the set of atomic propositions $\Phi$ , and the label function $\| \cdot \|$ . The set of agents, of course, consists of Ben and Mark, $\mathcal{A} = \{B, M\}$ . We use the letter $b$ to denote the atomic proposition “Ben knows Mr Tan’s birthday”, and the letter $m$ to the atomic proposition “Mark knows Mr Tan’s birthday”. Thus, the set of atomic propositions are $\Phi = \{b,m\}$ .

Now, no matter which month Mr Tan has told Ben, Ben definitely could not be certain on which day Mr Tan’s was born. Therefore, we set the label function for $b$ with $\| b\| = \emptyset$ . However, if Mark was told that Mr Tan’s birthday falls on the second or seventh day of the month, Mark could easily be certain that Mr Tan’s birthday is either $2/12$ or $7/6$ . This is, obviously, because no other month with these days could possibly be Mr Tan’s birthday. Therefore, we set the label function for $m$ with $\|m\| = \{2/12, 7/6\}$ .

Ben’s first remark

Let’s analyse what Ben says in the first place.

“I don’t know, but I can ensure that Mark doesn’t know too.”

This is translated into the formulae $(\neg \Box_{B} \, b) \ \wedge \ (\Box_{B} \,\neg m)$ . What we need to do next is to eliminate any state in our state model which contradicts with Ben’s first remark. We do this by removing the state $s \in S$ which $s \not\models (\neg \Box_{B} \, b) \ \wedge \ (\Box_{B} \,\neg m)$ .

From the semantics of Epistemic Logic, $s \models \neg\varphi$ , De Morgan’s rule $\neg(\varphi_1 \wedge \varphi_2) \ \equiv \ \neg \varphi_1 \ \vee \ \neg \varphi_2$ , and equality $\neg \Box_{B} \varphi \ \equiv \ \Diamond_{B} \neg \varphi$ , we need to remove the state $s \in S$ such that $s \models \Box_{B} \,b$ or $s \models \Diamond_{B} \,m$ .

Since we know that there is no state such that Ben could know Mr Tan’s birthday, $\|b\| = \emptyset$ , there cannot be any state such that $s \models \Box_{B} b$ . Therefore, we can safely ignore the first disjunct.

We, then, analyse for the second disjunct. The state $s \in S$ satisfy $\Diamond_{B} \, m$ if the following quantifier holds true.There are only two states $t$ such that $t \models m$ , that is, $2/12$ and $7/6$ . This implies that a state satisfying the quantifier above is the state which has at least one red arc to either states $2/12$ or $7/6$ , that is, $\{4/6, 7/6, 1/12, 2/12, 8/12\}$ . Here is the resulting state model.

From this new state model, we update again the label function for $m$ with $\|m\| = \{4/3, 8/3, 1/9, 5/9\}$ , and keep the old label function for $b$ . This is because, given this new state model, each day is unique except day five. There is also no unique month and, therefore, the label function for $\| b\|$ remains empty set.

Mark’s first remark

Now we analyse what Marks says.

“Initially I don’t know. But I know it now.”

We use the formulae $\Box_{M}\, m$ to represent this remark. (We only translate the second sentence, since the first sentence belong to the previous state model.) Again, what we have to do is to remove any state $s \in S$ such that $s \not \models \Box_{M} \, m$ . That is any state satisfying $s \models \Diamond_{M} \, \neg m$ . Since the set of states where $t \models \neg m$ is $\{5/3, 5/9\}$ , then we have to remove all states which have at least one blue arc to any member of this set. Surprisingly, they are the members of the set $\{5/3, 5/9\}$ themselves. We update again the state model as follows.

The label function becomes $\|b\| = \{1/9\}$ and $\|m\| = \{4/3, 8/3, 1/9\}$ .

Ben’s last remark

Lastly, Ben replies as follows.

“Oh, then I know it too.”

This translates into the formulae $\Box_{B} \, b$ . With this last remark, we remove the states which at least have a red arc to any state which satisfies $t \models \neg b$ . That is we have to remove the states $4/3$ and $8/3$ , which leaves us with a single state.

Conclusion

By quoting the famous Sherlock Holmes,

When you have eliminated the impossible, whatever remains, however improbable, must be the truth.

we know that Mr Tan’s birthday is the remaining state: the first September of 1970.

3 thoughts on “Mr Tan’s Birthday Puzzle”

lgc says:

December 29, 2014 at 5:18 am

there is a crucial typo in the listing of the dates it says 5/13 instead of 5/3

LikeLike

1. albertrizaldi says:
  
  December 29, 2014 at 5:37 am
  
  Hi! Thanks for the comment. It is indeed a typo. My mistake.
  
  LikeLiked by 1 person
  
agipras says:

April 14, 2015 at 10:45 am

Luar biasa Albert. Hahaha

LikeLike