1
$\begingroup$

I was trying to solve the common knowledge problem, but am not sure if my proof is accurate.

Here is a rough statement of the problem : 'An island consists of $k$ people with green eyes, all islanders can identify the eye colors of other islanders, but cannot identify their own eye color (there are no reflective surfaces on the island), they are also not allowed to communicate in any way with other islanders. Everyday, if an islander deduces, with absolute certainty, the color of his own eyes, he leaves the island at night.'

I am trying to prove that if there are $k$ islanders, and a third party enters the island and makes the statement 'at least one of you $k$ islanders has green eyes', that after $k$ days, all islanders will leave the island.

I will denote 'person $m$' with $m$ and the proposition 'at least one of you $k$ people has green eyes' will be denoted $P_k$. Furthermore, the connective 'knows' will be denoted $\leadsto$.

The inductive hypothesis I will use in my solution of the common knowledge problem is:

'If there is common knowledge of $P_l$ among the set of $l$ green eyed people, $S_l = \{1,2,...,l\}$, then after $l$ days, all $l$ people will leave the island, for all $l$ less than $k$. The proof for the base case $k=2$ has been omitted.

Before the message 'at least one of you $k$ people has green eyes' is delivered, there is only $k-1$th order knowledge. So by $k-1$th order knowledge, I mean that:

$1 \leadsto 2 \leadsto ... k-2 \leadsto k-1 \leadsto P_k $,

and we have this for all permutations of subsets of order $k-1$ of $\{1,2,..,k\}$

But we do not have:

$1 \leadsto 2 \leadsto ... k-2 \leadsto k-1 \leadsto k \leadsto P_k$

for any permutation of $\{1,2,...,k\}$

However, after the announcement, we gain:

$1 \leadsto 2 \leadsto ... k-2 \leadsto k-1 \leadsto k \leadsto P_k$

for all permutations of $\{1,2,...,k\}$

Now let us consider the subset of people:

$S_{k-1} = \{1,2,...,k-1\}$ and denote the proposition 'at least one person among $S_{k-1}$ has green eyes', $P_{k-1}$

It is clear that:

$1 \leadsto 2 \leadsto ... \leadsto k-2 \leadsto P_{k-1}$

However, we do not have:

$1 \leadsto 2 \leadsto ... \leadsto k-2 \leadsto k-1 \leadsto P_{k-1}$

for any permutation of $\{1,2,...,k-1\}$

(that is, we do not have common knowledge within the set $S_{k-1}$)

This is symmetrically true for any subset of order $k-1$ of the set of people $\{1,2,...,k\}$

Now we will show that after day $1$,that is, on day $2$ we will gain common knowledge within the set $S_{k-1}$ (and in fact, that we will also gain common knowledge in ANY subset of order $k-1$ of $\{1,2,...,k\}$ , by symmetry)

I will introduce another notation in place of the word 'think' (note this is different to 'knows', as it is speculative)

'think' - $\rightharpoonup$

Before day $1$, it is possible that:

$\displaystyle 1 \rightharpoonup 2 \rightharpoonup 3 ... \rightharpoonup k-1 \rightharpoonup \neg P_{k-1}$

where $\neg P_{k-1}$ is 'not $P_{k-1}$' or simply 'everyone in $S_{k-1}$ does NOT have green eyes'

Translating this to english, I am saying that it is possible, immediately after the announcement, that 'Person $1$ thinks that Person $2$ thinks that Person $3$ thinks that ... Person $k-1$ thinks that everyone in the set $\{1,2,...,k-1\}$ does NOT have green eyes'.

But since we have $1 \leadsto 2 \leadsto ... k-2 \leadsto k-1 \leadsto k \leadsto P_k$

after day $1$, that is, on day $2$, since person $k$ has remained on the island, $1$ must realize that $2$ must realize that .... $k-2$ must realize that $k-1$ must realize that $P_{k-1}$ is true, that is it is not possible for Person $1$ to think that Person $2$ thinks that ... Person $k-1$ thinks that $P_{k-1}$ is false (that everyone in the set $\{1,2,...,k-1\}$ does NOT have green eyes), as person $k$ has not left after day $1$, and we know that Person $1$ knows that Person $2$ knows that ... Person $k-1$ knows that Person $k$ knows that at least one person in $\{1,2,...,k\}$ has green eyes.

Thus after day $1$, $S_{k-1}$ gains common knowledge, (as the above argument can symmetrically be applied to all permutations of $\{1,2,...,k-1\}$) and so $k-1$ days after day $1$, at the end of day $k$, by the inductive hypothesis, all of $S_{k-1}$ leave the island, and similarly person $k$ will leave the island, as he too belongs to a set containing $k-1$ people that gains common knowledge after day $1$ ( again , by symmetry ).

My issue with this is that while I know that $1 \rightharpoonup 2 \rightharpoonup 3 ... \rightharpoonup k-1 \rightharpoonup \neg P_{k-1}$ is not possible after $1$ day passes and person $k$ remains on the island, as we also have the fact that $1 \leadsto 2 \leadsto ... k-2 \leadsto k-1 \leadsto k \leadsto P_k$, I am not sure how to 'formally prove' this, although after considering cases with $k=3,4,5$ I think an inductive argument may work.

Thank you

$\endgroup$
  • $\begingroup$ You might want to explain what the problem is to those who haven't heard it. $\endgroup$ – fleablood Jun 6 '16 at 6:14
  • $\begingroup$ noted, I'll edit my answer $\endgroup$ – Aneesh Jun 6 '16 at 6:17
  • 1
    $\begingroup$ math.stackexchange.com/questions/489308/… $\endgroup$ – zyx Jun 6 '16 at 8:58
  • $\begingroup$ Thank you for the link, I've read through several posts, but am still at odds with whether or not my solution in particular is valid, as it seems slightly different to the conventional solution (where one islander reasons that if he himself is not green eyed, then after $k-1$ days, all other islanders must leave the island, however after $k-1$ days, since this does not happen, the islander reasons he must indeed be green eyed, and leaves on the $k$th day). I think my solution is viable, but would appreciate verification from someone who knows more about this than me. $\endgroup$ – Aneesh Jun 6 '16 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.