Rethinking Blue Eyes - A Logic Puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Fri Jul 17, 2015 9:38 pm UTC

This is a variation of The Blue Eyes Puzzle by Randall Munroe some dude on the street in Boston named Joel, which poses the following differences:

1. Everyone on the island is superrational, if they played the Prisoner Dilemma, all of them would cooperate.
2. The guru says "I can see someone who has blue eyes. I can see everyone is superrational." So this is common knowledge.
3. Before they're put on the island, they're able to speak as much as they like with each other, make a plan, set rules, and anything that would let them escape earlier. However, once on the island, they're not able to communicate, which means they're not able to help other people realize what's their eye color (for instance, patting on the shoulder the people with blue eyes wouldn't be allowed.)

With these changes, are these people able to realize what is their eye color and leave the island sooner?

Solution
Spoiler:
No. Being superrational and having common knowledge about it, and being able to formulate a plan doesn't help them to get off the island earlier.


Discussion
Spoiler:
Comes from this thread.

Cauchy wrote:You can't shortcut a day, because each day the islanders all learn actual new information during the public reveal that no one left.


Superrational beings know that all other people will not leave the first 90 days, they will gain no information because they already had that information, so they should be able to skip them. There should be N amount of days that is safe to skip, mainly, because it's safe to skip 1 day.

douglasm wrote:Suppose that you have some superrational rule that, given a number N of blue-eyed people that you see, you skip D = f(N) days. For this rule to be worth anything, there has to be at least one value for N where f(N) > 0. For this rule to work for the single blue-eyed person case, f(0) and f(1) must be 0. Therefore, there are at least two distinct output values for f(N). Therefore, there exists an N where f(N) != f(N+1).

Consider the case of N where f(N) != f(N+1). This can be true in two different ways, either f(N) < f(N+1) or f(N) > f(N+1).

Consider f(N) < f(N+1). Suppose that there are, in fact, N+1 blue-eyed people on the island. The people with blue eyes will see N blue-eyed people and will skip f(N) days. Everyone else (with brown eyes) will see N+1 blue-eyed people and will skip f(N+1) days. The brown-eyed people are waiting for day N+1 - f(N+1). The blue-eyed people are waiting for day N - f(N). Because f(N) < f(N+1), the former will be at or before the latter, and all the brown-eyed people will conclude that they have blue eyes and attempt to leave. Puzzle failed.

So, there cannot be any N where f(N) < f(N+1). This means f(N) cannot increase. Combine this with the known value f(1) = 0, which is required for the single blue-eyes case, and f(N) cannot exceed 0 for any positive N.

It doesn't matter how clever your rule is, even if everyone's superrational or discussed it ahead of time, if there is any case where your rule has you skipping a positive number of days then there is a case where your rule causes the solution to fail.


Well, you said my previous attempt failed only with 750 people. If it worked with less than 750 or more than 750, then superrational beings should be able to make a plan to escape early, they just need to abort the plan when they're close to this number.

--------

Okay, if superrational beings can't leave earlier than perfect logicians (i.e. superrationality changes nothing, unlike in the Prisoner's Dilemma) I'd like to understand why, to me, the main difference is that superrational beings knows what everyone else know without having to wait.

Suppose that after the guru talked, some random superrational being talked, and said:

"I see at least 2 people with blue eyes!"

Would superrational beings then be able to leave one day sooner? Because, if they see 99, they see at least 2, and know that everyone sees at least 2, so they pretend that someone yelled that and leave one day earlier.

Again, superrational beings would not do that, because doing so was arbitrary, but if one is able to find a strategy that leaves earlier, that would work if the prisoners were able to communicate and leave the island, then it could be used by superrational beings without needing to communicate, because they know such a strategy exists and know all other people are using it.

Actually, this thread has had enough of this. I'm traveling back in time to the beginning of this post and instead of writing it here I'll do it into a new thread focused on discussing a variant of Blue Eyes with superrational beings.

Done.


Variation:

Since it's possible to form a plan that makes it likely for people to leave, but it's not for certain, this variation where the prisoners wouldn't risk their life is presented:

they're all prisoners, and the guru is a warden that gives them a chance to be set free. Every day, the people of the prison have these options:

1- Stay on the prison for one more day.
2- Try to guess their eye color.

If they go with 2:

a) If they guess wrong they're executed.
b) If they guess right they're set free.

The conditions of the prison aren't good, so they really want to be set free, and so, whenever they're certain of their eye color, they'll guess it. However, nobody wants to die, so they won't do it unless they know it for certain. This paragraph is common knowledge.
Last edited by Vytron on Sat Sep 12, 2015 3:29 pm UTC, edited 1 time in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Fri Jul 17, 2015 10:08 pm UTC

