12-27-2015, 12:27 AM
Someone posted a riddle on here recently, which reminded me of a problem I heard about a couple of years ago. I couldn't solve this one myself but I really liked the answer. Anyway, here it is:
There is an island full of perfect logicians. 100 of them have have blue eyes, the rest have brown eyes. There are no reflective surfaces on the island and they can't talk to each other for some reason so no one knows what colour eyes they have. There is a boat that comes to the island every night to take blue eyed people away from the island but if a brown eyed person tries to board, the boat will never return and no one will get off the island. The islanders are told that there is at least one person on the island with blue eyes. When do the blue eyed people leave the island?
The second last sentence that states that there is at least one blue eyed person on the island seems redundant since I already said that there are 100 blue eyed people on the island but the reason this is included in the posing of the question will become clear. The solution relies on mathematical induction. Consider a statement P(n) in terms of some integer n. To prove P(n) using induction, you show that it's true for the base case (in this case, the base case is n = 1). Then, you assume that P(k) is true for some n greater than or equal to 1 and prove that, if this is the case, P(k + 1) is also true. So, we know that P(1) is true, so then P(2) must be true, and then P(3) must be true, etc. So, P(n) is true for all n greater than or equal to one.
In this problem, forget that there are 100 blue eyed people on the island. Instead, think of the case where there is only one blue eyed person on the island (who knows that there is at least one blue eyed person on the island). Then think of the case where we have two blue eyed people, three, etc., and a pattern will emerge. Then, construct a statement P(n): "If there are n blue eyed people on the island, they will leave on the ____th night." (It will be obvious what to put in the blank space). Then, prove P(n) by induction.
I probably didn't explain this very well. There are better explanations elsewhere on the internet. I just thought I'd share this because I like the solution. It doesn't seem very practical but, in setting the scene, we have said that these people are perfect logicians so it'd be no bother to them.
There is an island full of perfect logicians. 100 of them have have blue eyes, the rest have brown eyes. There are no reflective surfaces on the island and they can't talk to each other for some reason so no one knows what colour eyes they have. There is a boat that comes to the island every night to take blue eyed people away from the island but if a brown eyed person tries to board, the boat will never return and no one will get off the island. The islanders are told that there is at least one person on the island with blue eyes. When do the blue eyed people leave the island?
The second last sentence that states that there is at least one blue eyed person on the island seems redundant since I already said that there are 100 blue eyed people on the island but the reason this is included in the posing of the question will become clear. The solution relies on mathematical induction. Consider a statement P(n) in terms of some integer n. To prove P(n) using induction, you show that it's true for the base case (in this case, the base case is n = 1). Then, you assume that P(k) is true for some n greater than or equal to 1 and prove that, if this is the case, P(k + 1) is also true. So, we know that P(1) is true, so then P(2) must be true, and then P(3) must be true, etc. So, P(n) is true for all n greater than or equal to one.
In this problem, forget that there are 100 blue eyed people on the island. Instead, think of the case where there is only one blue eyed person on the island (who knows that there is at least one blue eyed person on the island). Then think of the case where we have two blue eyed people, three, etc., and a pattern will emerge. Then, construct a statement P(n): "If there are n blue eyed people on the island, they will leave on the ____th night." (It will be obvious what to put in the blank space). Then, prove P(n) by induction.
I probably didn't explain this very well. There are better explanations elsewhere on the internet. I just thought I'd share this because I like the solution. It doesn't seem very practical but, in setting the scene, we have said that these people are perfect logicians so it'd be no bother to them.
![[-]](https://gayspeak.com/images/duende_v3_local/collapse.png)
