This is about famous Muddy Children puzzle mentioned in section 1.1. I am trying to understand the significance of rounds when number of muddy children are 3 or more than 3.
http://www.cs.cornell.edu/courses/cs6764/2012sp/book1.pdf
Assumption is that each kid answers NO unless she is sure about herself being muddy and YES otherwise. Let there be more than 3 kids in total out of which exactly 3 kids are muddy.
My dilemma is as follows :
-
Problem is symmetric to all the muddy kids.
When the father asks for first time, all the three muddy kids know for sure that there are 2 or 3 muddy kids (3rd could be herself) and they say NO. Also the father's statement that "At least one of you has muddy head" satisfies the situation. All the kids could see that there are at least 2 kids (unsure about their own status) are muddy. So they would answer NO for themselves. If A,B and C denote the muddy children, for A, (lets say, first round) hearing NO from the other two should not have any effect on her answer second round, because, she would think that B sees mud on C head and C sees mud on B head and therefore both of them answered NO. Thus A should repeat NO in second round too. Since the problem is symmetric given this reasoning, irrespective of number of rounds, all the kids should always answer NO when there are 3 or more muddy kids. I am unable to understand how the enumeration happens with the repeated rounds. I am missing some point here. -
Going by the "correct logic" given in books, is it possible if the father repeats the question even after all muddy kids accepted and said YES, some of clean kids to answer YES wrongly. The proof for the problem has been given using induction, assuming that after kth round, k-1 kids would have accepted them being muddy. But due to problem given above, I don't see the induction to work.
This may be a stupid question, but is not for homework. I presented the link for reference purposes only. Your help is appreciated.
Best Answer
Don;t feel bad: your confusion is a very common one!
Imagine this: suppose there are $56$ kids, and $37$ of them have mud on their forehead. Then, according to the solution, the father has to repeat the question $37$ times before the muddy kids will know that they have mud on their heads!
Well, that seems awfully strange indeed: what is it that the children are learning during the first $35$ times the father asks the question? I mean, it's not as if they don't know that there are any muddy kids. Clearly, there are plenty of muddy kids to go around, and so they all know that there are plenty of muddy kinds. Moreover, they all know that they know this: even if I am one of the muddy kids, I see $36$ other muddy kids, and so I know that all the other kids see at least $35$ muddy kids!
So again, why exactly is it that the kids are waiting until the father has asked the question so many times?! Sure, by induction we are told that we have to wait until the question has been asked as many times as the number of muddy kids I see before I know I am a muddy kid ... but why wait so long? We all know that father is going to ask the question, many, many times ... during which we basically all pick our noses and are completely bored. So really, what's the point of father asking over and over, when we all know exactly that that is going to happen?
In fact, it seems like the kids don't learn anything when father asks the question for, say, the $14$-th time and yet again nothing happens. It seems as if there is no information gained: they all knew nothing was going to happen at this point, and indeed we know this for all of the first $35$ question or so. And if we don't learn anything during any of the times that father asks the question, why is it that we have to go through this event? That is, if we don't learn anything, then why would the situation before the $14$-th be any different from the situation after the $14$-th question?!
So, here's the thing: it turns out that all the kids do learn something during each and every question! For example, before father has asked any questions yet, but after he did point out that there is at least one muddy kid, the following things are all true:
1.1) they all know there is at least one muddy kid (well, duh, they see lots!)
1.2) they all know that they all know that there is at least one muddy kid (again, duh, they see lots!)
1.3) they all know that they all know that they all know that there is at least one muddy kid
...
and in fact this goes on indefinitely ... because by saying that there is at least one muddy kid, this piece of information has become common knowledge
OK, what else is true? Well:
2.1 They all know there are at least two muddy kids
2.2 They all know that they all know that there are at least two muddy kids (again, with $37$ muddy kids, they can all comfortably know this of each other)
...
OK, but does this go on indefinitely? That is, is it common knowledge that there are at least two muddy kids? And, bizarrely, NO!, it is not common knowledge that there are at least two muddy kids!
What?!? With so many muddy kids, how can that be? They all know there are at least two muddy kids, and they all know that they all know that! What more would you want for this to be common knowledge?!
Well, think about this: let's say the muddy kids are $a_1$ through $a_{37}$. Now, does $a_1$ know that $a_2$ knows that $a_3$ knows that $a_4$ .... that $a_{36}$ knows that $a_{37}$ knows that there are at least two muddy kids? No! Because father said so, we have that $a_1$ know that $a_2$ knows that $a_3$ knows that $a_4$ .... that $a_{36}$ knows that $a_{37}$ knows that there is at least one muddy kid, but before the first time father asks the quesrtion, it is not true that $a_1$ know that $a_2$ knows that $a_3$ knows that $a_4$ .... that $a_{36}$ knows that $a_{37}$ knows that there are at least two muddy kids!
Why not? Well, think about this: $a_1$ does not know whether he/she is muddy, and so, thinking about what $a_2$ can know, $a_1$ has to consider the possibility that $a_2$ only sees $35$ muddy kids, even as $a_1$ sees $36$ muddy kids.
So, we have that:
$a_1$ knows that there are at least $36$ muddy kinds
... but we can't do any better than:
$a_1$ knows that $a_2$ knows that there are at least $35$ muddy kinds
But then $a_2$ (in $a_1$'s mind!), when considering what $a_3$ knows, has to consider the possibility that $a_2$ is not muddy, and that is within the possibility that $a_1$ is not muddy either, meaning that $a_3$ would see only $34$ muddy kids. So, at best we can say that:
$a_1$ knows that $a_2$ knows that $a_3$ knows that there are at least $34$ muddy
but again, it is not true that:
$a_1$ knows that $a_2$ knows that $a_3$ knows that there are at least $35$ muddy
OK ... you see where this is going. As $a_1$ is trying to figure out what $a_2$ can figure out what $a_3$ can figure out ...., you end up with:
$a_1$ knows that $a_2$ knows that $a_3$ knows that ... that $a_{36}$ knows there is at least $1$ muddy kid
And now you also see why it is so crucially important that father says that there is at least $1$ kid, because father would have said that, it would not be true that:
$a_1$ knows that $a_2$ knows that $a_3$ knows that ... that $a_{36}$ knows that $a_{37}$ knows that there is at least $1$ muddy kid
But now that father has made it public or common knowledge, we can say that:
$a_1$ knows that $a_2$ knows that $a_3$ knows that ... that $a_{36}$ knows that $a_{37}$ knows that there is at least $1$ muddy kid
OK, but before father has asked the first question, it is not true that:
$a_1$ knows that $a_2$ knows that $a_3$ knows that ... that $a_{36}$ knows there are at least $2$ muddy kids
But after father has asked the question the first time, and nothing happens, they can now all infer that there must at least be $2$ muddy kids ... and since they can all reason about each other, the fact that there are at least two muddy kids becomes common knowledge!
But, befoire the second question, it is not yet common knowledge that there are at least $3$ muddy kids. in particular, after the first question, it has now become true that:
$a_1$ knows that $a_2$ knows that $a_3$ knows that ... that $a_{36}$ knows there are at least $2$ muddy kids
before the second question, it is not yet true that:
$a_1$ knows that $a_2$ knows that $a_3$ knows that ... that $a_{36}$ knows there are at least $3$ muddy kids
but that does become true after the second question!
See how this works?