Rethinking Blue Eyes - A Logic Puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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 » Tue Aug 25, 2015 2:23 pm UTC

stekp wrote:
PeteP wrote:Hmm have you read my last post?

Sorry, Yeah I did it - there are too many replies from everyone for me to keep up with!!
With your group 1,2,3 etc, in my scenario the "group of people who only see 97 blue eyes" would be the empty set. Everyone would be able so determine that set is empty at the start.

PeteP wrote:Anyway another try: At the end of the chain it's unknown whether D knows that anyone has blue eyes not just whether a specific individual has blue eyes. Yes the actual people A ,B,C all know that D has the knowledge that there is someone with blue eyes. But the mental construct C created by the mental construct B which both only exist in A's mind doesn't have to share that knowledge. Because the mental construct C is not the real C.


Yes, the mental construct of C is not the same as C.
But - and this is important - because the information being used is globally known about C, anyone constructing a model of C's brain (at any level of abstraction) is able to use globally known facts about C. And one of those globally known facts about C is that he knows there is a lower bound on the number of blues of (N-2). Therefore everyone can use this fact in their mental constructs of C, and mental constructs any level of abstraction can use this information.

spoilered Because I think that my second explanation attempt below it might work better for you.
Spoiler:
A person who has blue eyes sees n-1 people with blue eyes and would know about these people that they see at least n-2 and would know that nobody sees less than n-2, however said person wouldn't know whether the people with blue eyes they see would know that everyone sees at least n-2 eyes. If the person didn't have blue eyes themselves the other would only know that everyone sees at least n-3. So where is the knowledge that the others know there everyone sees at least n-2 supposed to come from. And then the same for the next level.


Or let's put it in terms of global knowvedge. Person A knows there are at least n-1 and that it's globally known that there are at least n-2. However A doesn't know whether it's globally known that it is globally known that there are at least n-2. Because the people with blue eyes might only know that there are at least n-2 but only know that it's globally known that there are at least n-3 people with blue eyes. The knowledge about global knowledge also decreases with each step. That is why you can't use the global knowledge from the first step deeper in the chain because it isn't known anymore that it is known.

My last attempt for now too.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby stekp » Tue Aug 25, 2015 2:31 pm UTC

Bugger!

OK, so I started writing a detailed post with everybody's knowledge of everyone else in detail, including all the information that I figured the islanders could incorporate into their models. But then I had an epiphany and realized something rather shocking: What I have been arguing all this time doesn't work!