Spoiler:
As I said in the other thread, if you modified them all to have a voice shout in their heads "actually there are at least 10 people with blue eyes" such that they believed it was true and, in addition, made them all actually mentally identical with common knowledge of this fact, they could leave ten days early. This could be considered a small additional assumption or a huge one depending on your perspective. A common voice in their heads is equivalent to a guru.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Sat Jul 18, 2015 4:38 am UTC

Spoiler:
Okay, so I'll agree with you, but for the sake of discussion I'll use douglasm's argument against you:

Suppose there are 10 blue eyed people on the island, they'll see 9, so they can't use your strategy. However, the brown eyed people who say "actually there are at least 10 people with blue eyes" (this is true, they're seeing them) would incorrectly attempt to leave early and wrongly conclude their eyes are blue.

Basically, when there's an strategy to say "actually there are at least n people with blue eyes on the island" that strategy will break with n people, so "actually there are at least 10 people with blue eyes" only works with a large enough pool, but the tricky part is determining at what point it's safe to shout it in your head such that everyone shouts it so the brown eyed people would attempt to leave one day later than the blue eyed people.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Sat Jul 18, 2015 5:58 am UTC

Spoiler:
I also said in the other thread that they would fail in exactly such a case, and that this in no way contradicts anything started in the puzzle except the assertion (near the end) that they do not fail. However, the problem also tells us that there are 100 blue eyes, so your hypothetical is directly contradicted by that as well.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Sat Jul 18, 2015 6:50 am UTC

Spoiler:
But on the original puzzle they don't know there's going to be 100 blue eyed people on the island, so in this variant they also don't know. The guru doesn't tell them there's going to be 100 blue eyed people on the island, so they'd have to come up with a plan that would work for any number of blue eyed people, not just 100.

If they know there's going to be 100 blue eyed people on the island, then they don't need to shout internally "actually there are at least 10 people with blue eyes", they can leave without the guru speaking because they'll know whoever sees 99 blue eyed people has blue eyes and whoever sees 100, doesn't. They could leave Day 0.

If they don't know there'll be 100 blue eyed people then they don't know if shouting internally "actually there are at least 10 people with blue eyes" would work to leave earlier.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby PeteP » Sat Jul 18, 2015 12:09 pm UTC

Vytron wrote:
Spoiler:
Okay, so I'll agree with you, but for the sake of discussion I'll use douglasm's argument against you:

Suppose there are 10 blue eyed people on the island, they'll see 9, so they can't use your strategy. However, the brown eyed people who say "actually there are at least 10 people with blue eyes" (this is true, they're seeing them) would incorrectly attempt to leave early and wrongly conclude their eyes are blue.

Basically, when there's an strategy to say "actually there are at least n people with blue eyes on the island" that strategy will break with n people, so "actually there are at least 10 people with blue eyes" only works with a large enough pool, but the tricky part is determining at what point it's safe to shout it in your head such that everyone shouts it so the brown eyed people would attempt to leave one day later than the blue eyed people.

Spoiler:
Why would they leave, the only thing that makes sense is to skip to the point where everyone who sees less than 10 leaves, the brown eyed people have no reason to leave? Or am I misunderstanding something and the voice doesn't work for the blue eyed people who don't already have the info because they only see 9?

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Sat Jul 18, 2015 12:20 pm UTC

No way it can work
Spoiler:
We have two pools of people they are asymmetric and so can the rule be, To make it work we need a rule where Blue eyed people are guaranteed to skip the same or more days than brown

Brown eyed people see n blue eyed people
Blue eyed people see n-1 blue eyed people

So f(n)<=f(n-1)

We can see that as n increases f(n) can only decrease or stay the same. With 1 blue eyed person blue eyes can't skip a day or they'll never leave, brown eyes can't skip a day or they'll all leave
f(0)=0
f(1)=0

f(x)<=0 where x>=0
max(f(x))=0

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Sat Jul 18, 2015 1:33 pm UTC

Vytron wrote:
If they don't know there'll be 100 blue eyed people then they don't know if shouting internally "actually there are at least 10 people with blue eyes" would work to leave earlier.


That's where the magic and good luck come in. Because the magic voice just happens to shout a number that just happens to be less than the number of blue eyes, and because they all believe it without question, they don't fail.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Sat Jul 18, 2015 9:11 pm UTC

Spoiler:
the brown eyed people have no reason to leave?


If when there are 11 blue eyed people, they all see 10 eyed people and skip 10 days and leave early, when a brown eyed people see 10, they believe they're in that case and that their eyes are blue, incorrectly.

Really, probably the premise of the puzzle should be changed: they're all prisoners, and the guru is a warden that gives them a chance to be set free. Every day, the people of the prison have these options:

1- Stay on the prison for one more day.
2- Try to guess their eye color.

If they go with 2:

a) If they guess wrong they're executed.
b) If they guess right they're set free.

