Saving the islanders

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Saving the islanders

Postby SPACKlick » Tue Aug 25, 2015 3:54 pm UTC

Based on blue eyes, someone recently asked me the following questions. I wouldn't be surprised if they were somewhere on this forum but a search didn't identify them. In this version the penalty for knowing your eye colour is suicide rather than leaving the island.

Imagine there is a second guru (who is just as trusted as the first guru) who comes and goes from the island. The first guru made their statement in order to remove some politically difficult persons, who all happen to have blue eyes, from the island. The second guru wishes to keep these people alive.

1) If the second guru returns to the island the day of the guru's announcement and hears it what can they do to save the political people?
2) As above but the second guru returns the day after later rather than the next day. (generalise to n days)
3) Is there an announcement the second guru can make which guarantees the first guru's suicide but doesn't risk their own life? (let's pretend this question excludes explicitly telling the first guru "Your eyes are [insert color here]"

1)
Spoiler:
I think grabbing a blue eyed person and saying "your eyes are blue" does it. Everyone can terminate their logic because at the nth level of abstraction nobody expects anyone to leave because the one known blue eyed guy died.
2)
Spoiler:
I feel like the answer is trivially tell n+1 people they have blue eyes, they all commit suicide but I can't seem to prove it.
3)
Spoiler:
There are loads, this question isn't brilliant'y limited but the first I thought of relates to a bastard version of the puzzle where the guru has blue eyes. The second guru says "I can see someone with Green eyes". Even if the second guru has green eyes this doesn't risk their own life because they necessarily exclude themselves from the logic.

User avatar
SDK
Posts: 703
Joined: Thu May 22, 2014 7:40 pm UTC
Location: Canada

Re: Saving the islanders

Postby SDK » Tue Aug 25, 2015 8:46 pm UTC

On 2)
Spoiler:
Isn't it possible to shut the whole thing down at any point just by grabbing a blue eyed person and saying "your eyes are blue" (same as in 1)? If there are 100 blue eyed people on the island, and I'm one of them, I'm sitting there thinking to myself "Those lucky 99! They'll get to leave on the 99th day!" (or, I guess "Those poor 99! Set to die on the 99th day!") It's only after they fail to leave on the 99th day that I realise I have blue eyes. No one expects anyone to leave until the 99th day at the earliest, making the second guru's announcement equivalent anywhere from the 1st to the 98th day. Once it's the 99th day, it's too late to change anything.

You can prove this out with iterations from 2 blue eyed people up. There is no information gain until the final day (obviously, because everyone ends up leaving the same night).


On 3)
Spoiler:
You're solution is to lie? That's not very sporting. :P
The biggest number (63 quintillion googols in debt)

User avatar
SPACKlick
Posts: 195
Joined: Wed Apr 03, 2013 11:25 am UTC

Re: Saving the islanders

Postby SPACKlick » Tue Aug 25, 2015 9:22 pm UTC

SDK wrote:On 2)
Spoiler:
Isn't it possible to shut the whole thing down at any point just by grabbing a blue eyed person and saying "your eyes are blue" (same as in 1)?
Spoiler:
I don't think so. Everyone could see that everyone could see that person had blue eyes and they know that person would have left the same night as them. I can't make it stop in my head by killing one. Killing as many (or one more than as many) would have left that night seems to stop it but I can't make the logic solid.
SDK wrote:On 3)
Spoiler:
You're solution is to lie? That's not very sporting. :P
Spoiler:
In the original puzzle the Guru had green eyes, it's not a lie. The [point being made with this is that the announcers eye colour is irrelevant.

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

Re: Saving the islanders

Postby douglasm » Tue Aug 25, 2015 9:23 pm UTC

SDK wrote:On 2)
Spoiler:
Isn't it possible to shut the whole thing down at any point just by grabbing a blue eyed person and saying "your eyes are blue" (same as in 1)? If there are 100 blue eyed people on the island, and I'm one of them, I'm sitting there thinking to myself "Those lucky 99! They'll get to leave on the 99th day!" (or, I guess "Those poor 99! Set to die on the 99th day!") It's only after they fail to leave on the 99th day that I realise I have blue eyes. No one expects anyone to leave until the 99th day at the earliest, making the second guru's announcement equivalent anywhere from the 1st to the 98th day. Once it's the 99th day, it's too late to change anything.

You can prove this out with iterations from 2 blue eyed people up. There is no information gain until the final day (obviously, because everyone ends up leaving the same night).