It amounts to the fact the my "global knowledge of the minimum number of blues" only kicks at a certain point, and as PeteP says there would be uncertainty among the islands when that point would be. There will always be a someone (or someone's model of someone) who can't be sure whether this minimum number rule has yet kicked in. Yeah I know that's kind of what you were trying to tell me all along.

It still feels weird because you are left with that unsatisfactory feeling that there must be *some way* that would enable the existence of blue eyed people to be common knowledege, even without the Guru.

Anyway thanks all for your contributions.

Damn it, now I can't decide whether I love or hate this puzzle!

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Tue Aug 25, 2015 2:38 pm UTC

i think most people who discuss the puzzle have had that epiphany moment. The gut instinct that some days can be skipped or something is common knowledge because it's deeply recursive is very common. Welcome to this side of the coin.

While it's fresh and without looking at the comments of others, can you describe as closely as possible the thought process around your epiphany, it may help the next poster who comes along having not seen it yet.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby douglasm » Tue Aug 25, 2015 5:26 pm UTC

stekp wrote:Bugger!

OK, so I started writing a detailed post with everybody's knowledge of everyone else in detail, including all the information that I figured the islanders could incorporate into their models. But then I had an epiphany and realized something rather shocking: What I have been arguing all this time doesn't work!

It amounts to the fact the my "global knowledge of the minimum number of blues" only kicks at a certain point, and as PeteP says there would be uncertainty among the islands when that point would be. There will always be a someone (or someone's model of someone) who can't be sure whether this minimum number rule has yet kicked in. Yeah I know that's kind of what you were trying to tell me all along.

It still feels weird because you are left with that unsatisfactory feeling that there must be *some way* that would enable the existence of blue eyed people to be common knowledege, even without the Guru.

Anyway thanks all for your contributions.

Damn it, now I can't decide whether I love or hate this puzzle!

The real secret here is that your "global knowledge" is not real - it's a derived fact, not a base fact, derived from all the specific blue-eyed people, and if you eliminate the basis of its derivation (by following a chain of hypotheticals where those specific people's eye color is unknown) then the derived global fact goes away too.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby stekp » Wed Aug 26, 2015 2:09 pm UTC

SPACKlick wrote:i think most people who discuss the puzzle have had that epiphany moment. The gut instinct that some days can be skipped or something is common knowledge because it's deeply recursive is very common. Welcome to this side of the coin.


The reasoning process that happens after the announcement (blue eyed people all leaving on day N) was always my favourite part of the puzzle, I could see the logic of that quickly and it seemed elegant. It was always the significance of the Guru's announcement I was uncomfortable with. I used to tell myself that actually the blue-eyed law coming into place and the Guru's announcement should be on the same day in order to resolve this conflict. That thinking was what really what prompted all this.

SPACKlick wrote:While it's fresh and without looking at the comments of others, can you describe as closely as possible the thought process around your epiphany, it may help the next poster who comes along having not seen it yet.


It's hard to define. I was in the middle of a post trying to justify my brilliant scheme. Also I was thinking about this post about iterating down to zero. I had got it in my mind that something changed at N=3, this being the case where everyone's model of everyone observations would have to contain at least on blue-eye, meaning the reasoning process would need to be different in this case due to the "extra knowledge". But then I realized this was introducing a artificial discontinuity and that in any case, the islanders themselves would not know beforehand that N was 3 and not 2. Suddenly I saw the foundation of my argument falling away. It's seems obvious now, but somehow I managed to completely convince myself!

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3060
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby Qaanol » Wed Aug 26, 2015 9:35 pm UTC

Whee! I’ll jump back into this for some fun times!

I still like this explanation:

Suppose there are actually 201 separate islands, named “island 0” through “island 200”, where each island N has N blue-eyed people on it. Of course, the people on the islands don’t know which island they are on.

One day the guru plants a giant flag on island 0 which reads “This is island 0.” (Or equivalently, the guru tells each non-zero island “I see at least one blue-eyed person on this island”.) The existence and meaning of the flag is immediately common knowledge on all islands.

What happens next stekp?
wee free kings

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 » Thu Aug 27, 2015 6:46 am UTC

Well, looks like I came late to the party, since stekp had already been illuminated and understood the problem with his argument. I'm still going to answer to this, for courtesy.

stekp wrote:I don't agree with that. The problem tells us there are 100 blue eyed people as a fact. Even if, as an islander, I don't know there are 100, I do know there at least 99. Furthermore, when thinking about what everyone else knows, if I have blue eyes, I will know everyone else is able to reason the number cannot drop below 98. And if I have brown eyes, I will know everyone is able to reason the number cannot drop below 99. So taking the worse case scenario, the minimum is anyone's model is 98. This is global knowledge and can therefore be used to everyone. There is no circumstance where someone might think it's possible that anyone could be justified in having a model where there are only 97. Indeed, 98 is the minimum that any reasonable model must contain, and everyone on the island is able to deduce this.


So you see 99 and set the bare minimum to 98. This is "the bare minimum is one less than what I see". However, if your eyes are brown, then someone is seeing 98 blue eyed people, and setting their minimum to 97, so your bare minimum doesn't agree with them.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby stekp » Thu Aug 27, 2015 9:12 am UTC

Qaanol wrote:Whee! I’ll jump back into this for some fun times!

I still like this explanation:

Suppose there are actually 201 separate islands, named “island 0” through “island 200”, where each island N has N blue-eyed people on it. Of course, the people on the islands don’t know which island they are on.

One day the guru plants a giant flag on island 0 which reads “This is island 0.” (Or equivalently, the guru tells each non-zero island “I see at least one blue-eyed person on this island”.) The existence and meaning of the flag is immediately common knowledge on all islands.

What happens next stekp?



Hmm. Does everyone on every island know about the 200 islands and the rule that there N blue-eyed people on island N?
If so, since as you say, this amounts to the same as the Guru visiting every island and saying "I see at least one blue eyed person", presumably therefore it kicks off the process on all the islands? i.e. island N blues leave on day N.

Of course, I hope when the blue eyed people leave the island, they don't decide to travel to one of the other islands. That would really foul things up! :D

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Thu Aug 27, 2015 9:26 am UTC

Interestingly it wouldn't foul things up at all. Each islander on ilsand N>n would see n blue eyed islanders arrive and they would be excluded from the counting so N BEP woule leave on day N leaving the new n BEP behind.

Unless the n new BEP became bound by the rules of whatever island they landed on in which case they would leave islands every day and 200 days in you have an average of 100 hundred islanders arriving and leaving each island each day.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby stekp » Thu Aug 27, 2015 9:29 am UTC

Qaanol wrote:Suppose there are actually 201 separate islands....


Actually, thinking about this a bit more, yes I quite like it also.

If you are on an unknown island, and you see 0 blue eyed people. You know you must be on either island 0 or island 1. When the Guru plants the flag it immediately tells you which of those cases is true, and hence, allows you to determine your eye colour.

The 201 islands are really just a metaphor for all the possible worlds that could exist, and the Guru planting the flag is effectively ruling out one possible world.

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby stekp » Thu Aug 27, 2015 9:42 am UTC

SPACKlick wrote:Interestingly it wouldn't foul things up at all. Each islander on ilsand N>n would see n blue eyed islanders arrive and they would be excluded from the counting so N BEP woule leave on day N leaving the new n BEP behind.

Unless the n new BEP became bound by the rules of whatever island they landed on in which case they would leave islands every day and 200 days in you have an average of 100 hundred islanders arriving and leaving each island each day.


Perhaps this would so incense the blue-eyed people at the blatant discrimination on every island they went to, that they would overthrow the Guru's regime and live peaceably with the browns!
:D

But what would happen if the blue eyed people all lost their memory of their eye colour as soon as they landed on a new island?

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

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby SPACKlick » Thu Aug 27, 2015 9:49 am UTC

They'd stay put after the first move and all 201,000 blue eyed people would move once and only once. Their arrival doesn't disrupt the logic of the other islanders.

Interestingly because of the dispersal pattern (assuming no preference for island of landing) rather than being spread evenly accross the islands there's a bias towards the earlier islands such that you'd expect 50.5 more people on the first hundred islands than the last hundred.

MOJr
Posts: 12
Joined: Mon Sep 07, 2015 5:43 pm UTC

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby MOJr » Mon Sep 07, 2015 5:51 pm UTC

I think you only need 2 days if you can have prior communication and you don't even need the guru statement.

Each islander will simply go to the fery on ((number of blue eyes I see) modulo 2) day. And their eye color would be the eye color of everyone else there ;)

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 Sep 12, 2015 1:12 am UTC