The conditions of the prison aren't good, so they really want to be set free, and so, whenever they're certain of their eye color, they'll guess it. However, nobody wants to die, so they won't do it unless they know it for certain. This paragraph is common knowledge.

Okay, so with this and the premise of the first post, can they make a plan that will allow them to leave the prison earlier than in the perfect logicians puzzle?

That's where the magic and good luck come in. Because the magic voice just happens to shout a number that just happens to be less than the number of blue eyes, and because they all believe it without question, they don't fail.


I see. But there's still the tricky part of not being arbitrary (superrational beings always go with the best course of action when faced with many options) and to avoid worst case scenarios.

Arbitrariness - Okay, so if everyone agrees to hear an imaginary voice that tells them to skip 10 days, they all leave earlier. Why don't they imagine a voice that tells them to skip 11 days? What is the maximum number of days that can be skipped?

Worst case - There's 3 blue eyed people on the island, what does the magic voice shout? And what does it shout when there's 4 blue eyed people? It has to be something which doesn't confuse the brown eyed people so that in the 3 eyed case they don't believe they have blue eyes.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby PeteP » Sat Jul 18, 2015 9:41 pm UTC

Vytron wrote:
Spoiler:
the brown eyed people have no reason to leave?


If when there are 11 blue eyed people, they all see 10 eyed people and skip 10 days and leave early, when a brown eyed people see 10, they believe they're in that case and that their eyes are blue, incorrectly.


Spoiler:
I thought the idea was everyone gets the same mental message irregardless of the number of eyes they see allowing them to skip the same amount. For that the actions you are describing aren't logical. If you hear the communal voice saying there are at least 10 then when you see ten it makes no logical sense to leave early, first you wait whether there are people who see 9 and leave. If they don't you leave on the next day. From the message you have no logical reason to leave as a brown-eyed person.

Not that a magical voice that gives information doesn't completely change the puzzle.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Sat Jul 18, 2015 11:37 pm UTC

Spoiler:
There is no maximum that can be skipped though the number MUST be arbitrary. If it depended on anything subjective, it would fail.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby douglasm » Sun Jul 19, 2015 4:32 pm UTC

Spoiler:
quintopia wrote:There is no maximum that can be skipped though the number MUST be arbitrary. If it depended on anything subjective, it would fail.

In that case, there's a chance that it would either be too high (and thus useless) or on the borderline (and thus causing the brown-eyed people to incorrectly conclude their eyes are blue).

I proved in the other thread that if the number of blue eyes seen is an input to the decision of how many days to skip, then success cannot be guaranteed.

So, suppose you have some way to pick a universal arbitrary number of days to skip. If this number is guaranteed to be less than the number of blue-eyed people, then it's partly a function of the number of blue eyes seen, and thus can fail as already proven. If it lack that guarantee, then it is possible (by definition) for it to be greater than the number of blue-eyed people. If it is, then everyone instantly realizes it's an invalid number, and everyone skips 0 days instead, falling back on the merely rational solution. But wait! That's effectively equivalent to capping it based on the number of blue-eyed people, which makes it guaranteed to be less after all!

You can't win, no matter how you do it there's a chance of failure if you try to skip days.

Shortening the number of days required for a solution can only be done by accepting some risk of being wrong.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Sun Jul 19, 2015 9:23 pm UTC

Spoiler:
douglasm wrote:I proved in the other thread that if the number of blue eyes seen is an input to the decision of how many days to skip, then success cannot be guaranteed.


(And this is why the solution spoiler of the OP stands the way it is)

However, all this means is that if I manage to find an alternative solution for this variant, it could be used by perfect logicians on the other thread and leave earlier in the other thread, and there would be a statue built after me, right?

Because, long time ago I convinced myself that it was impossible, but now I have my doubts and I always thought superrationality would enable an earlier escape. If there's an strategy that works in all cases except 1 then people should be able to escape early by not using the strategy in 3 arbitrary cases (that is, if the warden doesn't know what strategy they'll use and chooses how many people will have blue eyes, they just need to not use the strategy if they have brown eyes, if they're the person with blue eyes that wonders if their own eyes are brown, or if they're from the rest of blue eyed people that are thinking about the blue eyed person that thinks their own eyes are blue.) Or something.

The key is:

Everyone knows that nobody will leave the first day.

And:

Everyone knows that everyone knows nobody will leave the first day.

