Today, I am going to present before you a very general version of classical problems involving knowledge about knowledge. Fondly dubbed as "The Suicides of Dot-Town", the problem is stated in the following manner:
Each resident of Dot-Town carries a red or blue dot on his forehead, but if he ever figures out what colour it is, he kills himself. Each day, all the residents gather in the town hall and count the number of red and blue dots they see. However, they do not communicate their counts to one another. One day, a stranger comes and tells them something non-trivial about the number of blue dots. Prove that the aftermath of this event is that, eventually, every resident kills himself.
[Note: Here, “non-trivial” means that there is some number of blue dots for which the statement would not have been true. Thus, through his statement, the stranger is effectively letting the residents of Dot-Town deduce a set $K$ such that the number of blue dots cannot belong to $K$.]
An elegant proof devised by Peter Winkler, which uses backward induction on the number of disallowed numbers of blue dots, follows:
Suppose that the population of Dot-Town is $n$.
Now, let us assume that the stranger announces that the number of blue dots does not belong to the set $K$, where $K$ is some non-empty subset of the numbers from $0$ to $n$.
When $|K| = n−1$, the base case of the induction applies.
Though each resident is oblivious to the colour of his own dot, if he sees $y$ number of blue dots in the gathering, he will know that the actual number of blue dots has to be either $y$ (if he is red-dotted) or $y+1$ (if he is blue-dotted). However, if $|K| = n−1$, then each resident can immediately eliminate one of these possibilities and deduce the colour of his own dot, which leads him to commit suicide. Thus, the entire population of the town gets wiped out immediately.
Otherwise, let us consider what happens when $|K| < n−1$.
Suppose the actual number of blue dots is $j$. So then, when all the residents gather in the town hall, the red-dotted residents see $j$ blue dots while the blue-dotted residents see only $j−1$.
Now, if $j−1 \in K$, then the blue-dotted residents will be able to deduce the colour of the dot on their foreheads, and hence, they will all kill themselves on the first night after the stranger's announcement. On noting the absence of their blue-dotted counterparts the following morning, the remaining residents (if any) will deduce that their spots are red, and dispense with themselves the same night.
Similarly, if $j+1 \in K$, then the red-dotted residents will be able to deduce the colour of the dot on their foreheads, and hence, they will all kill themselves on the first night after the stranger's announcement. On noting the absence of their red-dotted counterparts the following morning, the remaining residents (if any) will deduce that their spots are blue, and dispense with themselves at night.
If no one kills himself on the first night, then the following morning, everyone can deduce that neither $j−1$ nor $j+1$ is in $K$, which means the actual number of blue dots is not within one of any number in $K$. This effectively increases the number of forbidden numbers of blue dots, and so the induction hypothesis can now be applied by expanding the set $K$ to include numbers that are exactly one away from those already in $K$.
Note that the proof also shows that $n$ nights suffice; further, that the full $n$ nights are needed only when either $K = \{0\}$ and all the dots are blue, or $K = \{n\}$ and all the dots are red, or $n \leq 2$.
Each resident of Dot-Town carries a red or blue dot on his forehead, but if he ever figures out what colour it is, he kills himself. Each day, all the residents gather in the town hall and count the number of red and blue dots they see. However, they do not communicate their counts to one another. One day, a stranger comes and tells them something non-trivial about the number of blue dots. Prove that the aftermath of this event is that, eventually, every resident kills himself.
[Note: Here, “non-trivial” means that there is some number of blue dots for which the statement would not have been true. Thus, through his statement, the stranger is effectively letting the residents of Dot-Town deduce a set $K$ such that the number of blue dots cannot belong to $K$.]
An elegant proof devised by Peter Winkler, which uses backward induction on the number of disallowed numbers of blue dots, follows:
Suppose that the population of Dot-Town is $n$.
Now, let us assume that the stranger announces that the number of blue dots does not belong to the set $K$, where $K$ is some non-empty subset of the numbers from $0$ to $n$.
When $|K| = n−1$, the base case of the induction applies.
Though each resident is oblivious to the colour of his own dot, if he sees $y$ number of blue dots in the gathering, he will know that the actual number of blue dots has to be either $y$ (if he is red-dotted) or $y+1$ (if he is blue-dotted). However, if $|K| = n−1$, then each resident can immediately eliminate one of these possibilities and deduce the colour of his own dot, which leads him to commit suicide. Thus, the entire population of the town gets wiped out immediately.
Otherwise, let us consider what happens when $|K| < n−1$.
Suppose the actual number of blue dots is $j$. So then, when all the residents gather in the town hall, the red-dotted residents see $j$ blue dots while the blue-dotted residents see only $j−1$.
Now, if $j−1 \in K$, then the blue-dotted residents will be able to deduce the colour of the dot on their foreheads, and hence, they will all kill themselves on the first night after the stranger's announcement. On noting the absence of their blue-dotted counterparts the following morning, the remaining residents (if any) will deduce that their spots are red, and dispense with themselves the same night.
Similarly, if $j+1 \in K$, then the red-dotted residents will be able to deduce the colour of the dot on their foreheads, and hence, they will all kill themselves on the first night after the stranger's announcement. On noting the absence of their red-dotted counterparts the following morning, the remaining residents (if any) will deduce that their spots are blue, and dispense with themselves at night.
If no one kills himself on the first night, then the following morning, everyone can deduce that neither $j−1$ nor $j+1$ is in $K$, which means the actual number of blue dots is not within one of any number in $K$. This effectively increases the number of forbidden numbers of blue dots, and so the induction hypothesis can now be applied by expanding the set $K$ to include numbers that are exactly one away from those already in $K$.
Note that the proof also shows that $n$ nights suffice; further, that the full $n$ nights are needed only when either $K = \{0\}$ and all the dots are blue, or $K = \{n\}$ and all the dots are red, or $n \leq 2$.
No comments:
Post a Comment