1 Blue eyed people, and 100 brown eyed people, using MOJr's strategy:

100 brown eyed people see one blue eyed people, so day 1 they go into the ferry thinking their own eyes are blue, and die instead of leaving the island?

User avatar
Znirk
Posts: 174
Joined: Mon Jul 01, 2013 9:47 am UTC
Location: ZZ9 plural Z α

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby Znirk » Sat Sep 12, 2015 7:11 am UTC

You don't need blue eyes to leave, and there's no death (perfect logicians don't need sanctions because they never make mistakes).
http://www.xkcd.com/blue_eyes.html wrote:Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay.

(Incidentally, that is going to be one bored ferry operator on most nights ...)

A few issues though: First, wording. I'm pretty sure MOJr's "number of blue eyes modulo 2" should be "number of blue-eyed people modulo 2".

Second, there's a minor timing issue: The people going to the ferry only know that they all have the same eye colour; it's only when they see who else is coming that they know what colour that is. That one's solvable: just agree that the people leaving during the first night meet up at the Pier at 11pm and everybody else stays away, and by the time the ferry arrives they know the colour from looking at each other. (Of course this still breaks down in the edge case where only one person wants to leave on either of the nights.)

But the big one is that this plan assumes there are at most two eye colours on the island and that one of them is blue. That is not known, and not discussable in the pre-island Phase. Even if you allow general statements about what colours are and aren't present, still either at least one person would need to already know their own colour, or they need one of the more talkative sort of guru to help them.

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 Sep 12, 2015 2:17 pm UTC

Znirk wrote:You don't need blue eyes to leave, and there's no death (perfect logicians don't need sanctions because they never make mistakes).
http://www.xkcd.com/blue_eyes.html wrote:Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay.


You can discuss that puzzle here. This thread poses a variation that adds superrationality, allows them to make a plan before landing on the island, but basically, allows them to make a guess and if they're wrong, they die, so they would never guess unless they were absolutely certain of their eye color, and any strategy that is very likely to succeed but only fails in one case wouldn't be used because, even if they had 1 in 1000000000 chance of being wrong they wouldn't gamble their life.

Znirk wrote: just agree that the people leaving during the first night meet up at the Pier at 11pm and everybody else stays away


The puzzle forbids stuff like this, and I quote:

Vytron wrote: 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.)


Being in some part of the island at some prearranged time so that everyone arriving knows they have the eye color of the people they see IS communicating. Sorry, but that's like agreeing to wink to the blue eyed people you see, so they know what's their eye color, here, by appearing, you tell them "you have my eye color", which is forbidden.

User avatar
Znirk
Posts: 174
Joined: Mon Jul 01, 2013 9:47 am UTC
Location: ZZ9 plural Z α

Re: Rethinking Blue Eyes - A Logic Puzzle

Postby Znirk » Sat Sep 12, 2015 2:32 pm UTC

Vytron wrote:This thread poses a variation that adds superrationality, allows them to make a plan before landing on the island, but basically, allows them to make a guess and if they're wrong, they die, so they would never guess unless they were absolutely certain of their eye color, and any strategy that is very likely to succeed but only fails in one case wouldn't be used because, even if they had 1 in 1000000000 chance of being wrong they wouldn't gamble their life.

May I suggest that you update the first post in the thread with the extra rules you've come up with since?

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 Sep 12, 2015 3:30 pm UTC

Added.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: Google [Bot] and 3 guests