Not quite.
Spoiler:
There is, in fact, information gain on every single day - it's just subtle and hard to understand, just like the information originally communicated by the Guru on day 1.

To illustrate this, I'll use the formal logic definition of "common knowledge". Something is common knowledge if everyone knows it, everyone knows that everyone knows it, and everyone knows... ad infinitum. The Guru's statement on day 1 is common knowledge, as are the rules of the puzzle. Anything derived solely from common knowledge is also common knowledge. It is meaningful for a statement to be common knowledge even if the statement is weaker than a known true fact that is not common knowledge.

On day 1, every blue-eyed person has the personal knowledge that:
there are either 99 or 100 blue-eyed people

On day 1, it is common knowledge that:
there is at least 1 blue-eyed person

On day 2, if there were only 1 blue-eyed person he would have left on day 1. This is common knowledge. Combined with previous common knowledge, this means that common knowledge now includes that:
there are at least 2 blue-eyed people

Suppose you wait for day 2 to tell someone he has blue eyes. He would leave, but there would still be common knowledge that someone else had blue eyes, and the solution continues without a hitch.

In order to stop the solution, you have to cut the chain of increases in the common knowledge minimum at a point that it hasn't yet passed. To stop it on day 2, you must tell a minimum of 2 people that they have blue eyes. On day 3, you have to tell at least 3 people. On day N, you have to tell at least N people.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Saving the islanders

Postby Cradarc » Wed Aug 26, 2015 3:33 am UTC

I'm having trouble wrapping my head around the suicide part of the problem. A person simply have to not think about eye colors and they won't die. If the penalty is enforced by other people, how in the world do those people prove that someone is guilty? Now if those people want to commit suicide, the question becomes one about ethics.

Even if I accept the absurdity of the situation:

Spoiler:
1-2) The second guru arrives after the first guru speaks. As proven before, the information provided by the first guru is sufficient to trigger a cascade of knowledge being shared. The second guru cannot remove information from the system, short of erasing people's memories.

3) Assuming everyone knows the second guru cannot lie: "I see one person with green eyes on this island".
It was stated that the first guru was the only person with green eyes. Regardless if the second guru has green eyes or not, if the first guru sees nobody else has green eyes, he/she is dead.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Saving the islanders

Postby Gwydion » Thu Aug 27, 2015 1:21 am UTC

Questions 1-2:
Spoiler:
If the second guru on day k points out at least k blue eyed islanders, that does cut off the chain of logic and keeps anyone else from dying. Cradarc is right that information can't "go away", but one can collapse the possibility spaces in a more desirable fashion. A 4-person example, with all 4 having blue eyes:

On day 1, guru 2 calls out A, and the other 3 have to allow for the possibility that A was the person referred to on the first day. A dies, the others live.

On day 2, the others all know that the existence of at least 2 blue-eyed islanders is common knowledge. Guru 2 calling out A wont stop the rest from dying, because even when A is gone, B-D all know at least one of them has blue eyes, and we proceed as if we are on a 3 person island and it is day 1. Calling out two, however, keeps the others alive. From D's perspective, C could imagine that guru 1 could have been talking about A, who didn't die the night before because A saw B. With A and B dead,, D has no expectation of C dying and therefore doesn't learn anything when C doesn't. (Unsurprisingly, guru 2 naming more than 2 has the same effect on the unnamed islanders, but results in a higher body count.)

Day 3, the same argument can be made but with at least three deaths - D can assume he has brown eyes, and the situation would have played out the same way as if D had blue eyes, so D lives.

Day 4, it's too late to save anyone - they already know their eye color when everyone shows up alive in the morning.
Question 3:
Spoiler:
Nothing guru 2 says can threaten her own existence, except if we allow guru 1 to tell guru 2 a parallel statement in response. For example, if guru 2 tells guru 1 she sees someone with green eyes, guru 1 could reply "Me too." Barring this, guru 2 gains no knowledge about her own eyes by her own statement. This was discussed at length in the original blue eyes thread, when it was asked what would happen if the guru herself had blue eyes. Turns out, the guru still never leaves and the other n-1 blue eyed islanders leave on day n-1.

User avatar
SDK
Posts: 703
Joined: Thu May 22, 2014 7:40 pm UTC
Location: Canada

Re: Saving the islanders

Postby SDK » Thu Aug 27, 2015 2:15 pm UTC