And:

Everyone knows that everyone knows that everyone knows that nobody will leave the first day.

These three levels of knowledge are enough to be able to skip days most of the time (in all except 1 cases as has been said)

Why three levels? Well, because you need at least 4 blue eyed people to know that nobody leaves the first day. So you need 5 (i.e. one blue eyed people that sees 4 blue eyed people, and knows they see each other, but doesn't know if they can see her) to know that everyone knows that nobody leaves the first day, and 6 to know that everyone knows that everyone knows that nobody leaves the first day.

So, it allows for this arbitrary strategy for 100 people:

-Use the decimal system.
-If you see at least 97 blue eyed people, you can pretend that day 1 is day 91

In other words, if your eyes are brown, you know that the last blue eyed person is wondering if their eyes are brown, and if the penultimate blue eyed person is wondering what they are wondering. However, the person before them IS SEEING for a fact, the last person with blue eyes. So everyone knows, that everyone knows that everyone is seeing at least 94 blue eyed people.

So, it doesn't matter if your eyes are blue or brown, you'll be having the same expectations:

The first day, if 91 people leave the island, your eyes were brown.

You were seeing 99 blue eyed people, so you know it wasn't going to happen, but some deep layer hypothetical guy didn't know it.

The second day, if 92 people leave the island, your eyes were brown.
The third day, if 93 people leave the island, your eyes were brown.
The fourth day, if 94 people leave the island, your eyes were brown.
The fifth day, if 95 people leave the island, your eyes were brown.
The sixth day, if 96 people leave the island, your eyes were brown.
The seventh day, if 97 people leave the island, your eyes were brown.
The eighth day, if 98 people leave the island, your eyes were brown.

Now things get interesting, you don't know what will happen the 9th day. All you know is that everyone was seeing at least 98 blue eyed people, so they're following the strategy of jumping to day 90.

The ninth day, if 99 people leave the island, your eyes were brown.

The tenth day 100 blue eyed people wake up and see that 99 others didn't leave, they realize that their eyes were blue and leave. The brown eyed people were seeing 100 people and waiting for day 11, they don't leave.

Does this strategy work for 99 blue eyed people?

Yes.

The first day, if 91 people leave the island, your eyes were brown.
The second day, if 92 people leave the island, your eyes were brown.
The third day, if 93 people leave the island, your eyes were brown.
The fourth day, if 94 people leave the island, your eyes were brown.
The fifth day, if 95 people leave the island, your eyes were brown.
The sixth day, if 96 people leave the island, your eyes were brown.
The seventh day, if 97 people leave the island, your eyes were brown.
The eighth day, if 98 people leave the island, your eyes were brown.

The ninth day 99 blue eyed people see each other and leave, the brown eyed people were waiting for the 10th day of the above case.

Does this strategy work for 98 blue eyed people?

Yes.

The first day, if 91 people leave the island, your eyes were brown.
The second day, if 92 people leave the island, your eyes were brown.
The third day, if 93 people leave the island, your eyes were brown.
The fourth day, if 94 people leave the island, your eyes were brown.
The fifth day, if 95 people leave the island, your eyes were brown.
The sixth day, if 96 people leave the island, your eyes were brown.
The seventh day, if 97 people leave the island, your eyes were brown.

The eighth day, 98 blue eyed people see each other and leave, the brown eyed people were waiting for the 9th day of the above case.

Does this strategy work for 97 blue eyed people?

No.

With 97 blue eyed people, each see 96, and don't use the strategy. The brown eyed people do, think they are in the above case, but are wrong.

So, clearly, we have to make the 97 leave the seventh day.

...

My idea here:

When there are 100 people on the island, some are wondering if there are 99, if there are 100, or if there are 101. The superrational beings can then agree to leave the 9th for 99, the the 10th for 100 or the 11th for 101.

In the case of 97 people, some are wondering if there are 96, 97 or 98. The superrational beings can then agree to leave the 6th for 96, the the 7th for 100 or the 8th for 101.

And so on.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby PeteP » Sun Jul 19, 2015 9:48 pm UTC

Spoiler:
You didn't actually explain how your idea at the end works.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Sun Jul 19, 2015 10:11 pm UTC

Spoiler:
PeteP wrote:You didn't actually explain how your idea at the end works.


It works the same:

There is a range of numbers that everyone knows everyone knows the other people are wondering if it's the correct one of blue eyed people. Everyone knows that everyone knows that there aren't 10 less blue eyed people than this range, so the strategy I said that works for 100 blue eyed people works for 90, 80, 70, 60, 50, 40, 30, 20 and 10. You just modify it:

-If you see at least 87 blue eyed people, you can pretend that day 1 is day 81
-If you see at least 77 blue eyed people, you can pretend that day 1 is day 71
-If you see at least 67 blue eyed people, you can pretend that day 1 is day 61

Etc.

This is for base 10, but you can use different bases to cover different numbers.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Sun Jul 19, 2015 10:17 pm UTC

Vytron wrote:
Spoiler:
PeteP wrote:You didn't actually explain how your idea at the end works.


It works the same:

There is a range of numbers that everyone knows everyone knows the other people are wondering if it's the correct one of blue eyed people. Everyone knows that everyone knows that there aren't 10 less blue eyed people than this range, so the strategy I said that works for 100 blue eyed people works for 90, 80, 70, 60, 50, 40, 30, 20 and 10. You just modify it:

-If you see at least 87 blue eyed people, you can pretend that day 1 is day 81
-If you see at least 77 blue eyed people, you can pretend that day 1 is day 71
-If you see at least 67 blue eyed people, you can pretend that day 1 is day 61

Etc.

This is for base 10, but you can use different bases to cover different numbers.

Spoiler:
Yeah, so this fails for x*10+7 BEP. but everyone knows in our original case that nobody thinks it might be x*10+7 however that fact isn't common knowledge. I don't know if you can logic to this because
Alice sees 99BEP
Alice knows bob sees at least 98BEP
Alice knows bob knows Carla sees at least 97 BEP
Alice knows bob knows Carla knows dave sees at least 96BEP
Alice knows bob knows Carla may worry Dave is only going to skip to day 81 instead of 91
I don't think that all islanders can pick a rule that's guaranteed to work.
Last edited by SPACKlick on Sun Jul 19, 2015 10:23 pm UTC, edited 1 time in total.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby PeteP » Sun Jul 19, 2015 10:18 pm UTC

Spoiler:
No I mean you didn't actually offer a solution for the 97 case. You said this "In the case of 97 people, some are wondering if there are 96, 97 or 98. The superrational beings can then agree to leave the 6th for 96, the the 7th for 100 or the 8th for 101." Is that supposed to be the explanation? Because it doesn't say how they are supposed to do that without just moving the place where the error is. (Also you made a c&p error with 100/101)

Edit: To clarify my best interpretation for what people who see 96 are supposed to do is that you are just moving the barrier for jumping one down to 96. Which obviously wouldn't help. You spent much time explaining the trivial parts but not the actual crucial part.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Sun Jul 19, 2015 11:32 pm UTC

Spoiler:
SPACKlick wrote:
Vytron wrote:Alice knows bob knows Carla may worry Dave is only going to skip to day 81 instead of 91
I don't think that all islanders can pick a rule that's guaranteed to work.


If Dave doesn't actually exist then that doesn't matter. That is, if everyone knows that some guy in some nested hypothetical doesn't actually exist, they don't need to worry about him.

What allows would allow everyone to skip one day is the fact that they know the blue eyed person that only sees one blue eyed person and has to wait to see if they leave D1 doesn't really exists. Everyone knows this, and everyone knows that they have to wait at least 90 days (i.e. they know that the person that wakes up day 91 and is surprised that nobody left day 90 because their eyes are blue too doesn't really exist) for someone to leave. And they know nobody will leave at day 91. And they know nobody will leave at day 90...

