|
Was tested with this puzzle while doing my duty today, so i'm just gonna share with you guys.. For those who know about this puzzle, pls do not spoil the answer..
~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~
@Story: There's a group of islands in the northern edge of the earth. The biggest main island housed 100 blue-eyed people, and 100 red-eyed people, and an overseer with a green eye.
The problem with them is that they do not know their colour of their eyes. And on each day's 11am, those who know (after confirming) their eye colour, they will suicide (except the overseer).
And on each day, the residents of the entire island (201 ppl) will gather and meet up at 12noon. While during this gathering, they do not talk, or no means of communicating, so they could only observe the other residents.
Only on the first day (let's take it as the 0th Day), the overseer will announce "I see at least one blue-eyed".
@Assumptions:
(1.) The residents of the island are very logical, and they know that everyone else there are equally very logical. They will take any opportunity to deduce their eye colour.
(2.) As mentioned, during the noon meeting everyday, the residents are only supposed to only observe and deduce their eye colours.
(3.) The residents does not know their eye colour, and does not know it's the population and ratio of their eye colours in the island (e.g they do not know there are 100 reds or 100 blue coloured eyes)
(4.) And of cos, they do not know how many different colours are there in total
(5.) The overseer will know his eye colour, but will not suicide. (excluding the overseer, they may see 100 others with red, 99 others with blue, but they may not be either of these colours, they will not make assumption)
@Question: How many were suicided? And on which day?
@Hint:
+ Show Spoiler +(a.) there are ppl who suicide
+ Show Spoiler +(b.) the statement that the overseer announced is crucial
+ Show Spoiler +(c.) if you start analyzing with a smaller population instead
+ Show Spoiler +(d.) assumption (1.) is also crucial
Props to Oracle who solved it!
Solutions: http://www.teamliquid.net/blogs/viewblog.php?topic_id=151749#17
|
hah! Were you getting an interview for a job?
I got this exact question during an interview for a quant job at D.E. Shaw !
I solved this in the interview, so I won't spoil it for others ^^
|
On September 10 2010 14:19 mieda wrote:
hah! Were you getting an interview for a job?
I got this exact question during an interview for a quant job at D.E. Shaw !
I solved this in the interview, so I won't spoil it for others ^^
Wtf they ask these kinda questions in interviews?
|
oh no, i'm still serving my national service.. but just some guy who tested me with this puzzle, and i spent roughly an hour to solve this though (good time killer during my duty)
|
Consider if there was two people and one overseer
On day 0 the overseer says I see at least one blue eye the following would happen:
If they are both blue, on day 0 nothing would happen (they are unsure of their own eye colour), and then on day 1 they would both commit suicide due to the others uncertainty
If one is blue and one is red, the blue would commit suicide on day 0 because there it at least one blue eyed, and the one he is looking at is a red (thus he must be blue)
If we induct this for 100 blue and 100 red, I'd say on the 100th day the blues would all commit suicide.
On the 100th day, each person can count that there are 100 of their opposite eye colour. There cannot be 101 (the 101th being themselves) because then all the others would have suicided on the 99th day.
(Ex. if you are blue, and there are 101 reds, it would take 99 days to make certain you are indeed blue. You can count there are 101 reds, and 98 blues, and every other blue is doing the same. On the 98th day you see all the other blues are uncertain still, (like in the 2-player example) and thus on the 99th day you realize you are blue)
|
On September 10 2010 14:23 MyHeroNoob wrote:Show nested quote +On September 10 2010 14:19 mieda wrote:
hah! Were you getting an interview for a job?
I got this exact question during an interview for a quant job at D.E. Shaw !
I solved this in the interview, so I won't spoil it for others ^^ Wtf they ask these kinda questions in interviews?
He said it was for a quant job, so it makes sense. If you want a job involving numerical analysis, then it would make sense to be questioned with a riddle involving numerical analysis (assuming that's truly what the riddle is about).
|
On September 10 2010 14:23 MyHeroNoob wrote:Show nested quote +On September 10 2010 14:19 mieda wrote:
hah! Were you getting an interview for a job?
I got this exact question during an interview for a quant job at D.E. Shaw !
I solved this in the interview, so I won't spoil it for others ^^ Wtf they ask these kinda questions in interviews?
Yes it seems they like to give at least one brainteaser question for the quant interview. The rest were more (harder) advanced questions in stochastic calculus, real analysis (they even asked me how I can construct Haar measure on locally compact groups!), and some optimization problems.
|
On September 10 2010 14:25 Oracle wrote:
Consider if there was two people and one overseer
On day 0 the overseer says I see at least one blue eye the following would happen:
If they are both blue, on day 0 nothing would happen (they are unsure of their own eye colour), and then on day 1 they would both commit suicide due to the others uncertainty
If one is blue and one is red, the blue would commit suicide on day 0 because there it at least one blue eyed, and the one he is looking at is a red (thus he must be blue)
If we induct this for 100 blue and 100 red, I'd say on the 100th day they would all commit suicide.
On the 100th day, each person can count that there are 100 of their opposite eye colour. There cannot be 101 (the 101th being themselves) because then all the others would have suicided on the 99th day.
do you mean 200 ppl will suicide on the 100th day?
if it is, then it's wrong..
also, they do not know how many different colours are there, they are very logical, they do not assume their eye colour to be either blue or red, until they have good evidence.. who knows, one of them may have brown eye..
anyway, it's quite close though, nice try =)
|
OP or mieda, I have a question:
Does solving this riddle involve some sort of higher end mathematical knowledge? (ie. anything above basic Calculus)
If so, then I might end up wasting my time on a riddle I simply can't solve, and I'd like to go to bed soon.
|
On September 10 2010 14:29 The_Pacifist wrote:
OP or mieda, I have a question:
Does solving this riddle involve some sort of higher end mathematical knowledge? (ie. anything above basic Calculus)
If so, then I might end up wasting my time on a riddle I simply can't solve, and I'd like to go to bed soon.
Nope, just basic logic. No need for more advanced tools.
|
United States4053 Posts
On September 10 2010 14:29 kaleidoscope wrote:Show nested quote +On September 10 2010 14:25 Oracle wrote:
Consider if there was two people and one overseer
On day 0 the overseer says I see at least one blue eye the following would happen:
If they are both blue, on day 0 nothing would happen (they are unsure of their own eye colour), and then on day 1 they would both commit suicide due to the others uncertainty
If one is blue and one is red, the blue would commit suicide on day 0 because there it at least one blue eyed, and the one he is looking at is a red (thus he must be blue)
If we induct this for 100 blue and 100 red, I'd say on the 100th day they would all commit suicide.
On the 100th day, each person can count that there are 100 of their opposite eye colour. There cannot be 101 (the 101th being themselves) because then all the others would have suicided on the 99th day. do you mean 200 ppl will suicide on the 100th day? if it is, then it's wrong.. also, they do not know how many different colours are there, they are very logical, they do not assume their eye colour to be either blue or red, until they have good evidence.. who knows, one of them may have brown eye.. anyway, it's quite close though, nice try =)
I'm pretty sure he means every single blue-eyed person will suicide on the 100th day, if I read the argument right. I can't find a flaw in it, and I can't see any way the red-eyed people would ever commit suicide.
|
On September 10 2010 14:29 The_Pacifist wrote:
OP or mieda, I have a question:
Does solving this riddle involve some sort of higher end mathematical knowledge? (ie. anything above basic Calculus)
If so, then I might end up wasting my time on a riddle I simply can't solve, and I'd like to go to bed soon.
erm no, just simple deducing and logical thinking
|
On September 10 2010 14:29 kaleidoscope wrote:Show nested quote +On September 10 2010 14:25 Oracle wrote:
Consider if there was two people and one overseer
On day 0 the overseer says I see at least one blue eye the following would happen:
If they are both blue, on day 0 nothing would happen (they are unsure of their own eye colour), and then on day 1 they would both commit suicide due to the others uncertainty
If one is blue and one is red, the blue would commit suicide on day 0 because there it at least one blue eyed, and the one he is looking at is a red (thus he must be blue)
If we induct this for 100 blue and 100 red, I'd say on the 100th day they would all commit suicide.
On the 100th day, each person can count that there are 100 of their opposite eye colour. There cannot be 101 (the 101th being themselves) because then all the others would have suicided on the 99th day. do you mean 200 ppl will suicide on the 100th day? if it is, then it's wrong.. also, they do not know how many different colours are there, they are very logical, they do not assume their eye colour to be either blue or red, until they have good evidence.. who knows, one of them may have brown eye.. anyway, it's quite close though, nice try =)
Sorry i meant all [blue eyed] will suicide on the 100th day
|
On September 10 2010 14:32 infinitestory wrote:Show nested quote +On September 10 2010 14:29 kaleidoscope wrote:On September 10 2010 14:25 Oracle wrote:
Consider if there was two people and one overseer
On day 0 the overseer says I see at least one blue eye the following would happen:
If they are both blue, on day 0 nothing would happen (they are unsure of their own eye colour), and then on day 1 they would both commit suicide due to the others uncertainty
If one is blue and one is red, the blue would commit suicide on day 0 because there it at least one blue eyed, and the one he is looking at is a red (thus he must be blue)
If we induct this for 100 blue and 100 red, I'd say on the 100th day they would all commit suicide.
On the 100th day, each person can count that there are 100 of their opposite eye colour. There cannot be 101 (the 101th being themselves) because then all the others would have suicided on the 99th day. do you mean 200 ppl will suicide on the 100th day? if it is, then it's wrong.. also, they do not know how many different colours are there, they are very logical, they do not assume their eye colour to be either blue or red, until they have good evidence.. who knows, one of them may have brown eye.. anyway, it's quite close though, nice try =) I'm pretty sure he means every single blue-eyed person will suicide on the 100th day, if I read the argument right. I can't find a flaw in it, and I can't see any way the red-eyed people would ever commit suicide.
but he said everyone will know their eye colour on the 100th day, which is still partially wrong
|
On September 10 2010 14:34 Oracle wrote:Show nested quote +On September 10 2010 14:29 kaleidoscope wrote:On September 10 2010 14:25 Oracle wrote:
Consider if there was two people and one overseer
On day 0 the overseer says I see at least one blue eye the following would happen:
If they are both blue, on day 0 nothing would happen (they are unsure of their own eye colour), and then on day 1 they would both commit suicide due to the others uncertainty
If one is blue and one is red, the blue would commit suicide on day 0 because there it at least one blue eyed, and the one he is looking at is a red (thus he must be blue)
If we induct this for 100 blue and 100 red, I'd say on the 100th day they would all commit suicide.
On the 100th day, each person can count that there are 100 of their opposite eye colour. There cannot be 101 (the 101th being themselves) because then all the others would have suicided on the 99th day. do you mean 200 ppl will suicide on the 100th day? if it is, then it's wrong.. also, they do not know how many different colours are there, they are very logical, they do not assume their eye colour to be either blue or red, until they have good evidence.. who knows, one of them may have brown eye.. anyway, it's quite close though, nice try =) Sorry i meant all [blue eyed] will suicide on the 100th day
okay, props to Oracle for solving!!
|
On September 10 2010 14:35 kaleidoscope wrote:Show nested quote +On September 10 2010 14:34 Oracle wrote:On September 10 2010 14:29 kaleidoscope wrote:On September 10 2010 14:25 Oracle wrote:
Consider if there was two people and one overseer
On day 0 the overseer says I see at least one blue eye the following would happen:
If they are both blue, on day 0 nothing would happen (they are unsure of their own eye colour), and then on day 1 they would both commit suicide due to the others uncertainty
If one is blue and one is red, the blue would commit suicide on day 0 because there it at least one blue eyed, and the one he is looking at is a red (thus he must be blue)
If we induct this for 100 blue and 100 red, I'd say on the 100th day they would all commit suicide.
On the 100th day, each person can count that there are 100 of their opposite eye colour. There cannot be 101 (the 101th being themselves) because then all the others would have suicided on the 99th day. do you mean 200 ppl will suicide on the 100th day? if it is, then it's wrong.. also, they do not know how many different colours are there, they are very logical, they do not assume their eye colour to be either blue or red, until they have good evidence.. who knows, one of them may have brown eye.. anyway, it's quite close though, nice try =) Sorry i meant all [blue eyed] will suicide on the 100th day okay, props to Oracle for solving!!
yeah i did originally have that, because I didnt read the restriction of "they do not know that there are only red and blue colours"
if they knew there were only two eye colours then they would all suicide on the 100th day, but if there are infinitely many eye colours then only the blues would suicide. you caught me 
|
This is the solution:
+ Show Spoiler +WIth the announcement of the overseer, we could effectively eliminate the red-eyed ppl, and only consider the blue's perspective. All of the answers are in the perspective of any single blue-eyed ppl
If we take a smaller population, let's say 1 red 1 blue 1 overseer, when the overseer announce, on the 1st day's 11am, the blue will suicide.
Now if we have a population of 2 blue 2 red 1 overseer, after the announcement, on the 1st day, no one will suicide, which implies 2 blues (since 2 are red and 1 overseer). Hence, 2 blue will suicide on the 2nd day.
Now with 3 blue 3 red 1 overseer, after the announcement, on the 1st day, no one will suicide, which implies that 2 or 3 of them are blue. Each blue-eyed ppl will see 2 other blue. So on the 2nd day, if the 2 "other" blue eye ppl did not suicide (according to the theory from the 2blue2red1overseer), you can deduce there are 3 blues, hence suiciding on the 3rd day.
goes on and on, Pn, where n = 100.
|
I've pretty much figured out how this would work; just need to
+ Show Spoiler +Using a reduction argument:
w/ 3 people, 1b 1r 1g (Overseer)
Overseer declares on Day 0: "I see at least one blue-eyed".
Blue-Eye knows he is blue-eyed (seeing 1g and 1r) and suicides the next day
Red-Eye knows ONLY that there is "at-least" one blue eyed; (seeing 1g and 1b), he cannot make any conclusion on his own eye color after blue suicides.
w/ 4 people (2r 1b 1g)
Blue eye instantly knows (2r 1g) he is blue-eyed and commits suicide on Day 1
Red eye knows that his color is not blue on day 1 after Blue suicides.
w/ 4 people (2b 1r 1g)
Blue knows: (1b 1g 1r) that if other blue eye sees 2 red, he would suicide tomorrow. Then he doesn't. He now knows that his eyes are blue, and suicides on day 2.
Red knows: (2b 1g) does not know his own color and would not suicide
w/ 5 people
Blue Eye: (1g 2r 1b) If not blue eyed, would expect other Blue to suicide day 1, yet he does not, seeing as nobody else has blue eyes he would know his is blue and would suicide day 2.
Red Eye: (1g 2b 1r) Does not know his color and thus would not suicide.
Since the argument can be extended to 100 blue eyes, one would expect blue eyes suicide on day 100, but knowing that they would deduce that by day 2 because nobody suicides on day 1...
Thus answer is ALL BLUE EYES SUICIDE ON DAY 2.
(Otherwise I believe that the Day 100 blue eye suicide argument is correct)
I dunno if this is correct, but this is the kind of reasoning you would want to utilize in this logic argument.
|
On September 10 2010 15:04 Ciryandor wrote:I've pretty much figured out how this would work; just need to + Show Spoiler +Using a reduction argument:
w/ 3 people, 1b 1r 1g (Overseer)
Overseer declares on Day 0: "I see at least one blue-eyed".
Blue-Eye knows he is blue-eyed (seeing 1g and 1r) and suicides the next day
Red-Eye knows ONLY that there is "at-least" one blue eyed; (seeing 1g and 1b), he cannot make any conclusion on his own eye color after blue suicides.
w/ 4 people (2r 1b 1g)
Blue eye instantly knows (2r 1g) he is blue-eyed and commits suicide on Day 1
Red eye knows that his color is not blue on day 1 after Blue suicides.
w/ 4 people (2b 1r 1g)
Blue knows: (1b 1g 1r) that if other blue eye sees 2 red, he would suicide tomorrow. Then he doesn't. He now knows that his eyes are blue, and suicides on day 2.
Red knows: (2b 1g) does not know his own color and would not suicide
w/ 5 people
Blue Eye: (1g 2r 1b) If not blue eyed, would expect other Blue to suicide day 1, yet he does not, seeing as nobody else has blue eyes he would know his is blue and would suicide day 2.
Red Eye: (1g 2b 1r) Does not know his color and thus would not suicide.
Since the argument can be extended to 100 blue eyes, one would expect blue eyes suicide on day 100, but knowing that they would deduce that by day 2 because nobody suicides on day 1...
Thus answer is ALL BLUE EYES SUICIDE ON DAY 2.
(Otherwise I believe that the Day 100 blue eye suicide argument is correct)
I dunno if this is correct, but this is the kind of reasoning you would want to utilize in this logic argument.
wrong
+ Show Spoiler +this is pretty much flawed, since if u extend it with 3 blue-eyes or more, from the anyone of the blue-eye perspective, they will see another 2, and expect them to die on 2nd day, which if they dont, he's the 3rd blue eye.. for your case, the any one of the blue-eyed will see one other, but if u have one blue-eyed who see 2 others? they wont suicide on the 2nd day..
so in short, you've not considered the "trend" to it.. it's like, if u have two points in the graph, if you join them straight, it comes a line.. but u cant deduce that if u are given only two points in an equation, it must be a line.. you can join it with a curved line. Points on any other parts of the line is different than if u assume a straight line.
Note why i said excluding the red-eye upon the announcement, since, they do not know how many colours are there, they may b purple, but u just assume that they know, which they dont.. (how to know ur eye colour if u are the only one with the unique colour? since overseer did not say other colour, so u can safely eliminate the reds)
another reason why the red eyes will not confuse themselves with the blue, is because, they see on additional blue-eyed ppl, as compared to the perspective of any of the blue-eyed ppl.. Hence, if they see 3 blue eyed ppl (while the blue eyed ppl see two amongsnt themselve), they can only deduce if they are blue or non-blue 1day more than the blue-eyed ppl.
|
ok... so, will they "know" that people are staring at them more than others?
|
On September 10 2010 16:27 Jackoo wrote:
ok... so, will they "know" that people are staring at them more than others?
they are logical and they will deduce it.. ppl may stare at them because that one person have a gold eye? but he cant deduce what's the colour of his own eye..
let's put this aside
|
|
|
|
|
|
EPT
