[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums

100 islanders logic puzzle

Posted By: Stein Kulseth
Date: Friday, 21 August 2009, at 2:13 p.m.

In Response To: 100 islanders logic puzzle (bob koca)

After the oracle has spoken, the statement P(N): "If the number of blue-eyed people are N, they will all kill themselves exactly on the Nth morning" can be proved true by induction.

Induction step: If P(N) is true, then any person who sees N other people with blue eyes will be able to deduce his own color on day N. If they commit suicide, they were the only N, and he himself must have green eyes. If they do not, there must be at least one more blue-eyed person, and that can only be himself. So he will kill himself the next morning on day N+1, as will the other N who is essentially in the same position, and able to make the same deductions.

Thus we see that if P(N) is true then so is P(N+1)

Initial step, P(1): It is obviously true that a blue-eyed person that sees no other blue-eyed person will deduce that he is the one mentioned and he will kill himself on day 1.

So initial step is true and the induction step is true, thus P(N) holds for all N, so for P(10) it is proven that they all commit suicide on day 10.

(There are however a couple of caveats ... mentioned in another mail)

Messages In This Thread

 

Post Response
Your Name:
Your E-Mail Address:
Subject:
Message:

If necessary, enter your password below:

Password:
 

 

[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums is maintained by Stick with WebBBS 5.12.