A father comes back to his 100 children and tells them that some of them have mud on their head. The father asks “can you tell if you have mud on your head?” and all respond with “no”. The father then repeats the question until on the 15th turn, some of the children suddenly shouts out yes. How many children are muddy?
This was how we learned induction today.
Assuming that there are 100 children and only a single muddy child. The father asks the question, and the child sees that no one else have mud on their head, so he rationalizes that he must be the muddy child so he responds.
Now assume that there are two muddy children. The father asks the question, the two children sees only one other with mud on his/her head but cannot tell whether or not he himself is muddy, and so everyone replies no. After replying, the two children immediately knows that there are at least 2 children with mud on their head because the other muddy child did not respond with yes (the rest of the children sees two muddy children so they’re still unsure). Since these 2 children can only see one other muddy child, he/she rationalizes that he must also be a muddy child. The father asks the question again and the two responds in the affirmative.
By this line of reasoning, then we know the following to be true when there are n muddy children
- It is common knowledge to everyone that at least n-1 children are muddy. (The n muddy children can only see n-1 muddy children while everyone else sees n)
- If the father asks the question k times, then accumulatively the children would have to deduce that there are at least k muddy children for all k less than n.
- When the children responds with no at the kth turn, then each knows that at least k+1 children are muddy.
Following this line of reasoning, when the (n-1)th turn comes and everyone bellows out no, everyone will know that at least n other children are muddy. But the muddy children themselves can only see (n-1) muddy children, hence they know that they must also be muddy, so comes the nth turn, n muddy children will respond in the affirmative.