SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
CBuster
Topic Author
Posts: 4
Joined: August 11th, 2009, 12:33 pm

The isolated village

August 11th, 2009, 1:05 pm

Hi. I've seen this brainteaser posted before, along with the answer but no explanation. Hoping someone can help me out with the explanation or point me to a previous discussion.Paraphrasing the original question.... an isolated village consists of people with either a black or white dot on their forehead. No-one knows what colour their own spot is but if they find out they immediately die. An explorer enters the village and declares that at least one inhabitant has a white spot. what happens next?the solution posted was that everyone dies (i guess except the explorer). the reaon why evades me though. any thoughts? or am i simply not remembering the question properly?
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

The isolated village

August 11th, 2009, 2:46 pm

I don't think it works with "immediately". I think you have to have some sort of defined time interval. Like, if at any point in the preceding minute you figure out what color the spot on your forehead is then you die at the beginning of the next minute. Say there are A white dots and B black dots.Call the moment that the explorer makes his announcement t = 0If A = 1 then at t = 1 the one white dotted guy dies because nobody else has a white dot so he's it. Now everybody else figures out they have a black dot, so they all die at t = 2If A = 2 then at t = 1 the two white dotted guys look at each other in amazement because they each expected the other to die, being the only white-dotted person. Uh oh! They each figure out that they themselves have a white dot. At t = 2 they both die. At t = 3 everybody else dies. Yadda yadda yadda for any A.
Last edited by MatthewM on August 10th, 2009, 10:00 pm, edited 1 time in total.
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

The isolated village

August 11th, 2009, 2:52 pm

Note that the above requires everybody to have perfect information as to who dies when, as well as absolute faith in the reasoning abilities of everybody else in the village....
 
User avatar
twofish
Posts: 4944
Joined: February 18th, 2005, 6:51 pm

The isolated village

August 11th, 2009, 3:20 pm

I was thinking about that, but I couldn't get the induction step to work. The problem with this is that it requires that the number of people with white dots be known. Suppose I see eight people with white dots. There could be nine people with white dots or eight people with white dots with me and a black dot.
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

The isolated village

August 11th, 2009, 4:12 pm

No, it does not require the number of people with white dots be known.If I see x white dots then I am informed about the status of my own dot at time t = xIf the x people with white dots drop dead at t = x then I have a black dot. If they stay alive then I have a white dotEDIT: known to anybody in the vill, I mean. As an external observer who does the proving then you can know the exact state of the villagers' dots. Each villager can restrict the total number of white dots as being in the set {x, x+1} (if x is the number he himself sees)
Last edited by MatthewM on August 10th, 2009, 10:00 pm, edited 1 time in total.
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

The isolated village

August 11th, 2009, 4:26 pm

Formalizing this is a waste of time, but here goes:IH: if there are A white dots in the vill then all the white dots drop dead at t = AStarting step is trivial (A = 1)Inductive step:All white dotters in a vill with A+1 white dots see A white dots. They therefore know that their village contains either A or A+1 white dots. By their assumed infinite rationality and the inductive hypothesis they all know that if it contains A white dots then the A white dots they see will all die at t = A. At t = A nobody actually dies, so they know their vill contains A+1 white dots. This is only possible if they themselves have a white dot. Therefore they all die at t = A+1
 
User avatar
CBuster
Topic Author
Posts: 4
Joined: August 11th, 2009, 12:33 pm

The isolated village

August 11th, 2009, 4:27 pm

QuoteOriginally posted by: MatthewMI don't think it works with "immediately". I think you have to have some sort of defined time interval. Like, if at any point in the preceding minute you figure out what color the spot on your forehead is then you die at the beginning of the next minute. Say there are A white dots and B black dots.Call the moment that the explorer makes his announcement t = 0If A = 1 then at t = 1 the one white dotted guy dies because nobody else has a white dot so he's it. Now everybody else figures out they have a black dot, so they all die at t = 2If A = 2 then at t = 1 the two white dotted guys look at each other in amazement because they each expected the other to die, being the only white-dotted person. Uh oh! They each figure out that they themselves have a white dot. At t = 2 they both die. At t = 3 everybody else dies. Yadda yadda yadda for any A.yes - that makes sense. i'm not sure where i got "immediately" from. i had the A=1 part sorted but couldn't get past that.thanks very much
 
User avatar
arkol
Posts: 14
Joined: August 12th, 2008, 9:41 pm

The isolated village

August 11th, 2009, 4:37 pm

the problem is more clear if you put it likethe guy who knows kills himself only at midnight and the others discover the dead in the morning.put yourself in their place:if you see 0 whites you know you are the one and you kill yourself at midnight 1. if you see 1 white and no one dies at 1 then you know there is 1 more (you, otherwise the white guy who sees 0 whites would kill himself at 1) and kill yourself at 2.if you see 1 white and if he dies at 1 then you know there are no more whites and kill yourself at 2if you see 2 whites and no one dies at 1 and 2 you know there is 1 more (you, otherwise the white guys who see 1 white would kill themselves at 2) and kill yourself at 3.if you see 2 whites and if they die at 2 then you know there are no more whites and kill yourself at 3if you see 3 whites and no one dies at 1 and 2 and 3 you know there is 1 more (you, otherwise the white guys who see 2 whites would kill themselves at 3) and kill yourself at 4.if you see 3 whites and if they die at 3 then you know there are no more whites and kill yourself at 4if you see n whites and no one dies at 1 ... n you know there is 1 more (you, otherwise the white guys who see n-1 would kill themselves at n) and kill yourself at n+1.if you see n whites and if they die at n then you know there are no more whites and kill yourself at n+1if there are n whites everybody dies at n+1
 
