The Muddy Children Puzzle

Several children are playing together outside. After playing they come inside, and their mother says to them, at least one of you has mud on your head. Each child can see the mud on others but cannot see his or her own forehead. She then asks the following question over and over:

can you tell for sure whether or not you have mud on your head?

Assuming that all of the children are intelligent, honest, and answer simultaneously, what will happen? In this assignment, we will analyze this puzzle. To get a feeling for what is being asked, we now figure out what happens if there are two children. First, suppose that exactly one is muddy. When the mother asks the question, the muddy child sees no mud on the other child, and then can conclude that he has mud on his forehead. The other child cannot tell whether or not she has mud on her forehead. Now, suppose that both children have mud on their forehead. When the mother asks the question, neither can determine if they have mud on their foreheads since they see they other the child with mud. So, neither can answer yes to the question. Now, when the mother asks the question the second time, both children realize that they must have mud on their head; if either didn't have mud on their head, then the other child would have seen this and would have been able to answer yes the first time the mother asked the question. So, both answer yes to the second time the question is asked.

In the first three problems, there are three children. In each problem the children know that at least one of them has mud on their forehead but none know exactly how many children have mud on their forehead.

Problem 1. Suppose that there is exactly one child with mud on their forehead. Explain why, after the mother asks the question once, the muddy child is able to answer yes and the other two children cannot answer yes.

Problem 2. Suppose that there is exactly two children with mud on their forehead. Explain why, after the mother asks the question once, no child is able to answer yes. Also explain why, after the mother asks the question a second time, the children with mud on their foreheads can answer yes.

Problem 3. Now suppose that all three children have mud on their foreheads. Explain why each cannot answer yes after the mother asks the question for the first and second time, but that each can answer yes after the third time.

Problem 4. Suppose that there are 4 children playing. Explain why, if there are k muddy children (k can be 1, 2, 3, or 4), that after the k-th time the mother asks the question, the muddy children can answer yes, but that they cannot answer yes before the k-th time the question is asked.