If everyone can agree that before the experiment starts they'll skip one day as above, and the warden gives blue eyes to more than 90 people, they have guaranteed a one day skip, so there could be a strategy that allows one day skip in most cases, and in the cases where it doesn't work (i.e, there's few people with blue eyes) the strategy is cancelled simultaneously, by all, just like all, simultaneously, arranged to skip one day.

PeteP wrote:You spent much time explaining the trivial parts but not the actual crucial part.


That's because I don't have a working solution yet, just ideas. There may be no solution (other than the one in the OP) but it may also be we're not smart enough and aliens with technology millions of years more advanced than us could actually find a strategy that works.

I guess I'll wait for quintopia's reply to douglasm, though if they give up it may be the end of this (this thread would be pointless as the superrationality and being able to make a plan before the experiment starts does not help and the puzzles are the same. Just like... Rethinking the prisoner dilemma where adding perfect logic and common knowledge doesn't help them avoid Defect+Defect.)

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Sun Jul 19, 2015 11:53 pm UTC

Spoiler:
But Vytron there's an edge case

with 90 Blue eyes, Blue eyed people see 89 and don't skip a day, Brown eyes see 90 and do so everyone leaves day 89.

Because things are asymmetric you will always have an edge case.

n blue eyes

You have brown sees n knows others see (n+1 and n) or (n and n-1), Blue eyes see n-1 knows others see (n and n-1) or (n-1 and n-2). The rule has to work correctly for all of those circumstances or you can't use it because you don't know which of them you're in and that the other islanders are following the same rule.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Mon Jul 20, 2015 12:18 am UTC

Waiting on me to reply to douglasm? But douglasm is 100% correct, and I already said as much in the other thread! I have nothing to add.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Mon Jul 20, 2015 5:03 am UTC

Spoiler:
SPACKlick wrote:But Vytron there's an edge case

with 90 Blue eyes, Blue eyed people see 89 and don't skip a day, Brown eyes see 90 and do so everyone leaves day 89.


But they already see 91 blue eyes and know they're not in the edge case. They should be able to skip days only if they know there's enough people to avoid messing up.

quintopia wrote:Waiting on me to reply to douglasm? But douglasm is 100% correct, and I already said as much in the other thread! I have nothing to add.


And that is giving up, since it has been shown no magic voice can exist that would help the prisoners. Oh well.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Mon Jul 20, 2015 8:55 am UTC

Spoiler:
So if your point is that from outside the game there could be a second guru who declares a number
and if that number is 7 lower than the total of blue eyed people (6 less than any islander can confirm exists)
then everyone can skip that number of days?

That's trivially true, If the guru says I can see x blue eyed people and there are n blue eyed people, everyone leaves on day 1+n-x.

For a super rational actor to come to some number as if spoken by a second guru they all need to be able to derive the second number and that's why super rationality can't help here. Because of the asymmetry of knowledge between blue and brown eyed people, there is no rule that can derive a number higher than 0 that both blue and brown eyed people can determine both that they can skip and that others will skip .

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby douglasm » Mon Jul 20, 2015 11:03 am UTC

Spoiler:
Vytron wrote:If there's an strategy that works in all cases except 1 then people should be able to escape early by not using the strategy in 3 arbitrary cases (that is, if the warden doesn't know what strategy they'll use and chooses how many people will have blue eyes, they just need to not use the strategy if they have brown eyes, if they're the person with blue eyes that wonders if their own eyes are brown, or if they're from the rest of blue eyed people that are thinking about the blue eyed person that thinks their own eyes are blue.) Or something.

The problem with trying to avoid the edge case like that is that all you accomplish is exchanging one edge case for another edge case. Say you have a solution that works for anything except 97 blue eyed people, so you try to fix it by saying "if you see 96 or 97 blue-eyed people, fall back on the old rational solution". Congratulations, your solution now works for 97 blue-eyed people - but now it fails for 96.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Mon Jul 20, 2015 1:50 pm UTC

Spoiler:
Vytron wrote:And that is giving up, since it has been shown no magic voice can exist that would help the prisoners. Oh well.


On the contrary, it only shows that there is a risk that they fail with any magic voice. However, if we take the entire text of the original puzzle as additional givens, we know they do not fail. Good luck is on their side!

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Mon Jul 20, 2015 2:05 pm UTC

Spoiler:
The arbitrary voice, which tells them all as truth and common knowledge any number lower than the true value can skip days but it bears very little resemblance to super-rationality because it requires knowledge no participant has.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby Cauchy » Mon Jul 20, 2015 6:10 pm UTC

Quintopia, while the islanders leave early in your scenario, and indeed correctly claim they have blue eyes, they do not know they have blue eyes, since knowledge is not justified true belief. As such, the islanders have violated the terms of the island (even though they don't know it). I assume this means the bomb on the island goes off killing them all, or the ferry shuts down until they can reflect on their poor life choices, or some other event in which they no longer get to leave the island.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Mon Jul 20, 2015 9:55 pm UTC

Spoiler:
SPACKlick wrote:For a super rational actor to come to some number as if spoken by a second guru they all need to be able to derive the second number and that's why super rationality can't help here. Because of the asymmetry of knowledge between blue and brown eyed people, there is no rule that can derive a number higher than 0 that both blue and brown eyed people can determine both that they can skip and that others will skip .


Um, okay, I guess I've becoming desperate, but what about forming a strategy that works for all scenarios, except a Googol Plexian blue eyed people? There isn't enough atoms in the universe for them to be so many, so they all know they'll have to be less than that, so "pushing the edge case to infinity" could work.

And, anyway, what if they already know the max number of people? Say, they begin as 200 colorless eyed people, and the warden informs them of the situation. When they enter the island, they'll be from 1 to 200 blue eyed people. Can they come up with a strategy that would work? (say, one that doesn't work with 201 people, which is fine because they know it's impossible.)


And I agree with Cauchy, quintopia's solution doesn't work because you never know your eye color.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Mon Jul 20, 2015 10:27 pm UTC

Vytron wrote:
Spoiler:
Um, okay, I guess I've becoming desperate, but what about forming a strategy that works for all scenarios, except a Googol Plexian blue eyed people?
...
Can they come up with a strategy that would work? (say, one that doesn't work with 201 people, which is fine because they know it's impossible.)

The issue isn't the top end edge case. The edge case is at the bottom. You can't find a strategy that doesn't have an edge case at the bottom except skip none.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby PeteP » Mon Jul 20, 2015 10:29 pm UTC

Spoiler:
No matter you rule or rules if it only depends on the number of blue eyes and leads deterministically to a jump of a certain size you can pre-evaluate the rule for each value and write it as a list like this:
See 1 => Jump to 1
See 2 => Jump to 1

See 16 => Jump to 1
See 17 => Jump to 10

See 100 => Jump to 90

Point being all deterministic visible eye number based rules can be reduced to such a list no matter how clever so if no list can't do it then there isn't a rule that can do it either.

Also if you go down the list everytime the value in "Jump to" changes there is a case where it doesn't work. If you only see one you can't have a jump that goes farther so it has to start with 1. And since once you change it there is a case where it's not working it either will stay at one or have an case where it fails.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Tue Jul 21, 2015 3:18 am UTC

Cauchy wrote:Quintopia, while the islanders leave early in your scenario, and indeed correctly claim they have blue eyes, they do not know they have blue eyes, since knowledge is not justified true belief. As such, the islanders have violated the terms of the island (even though they don't know it). I assume this means the bomb on the island goes off killing them all, or the ferry shuts down until they can reflect on their poor life choices, or some other event in which they no longer get to leave the island.

Why must we insist that the justified true belief which they believe is actual knowledge and actually happen to be correct about also be actual knowledge from our perspective, unless we get our jollies from watching hundreds of people explode?

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby Gwydion » Tue Jul 21, 2015 8:37 pm UTC

quintopia wrote:
Spoiler:
Vytron wrote:And that is giving up, since it has been shown no magic voice can exist that would help the prisoners. Oh well.


On the contrary, it only shows that there is a risk that they fail with any magic voice. However, if we take the entire text of the original puzzle as additional givens, we know they do not fail. Good luck is on their side!

Well, if we take the entire text of the puzzle as given, the optimum superrational strategy is "if you see 99 BEP, leave immediately, otherwise your eyes are brown." Even before the guru speaks they could execute the same strategy. This situation isn't as fun to think about, it turns out.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Tue Jul 21, 2015 9:24 pm UTC

The entire text of the puzzle is not given to them. The parts at the end they cannot incorporate into their strategy. However, they are given to us, so we can use them all we want.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby Cauchy » Tue Jul 21, 2015 10:59 pm UTC

quintopia wrote:
Cauchy wrote:Quintopia, while the islanders leave early in your scenario, and indeed correctly claim they have blue eyes, they do not know they have blue eyes, since knowledge is not justified true belief. As such, the islanders have violated the terms of the island (even though they don't know it). I assume this means the bomb on the island goes off killing them all, or the ferry shuts down until they can reflect on their poor life choices, or some other event in which they no longer get to leave the island.

Why must we insist that the justified true belief which they believe is actual knowledge and actually happen to be correct about also be actual knowledge from our perspective, unless we get our jollies from watching hundreds of people explode?


If we don't hold them to an outside observer's standards of knowledge, and we don't have that they're actually rational beings, then this is just the story of hundreds of crazy people deluding themselves into believing they know the color of their eyes as fast as possible. In that case, the optimal strategy to leave the island as soon as possible is for each of them to hear a whisper in their head claiming their eyes are blue the moment they pop on the island, and for them to believe it and leave immediately, no Guru required. Sure, everyone with brown eyes (or any color other than blue) will be wrong, but that's really irrelevant in this situation. Hell, we don't even need superrationality at this point.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Wed Jul 22, 2015 12:03 am UTC

Exactly! Problem solved!

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Wed Jul 22, 2015 2:12 am UTC

@quintopia
Spoiler:
That's why I proposed the following variation:

they're all prisoners, and the guru is a warden that gives them a chance to be set free. Every day, the people of the prison have these options:

1- Stay on the prison for one more day.
2- Try to guess their eye color.

If they go with 2:

a) If they guess wrong they're executed.
b) If they guess right they're set free.

The conditions of the prison aren't good, so they really want to be set free, and so, whenever they're certain of their eye color, they'll guess it. However, nobody wants to die, so they won't do it unless they know it for certain. This paragraph is common knowledge.


In this case, the brown eyed people would hear the voice that tells them their eyes are blue, leave the island, and be executed. So, the blue eyed people are afraid of that case, and they don't leave the island. EVEN if all of them are blue eyed and luck is on their side.

So I guess the solution on the OP stands:

It's impossible to skip any number of days even with superrationality, because if you managed to find a strategy that skips n number of days, then it should work for n+1 days, so the prisoners should be able to use it immediately and leave. This isn't the case because whenever they decide to leave shouldn't be confused by brown eyed people (i.e. if they don't leave immediately then blue eyed people leave Day 2, so brown eyed people would leave Day 3 if blue eyed people were there, because they were seeing them.)

The bottom looks like this:

1 Blue eyed person leaves D1 (they don't see anybody else)
2 Blue eyed people leave D2 (they see the only blue eyed guy they see didn't leave D1)
3 Blue eyed people leave D3 (they see the only 2 blue eyed guys they see didn't leave D2)
4 Blue eyed people leave D4 (they see the only 3 blue eyed guys they see didn't leave D3)
5 Blue eyed people leave D5 (they see the only 4 blue eyed guys they see didn't leave D5)
...

The next cases are identical, and there's no magic number that is different. It follows that:

The only way to leave earlier for n number of people should work for 3 number of people.

If you manage to find a way for 3 people to leave earlier than D3 then you have a solution that should work generally.

Alas, with 3 people they don't know if it's only 2 people, and they won't know it's more than 2 until D3 and because the others didn't leave. So other guys were right :(

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby quintopia » Wed Jul 22, 2015 2:43 am UTC

well of course they were right! that's why I proposed a completely different variant to begin with! :P

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: Rethinking Blue Eyes - A Logic Puzzle

Postby Vytron » Wed Jul 22, 2015 3:05 am UTC

Well, your magic voice stinks of inefficiency, if we're going to have magic voices why don't they tell to the blue eyed people that their eyes are blue and the brown eyed people that theirs are brown? Then everyone is guaranteed to leave immediately and are correct.

And this is the only variant where the guru gets to know their own eye color and leaves too! :P

stekp
Posts: 18
Joined: Tue Aug 18, 2015 2:34 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby stekp » Tue Aug 18, 2015 2:56 pm UTC

Ah, the blue-eye puzzle. I first came across this about 20 years ago, and became fascinated - possibly even a little obsessed - by it. I came to the conclusion, which I still hold today, that the statement of the puzzle has a critical flaw, so I wanted to post here to see if anyone agrees.

I've read through a lot of this thread, but not all 35 pages, so apologies if this is going over old ground.

When I discovered this puzzle, I really liked the iterative logical reasoning aspect that after N days, N people will leave, assuming N blue-eyed people. I completely agree with that.

My problem is with the Guru's initial announcement that "I can see someone who has blue eyes".

Despite what others say in this thread, I strongly argue that this provides *no new information* to the islanders. Everyone already knows that there are at least 99-blue eyed people on the island, and therefore already knows the Guru can see someone with blue eyes.

Therefore my objection is this: From what date should the count of N days should begin.

I say that the count begins on the day when the law of the island is first established. If you think about it, as soon as the law stating "you must leave when you can infer your eye color" is established, the islanders can immediately look around and see there are others with blue eyes. So, the only question is "how many have blue eyes?". The answer to that question can be resolved N days after the law is established, using the reasoning as per the original.

I contend that most of the arguments about this puzzle arise from this difficulty with the Guru's initial statement.

The puzzle can easily be fixed by supposing the Guru is also lawgiver, and on Day 0, establishes the law about leaving the island if you determine you eye color. The Guru thus sets the puzzle starting from that moment.

Who agrees?

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby Ralp » Wed Aug 19, 2015 7:47 pm UTC

stekp wrote:the Guru's initial announcement that "I can see someone who has blue eyes"
provides *no new information*
Who agrees?


Probably lots of people, all of whom are wrong and haven't read this thread.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby douglasm » Thu Aug 20, 2015 4:30 am UTC

stekp wrote:I've read through a lot of this thread, but not all 35 pages, so apologies if this is going over old ground.

That exact point is the primary subject of discussion on every single one of those 35 pages.

stekp wrote:I say that the count begins on the day when the law of the island is first established.

The problem with that is that you don't have the base case.

Suppose that there exists a day where the island, its people, the rules, and their knowledge of the rules all spontaneously come into existence all at once - but the Guru doesn't say anything. Label this day as day 1. There are N blue-eyed people. When do those people leave? You're saying "on day N". Suppose N is 1. There's 1 blue-eyed schmuck who looks around and sees no one with blue eyes. He has no idea anyone has blue eyes. He has no reason to leave. Your solution fails.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 7 guests