The "muddy children" puzzle Imagine m children playing together. n children, 1 < n <=m get mud on their foreheads. Each can see the mud on the forehead of everyone but him/herself. In comes the father, who says, "At least one of you has mud on your forehead." The father then procedes to repeat the following question: "Do you know if you have mud on your forehead?" Assume that the children tell the truth and answer the question simultaneously. How many times must the father ask the question before each child knows whether they have mud on their forehead? Provide a conjecture and prove it by induction. n = # of muddy children m = # of children, m >= n NO = "I don't know whether I have or don't have mud" YES = "Yes, I know I have mud or don't have mud" n Rounds of questions "Do you have mud on your forehead?" P(n) --- -------------------------------------------------------------- 1 R1: 1 yes, rest no; R2: all yes 2 2 R1: all no; R2: 2 yes, rest no; R3: all yes 3 3 R1: all no; R2: all no; R3: 3 yes, rest no; R4: all yes 4 4 all no; all no; all no; 4 yes, rest no; all yes 5 ... looks like n+1. Basis. P(1) = yes;yes = 2 = 1+1; true. IH. Assume true for P(k) and any P(i), i >= 1 and < k: P(k) takes k+1 rounds for all children to know; e.g., k children know when k questions are asked and all children know when k+1 questions are asked. IS. Show that P(k+1) takes k+2 rounds. For k+1, k muddy children see k other children with mud. Let's say we are in round k+1. By IH, if there were only k muddy children, then all children would already know and we would be done in k+1 rounds. But since k muddy children see k other muddy children and we are not done, then those k children know they must have mud in round k+1. Once they know that, in round k+2, all the remaining children know they do not have mud.