douglasm wrote:
SDK wrote:On 2)
Spoiler:
Isn't it possible to shut the whole thing down at any point just by grabbing a blue eyed person and saying "your eyes are blue" (same as in 1)? If there are 100 blue eyed people on the island, and I'm one of them, I'm sitting there thinking to myself "Those lucky 99! They'll get to leave on the 99th day!" (or, I guess "Those poor 99! Set to die on the 99th day!") It's only after they fail to leave on the 99th day that I realise I have blue eyes. No one expects anyone to leave until the 99th day at the earliest, making the second guru's announcement equivalent anywhere from the 1st to the 98th day. Once it's the 99th day, it's too late to change anything.

You can prove this out with iterations from 2 blue eyed people up. There is no information gain until the final day (obviously, because everyone ends up leaving the same night).

Not quite.
Spoiler:
There is, in fact, information gain on every single day - it's just subtle and hard to understand, just like the information originally communicated by the Guru on day 1.

To illustrate this, I'll use the formal logic definition of "common knowledge". Something is common knowledge if everyone knows it, everyone knows that everyone knows it, and everyone knows... ad infinitum. The Guru's statement on day 1 is common knowledge, as are the rules of the puzzle. Anything derived solely from common knowledge is also common knowledge. It is meaningful for a statement to be common knowledge even if the statement is weaker than a known true fact that is not common knowledge.

On day 1, every blue-eyed person has the personal knowledge that:
there are either 99 or 100 blue-eyed people

On day 1, it is common knowledge that:
there is at least 1 blue-eyed person

On day 2, if there were only 1 blue-eyed person he would have left on day 1. This is common knowledge. Combined with previous common knowledge, this means that common knowledge now includes that:
there are at least 2 blue-eyed people

Suppose you wait for day 2 to tell someone he has blue eyes. He would leave, but there would still be common knowledge that someone else had blue eyes, and the solution continues without a hitch.

In order to stop the solution, you have to cut the chain of increases in the common knowledge minimum at a point that it hasn't yet passed. To stop it on day 2, you must tell a minimum of 2 people that they have blue eyes. On day 3, you have to tell at least 3 people. On day N, you have to tell at least N people.

Spoiler:
I'm not seeing that at all. Every blue eyed person sees 99 blue-eyed people and expects nothing until after the 98th night. How are they learning anything until their expectation is challenged? Night 1 passes, no one leaves the island... yep, there's at least 1 blue eyed person, exactly as I thought. It's not a matter of "I know he knows she knows", it's just a statement of fact that everyone on the island already knew there is at least 1 blue eyed peron - they can see that for themselves!

5 blue-eyed people. Day 1 passes, no one leaves (as everyone expected). Day 2 passes, no one leaves (as everyone expected). Day 3 the second guru tells one of them they have blue eyes. That person commits suicide. What happens to the other four blue-eyed people and why?


Oh shit. I'm falling into exactly the same trap as when I first heard this puzzle. The fact that killing one blue-eyed person on the day of resolution (Day 99) does nothing to stop it means that it does nothing to stop it at any time (except Day 1). If you did the same thing Day 98, I would expect it to do something because I can see 99 blue-eyed people. When nothing happens, I know I have blue eyes. Carry on down.

... Nice. :mrgreen:
The biggest number (63 quintillion googols in debt)

User avatar
Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: Saving the islanders

Postby Vytron » Thu Aug 27, 2015 8:14 pm UTC

Nitpickiness, go!
Spoiler:
SPACKlick wrote:1) If the second guru returns to the island the day of the guru's announcement and hears it what can they do to save the political people?
2) As above but the second guru returns the day after later rather than the next day. (generalise to n days)


I think the first question should ask instead: "If the second guru returns to the island the day of the guru's announcement and hears it what can they say to save the political people?"

Allowing two solutions:

-They tell the person directly they have blue eyes, so they commit suicide.

-They point to someone and exclaim publicly that they have blue eyes (or, if Alan has blue eyes they say "Alan has blue eyes" for the same effect, etc.)

But not this one:

The Second Guru herself goes and kills someone with blue eyes. As long as everyone sees them die, it works the same, and the Guru doesn't need to speak.

So, for the second question, the Guru can come and kill N people where N is the Day Number (though, I guess it allows an interesting variation that could trip some people up: The second Guru is mute and can't talk, and has to find a way to save blue eyed people. So the puzzle solver is expected to find the solution where the Guru has to become an assassin.)


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests