Steve: One guy is obvious and two guys is also easy to figure out. Think of adding the third guy as a spectator watching the two guys. Once the two guys do nothing when they should, the third guy figures out his eye color. After that add a fourth guy watching the three guys etc. This inductive proof gets you up to any number and tells you how long it takes. Also note, that even though you add people sequentially it really doesn't matter who the "new" spectator is. This symmetry is actually the reason why everyone leaves at the same time.
I'll repeat my other question (refined), since understanding it is good for your understanding of the original question.
Two of the people (let's call them Rym and Scott), upon looking one another in the eyes, realise they could not bear to be seperated. How, in keeping with the rules, should Rym ensure with absolute certainty that they will remain alive and in the same place. More specifically, I want the "lowest damage" solution.
If you understand the solution to the original question, this one shouldn't be hard.
Well, basically when you see 99 persons with blue eyes and they don't leave on the 99th night you know you have blue eyes. This is exactly for the same reason you know when you see three people with blue eyes and wen they don't leave on the third night.
The human brain is not suited to handle the large number (I suspect, but am not sure of, roughly 100! = 100*99*98*...*1) conditional "if he does this, then..." logical branches needed to tackle the 100 blue eyes problem with brute force. Induction lets you skip this. Once you prove that something works for 1 and that if it works for n then it'll work for n+1, you're set.
Your write up of cases 1-4 is, of course, not rigorous proof by induction (neither is my write up) but I think you can already convince yourself that going from 2 to 3 is no different than going from 3 to 4. Once you do that, you can just keep going 4->5->6-> etc, and finally come to the conclusion that for 99 blue eyed guys it'll take 99 nights.
I know the solution to the puzzle and it makes sense at low numbers. (Only one person with blue eyes and I see no one with blue eyes? Must be me!). As you add to it though it stops making sense. In part because the people can not communicate and the solution requires the people to communicate with each other.
Failure to board the ferry is a form of communication, but one that is not only acceptable but essential to the solution.
Also, I'll write up the generic (k)->(k+1) case, just to be proper. If we take B(n) as the statement that if there are n blue-eyed people, they will all leave on the nth day, we must prove that B(k) implies B(k+1).
Let's say a blue-eyed person looks at everyone else and sees k people with blue eyes. This person sees two cases: (1) I do not have blue eyes. Hence there are k people with blue eyes, and B(k) means that they will all leave on the kth day (2) I have blue eyes After the kth day has passed and obviously no-one has left, the person must conclude that we have gone into case (2), and hence all of the k+1 blue-eyed people will leave on the k+1th day.
Proving B(1) is straightforward - if a person sees no-one with blue eyes, then the person observing must themselves have blue eyes, and will leave on the first day. By induction, since B(1) is true and B(k)->B(k+1), B(n) is true for all positive integers n.
Anyone have an answer to my previous question (earlier posts)? It's easy if you understand the solution to the original.
Well, wouldn't all the brown-eyed people try to leave on the 99th night as well, since they don't know that there are only 100 blue eyed people?
The blue-eyed people can see 99 blue-eyed people, so they leave on the 100th night once it has been proven to each of them that they have blue eyes. Each brown-eyed person can see 100 blue-eyed people, so if no-one left for the first 100 nights, they would in fact leave on the 101st. However, since all the blue-eyes left on the 100th night, the brown-eyes stay back.
Here's the answer to my other question, since I got bored:- < spoiler>All they have to do is disable one blue eyed person. If that blue eyed person cannot leave, or cannot find out whether other people have left, no-one can leave< /spoiler>
Cheese: Wrong, you asked for a minimum damage solution. Minimum damage solution is that they each take out one of their eyes and look at it. As a bonus they get to leave the island immediately afterwards without having to wait for all the other chumps who are too wimpy to do this as well.
Comments
Two of the people (let's call them Rym and Scott), upon looking one another in the eyes, realise they could not bear to be seperated.
How, in keeping with the rules, should Rym ensure with absolute certainty that they will remain alive and in the same place.
More specifically, I want the "lowest damage" solution.
If you understand the solution to the original question, this one shouldn't be hard.
The human brain is not suited to handle the large number (I suspect, but am not sure of, roughly 100! = 100*99*98*...*1) conditional "if he does this, then..." logical branches needed to tackle the 100 blue eyes problem with brute force. Induction lets you skip this. Once you prove that something works for 1 and that if it works for n then it'll work for n+1, you're set.
Your write up of cases 1-4 is, of course, not rigorous proof by induction (neither is my write up) but I think you can already convince yourself that going from 2 to 3 is no different than going from 3 to 4. Once you do that, you can just keep going 4->5->6-> etc, and finally come to the conclusion that for 99 blue eyed guys it'll take 99 nights.
Also, I'll write up the generic (k)->(k+1) case, just to be proper.
If we take B(n) as the statement that if there are n blue-eyed people, they will all leave on the nth day, we must prove that B(k) implies B(k+1).
Let's say a blue-eyed person looks at everyone else and sees k people with blue eyes. This person sees two cases:
(1) I do not have blue eyes. Hence there are k people with blue eyes, and B(k) means that they will all leave on the kth day
(2) I have blue eyes
After the kth day has passed and obviously no-one has left, the person must conclude that we have gone into case (2), and hence all of the k+1 blue-eyed people will leave on the k+1th day.
Proving B(1) is straightforward - if a person sees no-one with blue eyes, then the person observing must themselves have blue eyes, and will leave on the first day.
By induction, since B(1) is true and B(k)->B(k+1), B(n) is true for all positive integers n.
Anyone have an answer to my previous question (earlier posts)? It's easy if you understand the solution to the original.
EDIT: And it's not an assumption.
Each brown-eyed person can see 100 blue-eyed people, so if no-one left for the first 100 nights, they would in fact leave on the 101st. However, since all the blue-eyes left on the 100th night, the brown-eyes stay back.
Here's the answer to my other question, since I got bored:-
< spoiler>All they have to do is disable one blue eyed person. If that blue eyed person cannot leave, or cannot find out whether other people have left, no-one can leave< /spoiler>