User avatar
wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

The isolated village

August 11th, 2009, 5:40 pm

there is a second part of the story which might make you appreciate the problem better. the solution of the original problem is seemingly paradoxical when there are at least two villagers with white dots. here is why:upon hearing from a friend what happened to the village few months later, the explorer felt really sorry albeit extremely puzzled. "i was not saying anything new to them," he claimed, "i looked around and saw bunch of people with white dots on their forehead - they are not blind, so everyone already knows that at least one guy has a white dot!" his friend agreed with him: "yeah, so they would kill themselves anyway if you had never been there." do you agree with them?
 
User avatar
CBuster
Topic Author
Posts: 4
Joined: August 11th, 2009, 12:33 pm

The isolated village

August 11th, 2009, 6:10 pm

QuoteOriginally posted by: wileyswthere is a second part of the story which might make you appreciate the problem better. the solution of the original problem is seemingly paradoxical when there are at least two villagers with white dots. here is why:upon hearing from a friend what happened to the village few months later, the explorer felt really sorry albeit extremely puzzled. "i was not saying anything new to them," he claimed, "i looked around and saw bunch of people with white dots on their forehead - they are not blind, so everyone already knows that at least one guy has a white dot!" his friend agreed with him: "yeah, so they would kill themselves anyway if you had never been there." do you agree with them?yes, interesting line of thought. however, not sure i do agree.if there are villagers with 2 white dots, each individual with a white dot knows only of the existence of one white dot. they have no clue about their own dot. the statement by the explorer provides the catalyst where each of these individuals thinks the other should realise they have the "only" white dot. when they don't, it triggers the realisation as others have pointed out. this argument can be extended to n=3, n=4 etc.i suppose the catalyst of the statement is the important part. i further suppose that the statement would cause mass death even if number of white dots = 0. in fact, it would probably speed it up?!? on day zero, the explorer makes the statement. all the villagers look about, see no white dots and assume they have a white dot. upon gaining this "knowledge", they would have to kill themselves. everyone dead in one step (rather than the two steps required if number of whites = 1). lastly, how about if one of the villagers makes the statement? seems to me that all the villagers would die except the villager that makes the statement, as he gains no knowledge of his own dot if he is making he initial statement.
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

The isolated village

August 11th, 2009, 6:18 pm

wileysw:I was going to post something about that prior to your post, but decided against it. I think the key insight is that, while the explorer does NOT bring any new news to the village the first day (or minute, or whatever time period you want) his statement gradually forces the villagers to make implicit statements about their knowledge as time progresses. Eventually he forces them to make a statement that is non-trivial, and on the next day people die.For example, with 2 white dots:Everybody already knows that there is at least one white dot. The explorer's statement provides no new information at t = 0. At t = 1, however, the continued survival of each person is an implicit statement that "yeah, I already knew that". While everybody knew that there was at least one white dot, not everybody knew that everybody else knew that. Specifically, each white dotted person did not know that the other white dotted person knew that. The explorer's statement to everybody at the same time is like a catalyst which forces more and more information to be revealed as time goes on. EDIT: posted that before I saw the response. He even used the term "catalyst".
Last edited by MatthewM on August 10th, 2009, 10:00 pm, edited 1 time in total.
 
User avatar
twofish
Posts: 4944
Joined: February 18th, 2005, 6:51 pm

The isolated village

August 11th, 2009, 10:32 pm

QuoteOriginally posted by: MatthewMEverybody already knows that there is at least one white dot.But I think the key reason that the explorer is important is that no one could tell anyone else what they knew. Curiously I think that this model may be a very good one for financial crashes. Everyone knows in a bubble that someone is going to lose money, it's only when people figure out that they are the sucker that is going to lose money that things fall apart. You might even be able to use this to model the fact that markets overcorrect.
Last edited by twofish on August 11th, 2009, 10:00 pm, edited 1 time in total.
 
User avatar
twofish
Posts: 4944
Joined: February 18th, 2005, 6:51 pm

The isolated village

August 11th, 2009, 10:36 pm

Is there a requirement that people die in an "orderly" way? If people die in a random way, does this throw off the induction?
 
User avatar
MikeLo
Posts: 19
Joined: August 8th, 2006, 3:08 pm

The isolated village

August 12th, 2009, 7:04 am

Suppose that when I look around I see one white dot and everyone else has black dots. After 1 minute (say, choose your own value), the one (A) with the white dot dies. How can I distinguish between "A has just realised that everyone else has a black spot" and "A has already concluded that I would have already realised that everyone else has a black spot and since I didn't die A must be white"?
 
User avatar
rmax
Posts: 6080
Joined: December 8th, 2005, 9:31 am

The isolated village

August 12th, 2009, 3:56 pm

Know the problem from old, but reading all the posts has led me to a slightly different use. Unclear on the exact formulation at present (and perhaps it is rubbish anyway) - however the system of the island is in a postion of local stability - however when the explorer comes, he is kind of making a measurement. This reminds me very much of the issue of the w.f. collapse problem in QM. The island is the w.f. and the explorer is the measurement. Not sure if this is profound, or just garbage. Probably the latter as been a long day...
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On