My write-up of the "Blue Eyes" solution (SPOILER A

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: My write-up of the "Blue Eyes" solution (SPOILER A

Arklarp, take a step away from the nested hypotheticals for a second. That exercise is to demonstrate what information the Guru's statement provides, but you have to agree with the answer to the puzzle first.

You agree that if there are only 3 blue-eyed people on the island, that they would leave on the 3rd night, right?

So, for an islander who only sees 3 blue-eyed people ("Blues"), and those three do not leave on the third night, what is the logical conclusion? Obviously there are not 3 Blues on the island (they would have left). But each of the Blues sees only 3 other Blues. The only other possible number there could be is 4, so there must be 4 Blues. Each of them would discover this at the same time - on the fourth day - and therefore leave at the same time: on the fourth night.

Now if there is an islander who sees 4 Blues, and they do not leave on the fourth night, then there must be 5 Blues, right? So if there are 5 Blues, they all leave on the fifth night.

What happens for the 100 case is, on the surface level, very simple:
Either there are 99 Blues, or there are 100 Blues.
If there are 100 Blues, then I am a Blue.
If there are 99 Blues, they will leave on the 99th night.
They did not leave on the 99th night, therefore there are not 99 Blues.
Therefore, there are 100 Blues.
Therefore, I am a Blue.

In fact, this is the way it works for any number of Blues:

Either there are X Blues, or there are X+1 Blues.
Etc.

Once you accept this answer, then you can get on to trying to understand the nested hypotheticals. Before that, thinking about the hypotheticals, and trying to wrap your head around all of these "I know that she knows that he knows" chains, won't actually make the inductive answer make any more sense to you.

simplelogic1
Posts: 1
Joined: Tue Jan 05, 2016 5:19 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

without a penalty for guessing wrong... if a person stays on the island more than two days...they're a fool. 3 they might be an optimist and 7 if they were an anomaly. Logically speaking if the majority of the people around had blue and brown eyes you would guess one of the two in the first two days. If you were an optimist you might think you had the same color as the one individual who was somehow a leader. Ultimately (logically speaking) there are only seven naturally occurring eye colors, not including variations. So the most anyone should spend on the island is a week.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

There is no penalty for guessing wrong because there is no guessing in the first place. The problem does not state that people that correctly state their eye color leave, but that people that know their eye color leave.

Incidentally, the problem also does not state that people want to leave. Or that they want to stay. Only that those who figure out their eye color do, in fact, leave.

PTGFlyer
Posts: 12
Joined: Wed Jan 13, 2016 6:15 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

I saw this and just got COMPLETELY nerd-sniped.

PTGFlyer
Posts: 12
Joined: Wed Jan 13, 2016 6:15 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

It seems like this would break down at large numbers, but my brain isn't running fast enough right now.

PTGFlyer
Posts: 12
Joined: Wed Jan 13, 2016 6:15 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

I think that I need a step-by-step of the 100 case, because it seems that the logic breaks down once you hit 6, because everybody sees 5 and knows that everybody else sees at least 4.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: My write-up of the "Blue Eyes" solution (SPOILER A

PTGFlyer wrote:I think that I need a step-by-step of the 100 case, because it seems that the logic breaks down once you hit 6, because everybody sees 5 and knows that everybody else sees at least 4.

Have you checked through the last 35 pages of step-by-step explanations?
There's no such thing as a funny sig.

rmsgrey
Posts: 3513
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

PTGFlyer wrote:I think that I need a step-by-step of the 100 case, because it seems that the logic breaks down once you hit 6, because everybody sees 5 and knows that everybody else sees at least 4.

...but the hypothetical people seeing 4 only know that everyone sees at least 3, and the hypothetical hypothetical people only seeing 3 only know that everyone sees at least 2, and so on.

It's easier to prove what happens by ignoring the question of what people know about what other people know about what a third person knows about what a fourth... and just focusing on the induction (actually, that's true for pretty much any proof by induction - and is the reason proof by induction is a useful technique in the first place - induction doesn't prove the result directly; instead it proves that you could construct a proof for any finite case.

Anyway, here, if you know that in the situation where, say, 99 islanders have blue eyes, they'll all leave on the 99th day, and that all the islanders know this, then when there are a bunch of islanders wondering whether there are 99 or 100 blue-eyed islanders, they'll find out on day 99 which it is (either people leave, or they don't) and if it turns out there aren't 99 blue-eyed islanders, then they'll know to leave on day 100. If you don't know about the 99 blue-eyed islander case, then you can settle it by invoking the 98 blue-eyed islander case, and so on until you get to the 2 blue-eyed islander case being determined by the 1 blue-eyed islander case, which is easily proven.

BedderDanu
Posts: 39
Joined: Tue Jan 14, 2014 6:18 am UTC

Re: My write-up of the "Blue Eyes" solution (SPOILER A

PTGFlyer wrote:I think that I need a step-by-step of the 100 case, because it seems that the logic breaks down once you hit 6, because everybody sees 5 and knows that everybody else sees at least 4.

I think I can break down the 6 case. But first, lets go through the basic logic:

Why 1 works:
Day 1
I see no one with blue eyes.
I am told at least one person has blue eyes.
I must have blue eyes.
I should leave.

Why 2 works:
Day 1
I see one person with blue eyes.
I am told at least one person has blue eyes.
If I don't have blue eyes, they will leave today.

Day 2
They didn't leave.
They must have seen one other person with blue eyes.
That must be me.
We should leave.

why 3-5 works:
Day 2-4, respectively
I see 2-4 people with blue eyes.
If I don't have blue eyes, they will leave on day 2-4.
I know this because I can show that anyone can prove that everyone knows that everyone can see someone that doesn't know about blue eyes.
This contradicts the guru...Which starts off the chain.
Because people didn't leave on day 1-3, they will leave today.

Day 3-5, respectively
They didn't leave.
They must have seen one other person with blue eyes.
That must be me.
We should leave.

Why Day 6 is "Problematic"
I can show that anyone can prove that everyone knows that everyone can tell that everyone can see someone with blue eyes.
This seems to imply that the guru added no additional knowledge, relative to the 5 person case.

Why it doesn't matter
Day 5
I see 5 people with blue eyes.
If I don't have blue eyes, they will leave on day 5
I know this because 5 blue eyes works, as above.

Day 6
They didn't leave.
They must have seen one other person with blue eyes.
That must be me.
We should leave.

Does that help explain it? Even if you can start doing weird logic chains at 6 people, that you can't really do with 5, it doesn't matter, because 5 works, so 6 works, so 7 works, so 8 works... etc.

the problem is that the only reason 1 person doesn't leave on day 1 because there are 2+ people with blue eyes. Which means that the only reason 2 people don't leave on day 2 is because there are 3+ people with blue eyes. Which means that the only reason 3 people don't leave on day 3 is because 4+ people have blue eyes.

Of course, person 1 won't leave until they know that there is at least 1 person with blue eyes, which means that nothing will happen until the guru says anything. Even if you know that anyone can prove that everyone knows that everyone sees someone who can see blue eyes.