Talk:Induction puzzles

Josephine's problem

In general, if there are n unfaithful husbands, each of their wives will believe there to be n-1 and will expect to hear a gunshot at midnight on the n-1th day. When they don't, they know their own husband was the nth.

Isn't the above statement incorrect? Gunshot will always be heard on the second day for any case other than n<2. For n =>2 the wives will always be aware of n-1 unfaithful husbands on the first day, hence any wife with an unfaithful husband will always know their husband is the nth unfaithful one on the second day.— Preceding unsigned comment added by Dmsdemon (talk • contribs) 07:45, 24 March 2006

That's not quite true - the wives of unfaithful husbands will be aware of n-1 unfaithful husbands and the wives of faithful husbands will be aware of n. If a wife from one group discusses numbers with a wife from the other group, they will both immediately know the fidelity of their own husbands, which breaks the rules. So we can assume they don't discuss numbers at all.

This means that no wife knows what n is. By your suggested logic, every wife would kill her husband on the second day, whether faithful or not. The only way they can tell which group they're in is by figuring out the inductive logic and waiting to see if anything happens on day n-1.

Note that the wives of faithful husbands are waiting too, but they're waiting to see if anything happens on day n because they know about one extra unfaithful husband. So when they hear the gunshots on night n, they know they're safe.

Any attempt to shortcut the wait time requires discussion that would give away the answer and break the rules. CupawnTae 09:37, 22 October 2006 (UTC)

I fail to understand how this puzzle can really be solved for n>3. If every wife in the kingdom knows that at least 3 husbands are unfaithful, they know that there will be no gunshot on day 1. It makes no sense to expect a gunshot or to think someone expects one.--Iv (talk) 15:52, 19 July 2015 (UTC)

If there are 4 unfaithful husbands in the kingdom, i.e., n = 4, then each wife of an unfaithful husband expects that there are at least 3 unfaithful husbands. If n = 3, they would hear 3 gunshots on day 3. Since they would not (as n is not 3), they know that there must be a 4th unfaithful husband, and that it is theirs. --Joshua Issac (talk) 23:39, 31 July 2015 (UTC)

Wording in third solution

I changed the wording in the solution to the third problem because it made heavy use of the word 'repeated' to mean 'seen' or 'appeared.' For instance, seeing a color "repeated once" means it is seen twice because one must have already seen the color in order for it to be repeated. --Ddawn23 12:42, 19 November 2006 (UTC)

The solution to the third problem also has many wording/grammar issues starting with the italicized portion. Someone with more knowledge of the logic problem should probably rewrite that part. --Larryhl45 (talk) 07:28, 19 July 2015 (UTC)

Flaw in first solution

I added a note to the first solution to explain the flaw in its statement. For people who aren't too worried about it, I left the statement and the answer completely unchanged, and only added a final note after the other comments in the answer.Frentz 08:07, 22 October 2007 (UTC)

I think that the original solution was incorrect, as it missed an important element in the puzzle and didn't in fact solve both questions presented (what will he say and why?). I changed the answer. Acertain (talk) 22:09, 26 February 2013 (UTC)

There is a flaw in the answer. The first man could be wearing a white or blue hat, there is no certainty that they are all wearing blue hats — Preceding unsigned comment added by 145.100.112.108 (talk) 08:15, 7 February 2019 (UTC)

Merger proposal

I propose to merge Muddy children puzzle into Induction puzzles. The puzzle does not seem to be fundamentally different from other induction puzzles, and would be best served by being presented in the context of the similar puzzles in this article. Sneftel (talk) 08:23, 19 February 2020 (UTC)

Correct, I also thought about it. But, Induction puzzles (20 views per day) has to be restructured first. And, also Hat puzzle (100 views per day) has to be cleaned up merged with the Induction puzzles.--Geysirhead (talk) 08:57, 21 February 2020 (UTC)

Yeah, I wish I'd noticed your merge proposal before starting my own. I agree with that ordering -- hat+induction is going to be more involved than muddy+result, and will affect the structure. Sneftel (talk) 09:07, 21 February 2020 (UTC)

Good, I restructured the Induction puzzles. Now, there are a slots for Muddy children puzzle and Hat puzzles.--Geysirhead (talk) 09:16, 21 February 2020 (UTC)

Muddy Children Puzzle

The description of the Muddy children puzzle and the solution can be greatly clarified:

A group of children is told that some of them have muddy faces. Each child can see the faces of the others, but cannot tell if his or her own face is muddy. The children are told that those with muddy faces must step forward, but any child with a clean face who steps forward will be punished. At the count of three, every child who believes that his or her face is muddy must step forward simultaneously; any child who signals to another in any way will be punished. If any child with a muddy face has not stepped forward, the process will be repeated.

If, and only if, each child has and knows each of the others to have perfect logic, all children with muddy faces (X) will step forward together on turn X. The children have different information, depending on whether their own faces are muddy or not. Each member of X sees X-1 muddy faces, and knows that those children will step forward on turn X-1 if they are the only muddy faces. When that does not occur, each member of X knows that he or she is also a member of X, and steps forward on turn X. Each non-member of X sees X muddy faces, and will not expect anyone to step forward until turn X:

1. If there is only one muddy face (A), A sees no muddy faces, and knows the number of muddy faces is either zero or 1. Because there must be at least one muddy face, A knows that his or her own face must be muddy and will step forward on the first turn. Each of the other children sees A's muddy face, so they know that the number of muddy faces is either 1 or 2. They lack enough information on turn one to rule out that their own face is also muddy.
2. If there are two muddy faces (A,B), A and B each see only one muddy face, and know that the number of muddy faces is either 1 or 2. After turn one, A and B know that the number of muddy faces cannot be 1; B knows that if A must have seen a second muddy face, which can only be B's, and vice versa. A and B step forward together on turn two. The other children, seeing two muddy faces, know that the number of muddy faces must be 2 or 3. They lack enough information on turn two to rule out that their own face is also muddy.
3. If there are three muddy faces (A,B,C), each of them knows that the number of muddy faces is 2 or 3, and seeing that the other two did not step forward on turn two, would step forward together on the third turn, etc.

Rickwodz (talk) 17:19, 18 December 2020 (UTC)