Muddy Children, Other Logic Puzzles, and （泥泞的孩子,其他的逻辑谜题,）.pdf

Muddy Children, Other Logic Puzzles, and Temporal Dynamic Epistemic Logic 1 Muddy Children Three brilliant children go to the park to play. When their father comes to find them, he sees that two of them have mud on their foreheads. He then says, “At least one of you has mud on your forehead”, and then asks, “Do you know if you have mud on your forehead?” The children simultaneously respond, “No”. The father repeats his question, “Do you know if you have mud on your forehead?” and this time the two children with muddy foreheads simultaneously answer, “Yes, I have!” while the re- maining child answers, “No”. 2 Claim If there are n children, k of whom are muddy, then the k children will announce that they are muddy after the father repeats his question k times. All we care about n is that n ≥ k . 3 Induction Base case: Suppose 1 child was muddy. After the father an- nounces, “At least one of you has mud on your forehead”: • What does the muddy child know? That he is the muddy one • What do the clean children consider possible? Either 1 or 2 muddy children total. When the father asks, “ Do you know if you have mud on your forehead?”, the muddy child will respond, “Yes, I am!”. 4 Just another step to build intuition: Suppose 2 children were muddy. After the father announces, “At least one of you has mud on your fo