Mixing
Muddy Children Puzzle (when more than 2 kids are muddy)
$begingroup$
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.
discrete-mathematics logic
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
$endgroup$
add a comment |
$begingroup$
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.
discrete-mathematics logic
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
$endgroup$
3
$begingroup$
I can find links on google for the "Muddy Children Problem", but can you add a statement of the problem to your question? Even if this problem is famous (and I hadn't actually heard of it until now), it's good to explicitly state what you're asking about.
$endgroup$
– Kevin Long
Feb 2 at 16:33
$begingroup$
I understand, thanks and +1 for explicitly reminding that.
$endgroup$
– ultimate cause
Feb 2 at 16:40
add a comment |
$begingroup$
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.
discrete-mathematics logic
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
$endgroup$
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.
discrete-mathematics logic
discrete-mathematics logic
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
edited Feb 2 at 16:43
ultimate cause
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
asked Feb 2 at 16:28
ultimate causeultimate cause
1289
1289
3
$begingroup$
I can find links on google for the "Muddy Children Problem", but can you add a statement of the problem to your question? Even if this problem is famous (and I hadn't actually heard of it until now), it's good to explicitly state what you're asking about.
$endgroup$
– Kevin Long
Feb 2 at 16:33
$begingroup$
I understand, thanks and +1 for explicitly reminding that.
$endgroup$
– ultimate cause
Feb 2 at 16:40
add a comment |
3
$begingroup$
I can find links on google for the "Muddy Children Problem", but can you add a statement of the problem to your question? Even if this problem is famous (and I hadn't actually heard of it until now), it's good to explicitly state what you're asking about.
$endgroup$
– Kevin Long
Feb 2 at 16:33
$begingroup$
I understand, thanks and +1 for explicitly reminding that.
$endgroup$
– ultimate cause
Feb 2 at 16:40
3
3
$begingroup$
I can find links on google for the "Muddy Children Problem", but can you add a statement of the problem to your question? Even if this problem is famous (and I hadn't actually heard of it until now), it's good to explicitly state what you're asking about.
$endgroup$
– Kevin Long
Feb 2 at 16:33
$begingroup$
I can find links on google for the "Muddy Children Problem", but can you add a statement of the problem to your question? Even if this problem is famous (and I hadn't actually heard of it until now), it's good to explicitly state what you're asking about.
$endgroup$
– Kevin Long
Feb 2 at 16:33
$begingroup$
I understand, thanks and +1 for explicitly reminding that.
$endgroup$
– ultimate cause
Feb 2 at 16:40
$begingroup$
I understand, thanks and +1 for explicitly reminding that.
$endgroup$
– ultimate cause
Feb 2 at 16:40
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This is where it's important that the children are super-hyper-intelligent: i.e. that they are able to deduce everything we can about the problem during the time that they are being asked. (This is definitely an unrealistic assumption, but pop mathematics problems are full of such simplifications for the purpose of demonstrating the mathematical ideas.)
Going by the context of your question, you've understood how two children with muddy heads can eventually say Yes. The important point is that Child A understands how two children with muddy heads can eventually say Yes, just like you do. Therefore, when Child A sees two other children with muddy heads, A expects that if those two are the only such children, they will say Yes on the second round.
They didn't say Yes on the second round. Therefore, A learns that the two children they can see with muddy heads aren't the only two muddy children. Therefore A learns that they are also muddy.
The same idea - that every kid is expecting the solution to this problem - answers your other objection. If $k$ kids are muddy, each clean kid knows that there are either $k$ muddy kids not including themself or $k+1$ kids including themself. When the $k$ muddy kids accept that they are muddy on the $k^{th}$ round, which they can only do if there are only $k$ muddy kids, every clean kid learns that there are only $k$ muddy kids and therefore that they are themselves clean. This is why none of them will claim to be muddy even if they are asked a ${k+1}^{th}$ time.
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
$endgroup$
$begingroup$
Thanks for answering but this is exactly my problem. The predicate ". At least one of you are muddy head" has to be true and that is why all this round business is there. And in order for that to be true, if Child A sees that the other two are actually muddy heads, third or fourth round does not changes a thing. So, there is no point in suspecting one's own muddiness. I seem to have very minuscule IQ compared to these kids :-)
$endgroup$
– ultimate cause
Feb 2 at 18:14
1
$begingroup$
You're only one step behind the kids. Imagine if you were Kid A, standing there looking at the two kids with muddy heads. You know there's only two kids with muddy heads, you've worked through the maths (and trust them to have done the same) and you know exactly how those two kids, the only two kids with muddy heads, will work it out and announce that they are the only two muddy kids on the second round.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
Then the second round comes. And neither kid speaks up.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
How the hell did that happen? You know how two muddy kids can work it out and speak up, and you know that both of the kids who are actually muddy are capable of doing that. There must be something wrong with your assumption. But how could there be more than two muddy kids when you can only see two?
$endgroup$
– Chessanator
Feb 2 at 18:28
1
$begingroup$
There must be a third muddy kid, and it must be you. Therefore you now know you're muddy and can say so during the third round.
$endgroup$
– Chessanator
Feb 2 at 18:29
|
show 1 more comment
$begingroup$
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?
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
$endgroup$
$begingroup$
Awsome reasoning, I did not think this approach is possible.This answer is worth a bow down. Would learn this one too. Thanks and +1.
$endgroup$
– ultimate cause
Feb 3 at 3:50
$begingroup$
@ultimatecause Glad you like the answer :) It's so strange: you see how the inductive proof works, and yet you're left with this paradox I try to highlight in my answer ... it took me while to figure out how to resolve it and thereby really understand the 'guts' of this problem.
$endgroup$
– Bram28
Feb 3 at 4:16
$begingroup$
I too was laughing at myself after I got that mistake in my argument. People like me hear the joke at party but laugh only when they reach home :)
$endgroup$
– ultimate cause
Feb 3 at 7:39
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3097469%2fmuddy-children-puzzle-when-more-than-2-kids-are-muddy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is where it's important that the children are super-hyper-intelligent: i.e. that they are able to deduce everything we can about the problem during the time that they are being asked. (This is definitely an unrealistic assumption, but pop mathematics problems are full of such simplifications for the purpose of demonstrating the mathematical ideas.)
Going by the context of your question, you've understood how two children with muddy heads can eventually say Yes. The important point is that Child A understands how two children with muddy heads can eventually say Yes, just like you do. Therefore, when Child A sees two other children with muddy heads, A expects that if those two are the only such children, they will say Yes on the second round.
They didn't say Yes on the second round. Therefore, A learns that the two children they can see with muddy heads aren't the only two muddy children. Therefore A learns that they are also muddy.
The same idea - that every kid is expecting the solution to this problem - answers your other objection. If $k$ kids are muddy, each clean kid knows that there are either $k$ muddy kids not including themself or $k+1$ kids including themself. When the $k$ muddy kids accept that they are muddy on the $k^{th}$ round, which they can only do if there are only $k$ muddy kids, every clean kid learns that there are only $k$ muddy kids and therefore that they are themselves clean. This is why none of them will claim to be muddy even if they are asked a ${k+1}^{th}$ time.
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
$endgroup$
$begingroup$
Thanks for answering but this is exactly my problem. The predicate ". At least one of you are muddy head" has to be true and that is why all this round business is there. And in order for that to be true, if Child A sees that the other two are actually muddy heads, third or fourth round does not changes a thing. So, there is no point in suspecting one's own muddiness. I seem to have very minuscule IQ compared to these kids :-)
$endgroup$
– ultimate cause
Feb 2 at 18:14
1
$begingroup$
You're only one step behind the kids. Imagine if you were Kid A, standing there looking at the two kids with muddy heads. You know there's only two kids with muddy heads, you've worked through the maths (and trust them to have done the same) and you know exactly how those two kids, the only two kids with muddy heads, will work it out and announce that they are the only two muddy kids on the second round.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
Then the second round comes. And neither kid speaks up.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
How the hell did that happen? You know how two muddy kids can work it out and speak up, and you know that both of the kids who are actually muddy are capable of doing that. There must be something wrong with your assumption. But how could there be more than two muddy kids when you can only see two?
$endgroup$
– Chessanator
Feb 2 at 18:28
1
$begingroup$
There must be a third muddy kid, and it must be you. Therefore you now know you're muddy and can say so during the third round.
$endgroup$
– Chessanator
Feb 2 at 18:29
|
show 1 more comment
$begingroup$
This is where it's important that the children are super-hyper-intelligent: i.e. that they are able to deduce everything we can about the problem during the time that they are being asked. (This is definitely an unrealistic assumption, but pop mathematics problems are full of such simplifications for the purpose of demonstrating the mathematical ideas.)
Going by the context of your question, you've understood how two children with muddy heads can eventually say Yes. The important point is that Child A understands how two children with muddy heads can eventually say Yes, just like you do. Therefore, when Child A sees two other children with muddy heads, A expects that if those two are the only such children, they will say Yes on the second round.
They didn't say Yes on the second round. Therefore, A learns that the two children they can see with muddy heads aren't the only two muddy children. Therefore A learns that they are also muddy.
The same idea - that every kid is expecting the solution to this problem - answers your other objection. If $k$ kids are muddy, each clean kid knows that there are either $k$ muddy kids not including themself or $k+1$ kids including themself. When the $k$ muddy kids accept that they are muddy on the $k^{th}$ round, which they can only do if there are only $k$ muddy kids, every clean kid learns that there are only $k$ muddy kids and therefore that they are themselves clean. This is why none of them will claim to be muddy even if they are asked a ${k+1}^{th}$ time.
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
$endgroup$
$begingroup$
Thanks for answering but this is exactly my problem. The predicate ". At least one of you are muddy head" has to be true and that is why all this round business is there. And in order for that to be true, if Child A sees that the other two are actually muddy heads, third or fourth round does not changes a thing. So, there is no point in suspecting one's own muddiness. I seem to have very minuscule IQ compared to these kids :-)
$endgroup$
– ultimate cause
Feb 2 at 18:14
1
$begingroup$
You're only one step behind the kids. Imagine if you were Kid A, standing there looking at the two kids with muddy heads. You know there's only two kids with muddy heads, you've worked through the maths (and trust them to have done the same) and you know exactly how those two kids, the only two kids with muddy heads, will work it out and announce that they are the only two muddy kids on the second round.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
Then the second round comes. And neither kid speaks up.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
How the hell did that happen? You know how two muddy kids can work it out and speak up, and you know that both of the kids who are actually muddy are capable of doing that. There must be something wrong with your assumption. But how could there be more than two muddy kids when you can only see two?
$endgroup$
– Chessanator
Feb 2 at 18:28
1
$begingroup$
There must be a third muddy kid, and it must be you. Therefore you now know you're muddy and can say so during the third round.
$endgroup$
– Chessanator
Feb 2 at 18:29
|
show 1 more comment
$begingroup$
This is where it's important that the children are super-hyper-intelligent: i.e. that they are able to deduce everything we can about the problem during the time that they are being asked. (This is definitely an unrealistic assumption, but pop mathematics problems are full of such simplifications for the purpose of demonstrating the mathematical ideas.)
Going by the context of your question, you've understood how two children with muddy heads can eventually say Yes. The important point is that Child A understands how two children with muddy heads can eventually say Yes, just like you do. Therefore, when Child A sees two other children with muddy heads, A expects that if those two are the only such children, they will say Yes on the second round.
They didn't say Yes on the second round. Therefore, A learns that the two children they can see with muddy heads aren't the only two muddy children. Therefore A learns that they are also muddy.
The same idea - that every kid is expecting the solution to this problem - answers your other objection. If $k$ kids are muddy, each clean kid knows that there are either $k$ muddy kids not including themself or $k+1$ kids including themself. When the $k$ muddy kids accept that they are muddy on the $k^{th}$ round, which they can only do if there are only $k$ muddy kids, every clean kid learns that there are only $k$ muddy kids and therefore that they are themselves clean. This is why none of them will claim to be muddy even if they are asked a ${k+1}^{th}$ time.
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
$endgroup$
This is where it's important that the children are super-hyper-intelligent: i.e. that they are able to deduce everything we can about the problem during the time that they are being asked. (This is definitely an unrealistic assumption, but pop mathematics problems are full of such simplifications for the purpose of demonstrating the mathematical ideas.)
Going by the context of your question, you've understood how two children with muddy heads can eventually say Yes. The important point is that Child A understands how two children with muddy heads can eventually say Yes, just like you do. Therefore, when Child A sees two other children with muddy heads, A expects that if those two are the only such children, they will say Yes on the second round.
They didn't say Yes on the second round. Therefore, A learns that the two children they can see with muddy heads aren't the only two muddy children. Therefore A learns that they are also muddy.
The same idea - that every kid is expecting the solution to this problem - answers your other objection. If $k$ kids are muddy, each clean kid knows that there are either $k$ muddy kids not including themself or $k+1$ kids including themself. When the $k$ muddy kids accept that they are muddy on the $k^{th}$ round, which they can only do if there are only $k$ muddy kids, every clean kid learns that there are only $k$ muddy kids and therefore that they are themselves clean. This is why none of them will claim to be muddy even if they are asked a ${k+1}^{th}$ time.
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
answered Feb 2 at 16:53
ChessanatorChessanator
2,3751412
2,3751412
$begingroup$
Thanks for answering but this is exactly my problem. The predicate ". At least one of you are muddy head" has to be true and that is why all this round business is there. And in order for that to be true, if Child A sees that the other two are actually muddy heads, third or fourth round does not changes a thing. So, there is no point in suspecting one's own muddiness. I seem to have very minuscule IQ compared to these kids :-)
$endgroup$
– ultimate cause
Feb 2 at 18:14
1
$begingroup$
You're only one step behind the kids. Imagine if you were Kid A, standing there looking at the two kids with muddy heads. You know there's only two kids with muddy heads, you've worked through the maths (and trust them to have done the same) and you know exactly how those two kids, the only two kids with muddy heads, will work it out and announce that they are the only two muddy kids on the second round.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
Then the second round comes. And neither kid speaks up.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
How the hell did that happen? You know how two muddy kids can work it out and speak up, and you know that both of the kids who are actually muddy are capable of doing that. There must be something wrong with your assumption. But how could there be more than two muddy kids when you can only see two?
$endgroup$
– Chessanator
Feb 2 at 18:28
1
$begingroup$
There must be a third muddy kid, and it must be you. Therefore you now know you're muddy and can say so during the third round.
$endgroup$
– Chessanator
Feb 2 at 18:29
|
show 1 more comment
$begingroup$
Thanks for answering but this is exactly my problem. The predicate ". At least one of you are muddy head" has to be true and that is why all this round business is there. And in order for that to be true, if Child A sees that the other two are actually muddy heads, third or fourth round does not changes a thing. So, there is no point in suspecting one's own muddiness. I seem to have very minuscule IQ compared to these kids :-)
$endgroup$
– ultimate cause
Feb 2 at 18:14
1
$begingroup$
You're only one step behind the kids. Imagine if you were Kid A, standing there looking at the two kids with muddy heads. You know there's only two kids with muddy heads, you've worked through the maths (and trust them to have done the same) and you know exactly how those two kids, the only two kids with muddy heads, will work it out and announce that they are the only two muddy kids on the second round.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
Then the second round comes. And neither kid speaks up.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
$begingroup$
How the hell did that happen? You know how two muddy kids can work it out and speak up, and you know that both of the kids who are actually muddy are capable of doing that. There must be something wrong with your assumption. But how could there be more than two muddy kids when you can only see two?
$endgroup$
– Chessanator
Feb 2 at 18:28
1
$begingroup$
There must be a third muddy kid, and it must be you. Therefore you now know you're muddy and can say so during the third round.
$endgroup$
– Chessanator
Feb 2 at 18:29
$begingroup$
Thanks for answering but this is exactly my problem. The predicate ". At least one of you are muddy head" has to be true and that is why all this round business is there. And in order for that to be true, if Child A sees that the other two are actually muddy heads, third or fourth round does not changes a thing. So, there is no point in suspecting one's own muddiness. I seem to have very minuscule IQ compared to these kids :-)
$endgroup$
– ultimate cause
Feb 2 at 18:14
$begingroup$
Thanks for answering but this is exactly my problem. The predicate ". At least one of you are muddy head" has to be true and that is why all this round business is there. And in order for that to be true, if Child A sees that the other two are actually muddy heads, third or fourth round does not changes a thing. So, there is no point in suspecting one's own muddiness. I seem to have very minuscule IQ compared to these kids :-)
$endgroup$
– ultimate cause
Feb 2 at 18:14
1
1
$begingroup$
You're only one step behind the kids. Imagine if you were Kid A, standing there looking at the two kids with muddy heads. You know there's only two kids with muddy heads, you've worked through the maths (and trust them to have done the same) and you know exactly how those two kids, the only two kids with muddy heads, will work it out and announce that they are the only two muddy kids on the second round.
$endgroup$
– Chessanator
Feb 2 at 18:25
$begingroup$
You're only one step behind the kids. Imagine if you were Kid A, standing there looking at the two kids with muddy heads. You know there's only two kids with muddy heads, you've worked through the maths (and trust them to have done the same) and you know exactly how those two kids, the only two kids with muddy heads, will work it out and announce that they are the only two muddy kids on the second round.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
1
$begingroup$
Then the second round comes. And neither kid speaks up.
$endgroup$
– Chessanator
Feb 2 at 18:25
$begingroup$
Then the second round comes. And neither kid speaks up.
$endgroup$
– Chessanator
Feb 2 at 18:25
1
1
$begingroup$
How the hell did that happen? You know how two muddy kids can work it out and speak up, and you know that both of the kids who are actually muddy are capable of doing that. There must be something wrong with your assumption. But how could there be more than two muddy kids when you can only see two?
$endgroup$
– Chessanator
Feb 2 at 18:28
$begingroup$
How the hell did that happen? You know how two muddy kids can work it out and speak up, and you know that both of the kids who are actually muddy are capable of doing that. There must be something wrong with your assumption. But how could there be more than two muddy kids when you can only see two?
$endgroup$
– Chessanator
Feb 2 at 18:28
1
1
$begingroup$
There must be a third muddy kid, and it must be you. Therefore you now know you're muddy and can say so during the third round.
$endgroup$
– Chessanator
Feb 2 at 18:29
$begingroup$
There must be a third muddy kid, and it must be you. Therefore you now know you're muddy and can say so during the third round.
$endgroup$
– Chessanator
Feb 2 at 18:29
|
show 1 more comment
$begingroup$
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?
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
$endgroup$
$begingroup$
Awsome reasoning, I did not think this approach is possible.This answer is worth a bow down. Would learn this one too. Thanks and +1.
$endgroup$
– ultimate cause
Feb 3 at 3:50
$begingroup$
@ultimatecause Glad you like the answer :) It's so strange: you see how the inductive proof works, and yet you're left with this paradox I try to highlight in my answer ... it took me while to figure out how to resolve it and thereby really understand the 'guts' of this problem.
$endgroup$
– Bram28
Feb 3 at 4:16
$begingroup$
I too was laughing at myself after I got that mistake in my argument. People like me hear the joke at party but laugh only when they reach home :)
$endgroup$
– ultimate cause
Feb 3 at 7:39
add a comment |
$begingroup$
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?
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
$endgroup$
$begingroup$
Awsome reasoning, I did not think this approach is possible.This answer is worth a bow down. Would learn this one too. Thanks and +1.
$endgroup$
– ultimate cause
Feb 3 at 3:50
$begingroup$
@ultimatecause Glad you like the answer :) It's so strange: you see how the inductive proof works, and yet you're left with this paradox I try to highlight in my answer ... it took me while to figure out how to resolve it and thereby really understand the 'guts' of this problem.
$endgroup$
– Bram28
Feb 3 at 4:16
$begingroup$
I too was laughing at myself after I got that mistake in my argument. People like me hear the joke at party but laugh only when they reach home :)
$endgroup$
– ultimate cause
Feb 3 at 7:39
add a comment |
$begingroup$
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?
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
$endgroup$
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?
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
edited Feb 3 at 3:49
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
answered Feb 2 at 23:00
Bram28Bram28
64.5k44793
64.5k44793
$begingroup$
Awsome reasoning, I did not think this approach is possible.This answer is worth a bow down. Would learn this one too. Thanks and +1.
$endgroup$
– ultimate cause
Feb 3 at 3:50
$begingroup$
@ultimatecause Glad you like the answer :) It's so strange: you see how the inductive proof works, and yet you're left with this paradox I try to highlight in my answer ... it took me while to figure out how to resolve it and thereby really understand the 'guts' of this problem.
$endgroup$
– Bram28
Feb 3 at 4:16
$begingroup$
I too was laughing at myself after I got that mistake in my argument. People like me hear the joke at party but laugh only when they reach home :)
$endgroup$
– ultimate cause
Feb 3 at 7:39
add a comment |
$begingroup$
Awsome reasoning, I did not think this approach is possible.This answer is worth a bow down. Would learn this one too. Thanks and +1.
$endgroup$
– ultimate cause
Feb 3 at 3:50
$begingroup$
@ultimatecause Glad you like the answer :) It's so strange: you see how the inductive proof works, and yet you're left with this paradox I try to highlight in my answer ... it took me while to figure out how to resolve it and thereby really understand the 'guts' of this problem.
$endgroup$
– Bram28
Feb 3 at 4:16
$begingroup$
I too was laughing at myself after I got that mistake in my argument. People like me hear the joke at party but laugh only when they reach home :)
$endgroup$
– ultimate cause
Feb 3 at 7:39
$begingroup$
Awsome reasoning, I did not think this approach is possible.This answer is worth a bow down. Would learn this one too. Thanks and +1.
$endgroup$
– ultimate cause
Feb 3 at 3:50
$begingroup$
Awsome reasoning, I did not think this approach is possible.This answer is worth a bow down. Would learn this one too. Thanks and +1.
$endgroup$
– ultimate cause
Feb 3 at 3:50
$begingroup$
@ultimatecause Glad you like the answer :) It's so strange: you see how the inductive proof works, and yet you're left with this paradox I try to highlight in my answer ... it took me while to figure out how to resolve it and thereby really understand the 'guts' of this problem.
$endgroup$
– Bram28
Feb 3 at 4:16
$begingroup$
@ultimatecause Glad you like the answer :) It's so strange: you see how the inductive proof works, and yet you're left with this paradox I try to highlight in my answer ... it took me while to figure out how to resolve it and thereby really understand the 'guts' of this problem.
$endgroup$
– Bram28
Feb 3 at 4:16
$begingroup$
I too was laughing at myself after I got that mistake in my argument. People like me hear the joke at party but laugh only when they reach home :)
$endgroup$
– ultimate cause
Feb 3 at 7:39
$begingroup$
I too was laughing at myself after I got that mistake in my argument. People like me hear the joke at party but laugh only when they reach home :)
$endgroup$
– ultimate cause
Feb 3 at 7:39
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3097469%2fmuddy-children-puzzle-when-more-than-2-kids-are-muddy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
I can find links on google for the "Muddy Children Problem", but can you add a statement of the problem to your question? Even if this problem is famous (and I hadn't actually heard of it until now), it's good to explicitly state what you're asking about.
$endgroup$
– Kevin Long
Feb 2 at 16:33
$begingroup$
I understand, thanks and +1 for explicitly reminding that.
$endgroup$
– ultimate cause
Feb 2 at 16:40