Imagine $n$ children playing together. The mother of these children has told them that if they get dirty there will be severe consequences. So, of course, each child wants to keep clean, but each would love to see the others get dirty. Now it happens during their play that some of the children, say $k$ of them, get mud on their foreheads. Each can see the mud on others but not on his own forehead. So, of course, no one says a thing. Along comes the father, who says, "At least one of you has mud on your forehead,” thus expressing a fact known to each of them before he spoke (if $k > 1$). The father then asks the following question, over and over: "Does any of you know whether you have mud on your own forehead?” Assuming that all the children are perceptive, intelligent, truthful and that they answer simultaneously, what will happen?
I am trying to prove by induction, that for the first $k-1$ times that the question is asked, all children say No. On the $k$th question, all those with muddy foreheads answer Yes.
The case when $k=1$ is trivial. So I take $k=2$ as my base case. Suppose the muddy children are $A$ and $B$. After the first question, both say No, due to mud on the other child's forehead. However, when $A$ says No, $B$ (being intelligent) realizes that $B$ must have mud on his own forehead. Similarly for $A$. So, $A$ and $B$ both say Yes after the next (second) round of questioning. This completes the base case.
Inductive hypothesis: Suppose for $1 \le k \le m$, the statement holds. To complete the induction, we show it holds for $m+1$.
I'm not sure how to complete the induction step. Any ideas? Would appreciate any help, thanks so much!
Best Answer
The induction step: Suppose there are $m+1$ muddy children. After $m$ rounds of questioning, all the muddy children would have answered Yes, had there been only $m$ muddy children (induction hypothesis). However, that did not happen. Moreover, each one of the muddy children sees $m$ other muddy children. So, they conclude that they themselves must also be muddy. Hence, in the next round of questioning, the $m+1$ muddy children all say Yes.
I had posted this as an "Update" in one of the edits of my question but decided to include it as an answer after the discussion in the comments, for completeness.