Lying Fairy
There are 100 islands, each of a distinct size. 100 perfectly logical villagers live on each island, and the numbers of villagers with blue eyes on each of the islands are the distinct numbers 0 , 1 , … , 9 9 , with a uniform distribution.
On one of the islands, all the villagers know that everyone has either blue or brown eyes, but it is forbidden for a villager to know his/her own eye color. If a villager believes they know their own eye color on a given day, they must leave the village in exile that night.
One day a fairy visits this island and announces that at least 50 villagers have blue eyes. Unfortunately, the fairy chooses completely randomly whether to lie or to the truth, but each villager believes the fairy unless they observe a contradiction. The villagers do not discuss the fairy's statement.
What is the probability that a given random villager from the smallest island will eventually leave the island in exile but be incorrect about their eye color?
If the probability is q p , where p , q are positive, coprime integers, give your answer as p + q .
The answer is 10051.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
There is a contradiction here.
Statement 1: "The fairy lies with probability 1/2"
Statement 2: "the probability of exactly n people having blue eyes is 1/101" AND "the fairy visits the island and announces that at least 50 people have blue eyes"
Statement 2 implies that the fairy lies with probability 51/101, not 1/2.
If we ignore Statement 1 and work with the information in Statement 2 we get that if 49 people have blue eyes all the brown-eyes will leave (and be incorrect) then the next day all the blues will leave (being correct). if <49 blues everyone is correct, same with >49.
So we have probability P ( 4 9 have blue eyes ) × P ( The person we consider has brown eyes ) = 1 0 1 1 × 1 0 0 5 1 = 1 0 1 0 0 5 1 So the answer is 10151. You're 100 out using my preferred formulation of the question. Or correct given a version of the question when it is given that n ≥ 1 and so the the probability of exactly n people having blue eyes is 1/100, which is what you effectively solved.
Log in to reply
Yes, that's what I did as well. I considered the 1/2 probability irrelevant because we were told it doesn't affect inference.
The probability of exactly n villagers having blue eyes is 1 0 1 1 when we don't know any other information. However, this probability and the probability of the fairy lying are not independent, so when we are told that the fairy lies with probability 1/2 (note this is a fact about the fairy, not something that can be deduced), it is more likely that exactly n people have blue eyes for each n < 5 0 .
Log in to reply
The question still contains a contradiction. In what sense is the probability 1/101? When you say "any other information", what do you mean? information other than what? All we have been told (at this point in the question statement) is that there are n people with blue eyes and that 0 ≤ n ≤ 1 0 0 . This does not imply that the probability is 1/101, since we have no basis for assuming a uniform distribution. By telling us that the probability is 1/101 you are giving extra information (information which is apparently false, so why give it?)
Statements 1 & 2 (in my comment above) are contradictions, you are trying to remedy this by saying that the statement "the probability is 1/101" is in someway "overruled" by information given later in the question, but then how do you get a probability of 1/50 for " n = 4 9 given the fairy lied"? We no longer know what P ( n = 4 9 ) is, according to your comment, and so there is no way to solve the problem.
Consider the following scenario:
Alice has a 1/2 probability of lying about people's hair colour. That is, when she meets someone she has a 1/2 chance of telling them their correct hair colour, and a 1/2 chance of lying (that is, she may tell a black-haired person "you have green hair" - this would be a lie). This 1/2 probability is a statement about Alice herself and cannot be deduced. Also, every single time Alice meets someone, she tells them they have green hair.
The final statement implies that Alice does not have an a priori probability attached to her chances of lying to somebody, the chance of her lying is either 0 or 1 and is fixed at the moment that she meets somebody. One could infer that Alice's actions are random and governed by probabilities, one could then calculate an a posteriori estimate of this probability which will be equal to the fraction of green-haired people in the sample "people Alice has met".
The only way to "fix" your question is to delete the bit about 1/101 and instead state that the probability of there being n blue-eyed people is 1 / 5 0 for 0 ≤ n < 5 0 . This still has the problems from the Alice story but they make no difference to the answer.
Alternatively you could do as I advise in my first comment and drop the bit about the fairy lying with chance 1/2, adjusting the answer accordingly.
Log in to reply
@Joshua Prettyman – There isn't a problem with the 1 0 1 1 bit. In the real world there would be no reason for the probability distribution to be uniform, but it happens to be part of the premise of this problem (perhaps there are 101 different islands on which each a different number of.people have blue eyes)- it is not a deduction, just a given fact. I believe that is the main point of confusion here - I've updated the wording to make it more clear. I gave the probability as evenly distributed so solvers could avoid some tediousness.
Given that the fairy lied, the probability that exactly n people have blue eyes is 1 0 1 5 0 1 0 1 1 = 5 0 1 for n < 5 0 . Given that the fairy told.the truth, the probability is 0.
The Alice example doesn't make sense here because you say she lies with probability 1/2 but then say she always lies. I'm not claiming the fairy will say at least 50 people have blue eyes every time - just in this one particular instance.
Log in to reply
@Maggie Miller – I quite like this discussion. When you say "it is not a deduction, just a given fact" I assume you are aware that it is not in fact given in the question, so there is no way for solvers to know.
I can grandly declare (oh my god, I'm really sorry if if wrong. I did something really stupid yesterday so it might turn out I'm just an idiot) that I have discovered the root of your confusion. I was going to write something (see below if you're interested) relating to this and I had to reread your solution to make sure of something. It was then when I realised what you'd done, eureka!
You've used conditional probability to say
P ( Lie ∩ 49 blue ) = P ( 49 blue ∣ Lie ) P ( Lie ∗ ) = 5 0 1 × 2 1
Which is all perfect if Lie = Lie ∗ but that is where the error has been made.
Lie is the statement "The statement 'at least 50 are blue' is a lie"
Lie ∗ is the statement "The fairy lies", so P ( Lie ∗ ) = 1 / 2
What you should have done is:
P ( Lie ∩ 49 blue ) = P ( 49 blue ∣ Lie ) P ( Lie ) = 5 0 1 × 1 0 1 5 0 = 1 0 1 1
Problem solved.
Now here's some other stuff I'd already written so I may as well post it:
In the question we have the statement "the fairy lies half the time (probability 1/2)". This alone is very interesting. If I say "a coin is heads with probability 1/2" I am saying something about the a priori distribution of the outcomes, this is not the same as saying "a coin is heads half the time". Indeed, even my fair coin could be tails 90% of the time.
My interpretation is that the fairy lies with probability 1/2 (which I assume is what you meant because you put in brackets as if to clarify). In this case, before she opens her mouth, she tosses a coin - if it's heads she lies. She does not have to toss the coin directly before she speaks, it may have been tossed weeks before, however, the very important factor is that when the coin is tossed it must be associated with a particular future statement. What she cannot do is toss a coin a hundred times (say there were 50 heads) and then think "right, in the next 100 statements I make I shall include 50 lies, but before I make each statement I can choose using my free will whether to lie or not (maybe I'll use one of my lies when my boss asks me if his new suit is a good fit, at the expense of having to tell the truth about something later on)". She would still lie half the time but it's not the same thing as lying with probability 1/2.
So the fairy goes to the island, there is a 1/101 chance of there being 49 blue-eyed people on the island, there is also a 51/101 chance of there being at least 50 blues. She tosses a coin and then makes a statement. So far so good, but we don't know what her statement is yet. It turns out that her statement is "at least 50 have blue eyes".
You have made another interesting point here: Precisely the point of my Alice example was that it does not make sense, but I never claimed that she always lies, just that she always tells people they have green hair (so if someone had green hair, she would not be lying).
Log in to reply
@Joshua Prettyman – I do want to point out that the equal probability distribution was actually given though - originally I had written "assume the probability is 1/101." Generally, 'assum' means, "There's no reason to think this is true but please pretend for the sake of thought that it is." ;)
I do see your point with the wording of the fairy lied - it's a shame; originally I had written something more direct but changed it trying to clarify for someone else - I'll just re-edit it. Thanks!
Log in to reply
@Maggie Miller – Just stop joshua is right
Log in to reply
@Yamin Belmessous – Uhhhhh guys? The question states there are 100 islands and that the each island has a unique number of blue eyed people, 0-99. That means there is 100 different combinations of blue/brown to work with and that every island will have at least 1 brown.
I found 2 problems with the presentation of the problem itself: 1. According to the language of the problem, you wrote that all the villagers have either "blue or brown" eyes. Read simply, this means that either all the villagers have blue eyes or they all have brown eyes. But from the first paragraph we know that there is no island that has 100 villagers with blue eyes. And we can therefore assume that the island is referring to the island with all the villagers having brown eyes. I think what you meant to write was that the only 2 possible colors for each villager on the island was either blue or brown. 2. In the second to last paragraph you wrote "a given random villager from the smallest island". What is the smallest island? According to the first paragraph, there are 100 villagers living on each island?
Re the famous problem you linked to - while I see how the simplified case of one or two blue-eyed girls works out, I believe the induction is fallacious - with 3 blue-eyed girls, the process breaks down. If Sally sees that both Jane and Anna have blue eyes, then she knows that ALL three of them are seeing blue eyes, and therefore none of them will be able to make a deduction about their own eye colour. The next day's announcement, therefore, will play out the same way.
your answer and solution both are incorrect....... you didn't take any possibility of whether the fairy is lying or not...... the question follows the Bey's theorem...... the answer to the following problem must be 152 Here's the solution: 1.) first of all it is given that a certain person leaves the island he leaves the island only in two cases a) if fairy is telling the truth, and there is exactly 50 villagers with blue eyes, and the person is having the blue eyes. So the probabilty of this condition is 1/2×1/50×50/100 . b) if fairy is lying, and there is exactly 49 villagers with blue eyes, and the villager has brown eyes. So the probability is 1/2×1/50×51/100 2.) probability of 1(b) is our required one So by applying bey’s theorem : ( 1/2×1/50×51/100 )/(1/2×1/50×51/100 + 1/2×1/50×50/100) = 51/101 SO answer to the following problem is 152.
Log in to reply
You forget that when 1 blue-eyed person leaves, all blue-eyed persons leave, and a day later all brown-eyed persons will leave, and vice versa.
Either this solution is incorrect, the original problem you linked to is incorrect, or both are incorrect, but I'll try to explain why later as I don't have any time right now and it must take quite a while to explain.
The only way to know what color you have if you are to believe "at least 50 people have blue eyes" without obsering a contradiction is to observe 49 people with blue eyes (you'd assume due to no contradicition you must be the 50th blue eyed). Anything larger would not necessitate you to have to have any particular color because 50 blue eyes is already fulfilled. Anything smaller would be a contradiction and the fairies statement simply becomes worthless and youre back to square one. Observing 49 blue eyes is 1/100 chance, becauze of 0-99 (100 different integers) 49 is one of these. Now to be incorrect about your conclusion of you having blue eyes there must be only 49 and she lies, which is 1/2 chance. Island smallness probability is random 1/100 islands. 1/100 islands 1/100 blueeyes 1/2lies=1/20000. I believe the answer should be 20001. Not sure where people are getting 101 from.
If they are all perfectly logical then they wouldn't assume that the fairy was telling the truth
This problem needs to be made more clear and actually proof read.
The correct probability I think is actually 1/100 x the official solution.
As correctly stated, the island visited by the fairy has to be the [49 blue,51 brown] island (P=1/100), and the random villager has to be one of the brown eyes (P=51/100).
But the island ALSO has to be the smallest of the 100 (all islands are a distinct size remember), and nowhere is it stated or implied that the smallest island was the one with the logical villagers (the one visited by the fairy). The visited island could indeed be the [49 blue,51 brown] island, but if this island was, say, the 20th largest island, then the chance of anyone leaving the smallest island is zero.
So, the visited island has to be the smallest (P=1/100), it has to be the [49 blue,51 brown] island (P=1/100), and the random villager has to be brown-eyed (P=51/100). Probability is the product 51/1000000 Answer = 1000051
Fun thing to notice is that on Islands 51 and 52, half of the population will leave on the same night. (If I was on Island 51 and leaving, it will actually give me pause to think, seeing my brown-eyed neighbour rummaging around in his boat. So he's got brown eyes and thought he had to leave. Which lets me deduce that he's in the same position as I am. Which leads me to think I must have deduced wrongly, and must have brown eyes in stead of blue ones. So I can stay, right? . .. ... Daaaamn) Even funnier is that the next day, everybody will be waking up to an island half depopulated, which will let everybody deduce their eye colour. Two Islands, swiped clean by a random fairy. Ouch.
I think this is a simpler (but wordier) solution that doesn't require villagers doing multiple-day reasoning.
The only case where a villager would leave the island in exile but be incorrect about their eye color is when the fairy is lying but the villager believes it, which means that the villager doesn't observe a contradiction. Otherwise, perfectly logical villagers would only leave the island if they were correct about their eye color.
This can only happen if, with looking at the other 99 villagers' eyes, a villager can't determine if the fairy is lying or not (in other words, they need information about their own eyes). This is only the case when the villager observes 49 blue eyes and 50 brown eyes. If the villager observes 50 or more blue eyes, they would know that the fairy is telling the truth that at least 50 villagers have blue eyes. If the villager observes 48 or less blue eyes, they would know that the fairy is lying about at least 50 villagers having blue eyes because even if the villager has blue eyes, there won't be enough blue eyes to back the fairy's claim.
With the villager observing 49 blue eyes and 50 brown eyes, they need information about their own eye color in order to determine if the fairy is lying or not about at least 50 villagers having blue eyes. If they have blue eyes, the fairy is telling the truth. On the other hand, if they have brown eyes, the fairy is lying. Since the villager doesn't observe a contradiction, the villager will believe the fairy and therefore believe they have blue eyes. They would then leave the island in exile that night. If they actually have blue eyes, they would correct about their eye color. Otherwise, if they actually have brown eyes, they would be incorrect. This case where the villager actually has brown eyes is the only case where the situation described in the question happens.
In order for this to happen, the village must have 49 villagers with blue eyes and 51 villagers with brown eyes. Since the total number of blue eyes on an island has a uniform distribution with 100 possibilities, the chance for this to happen is 1 0 0 1 . Next, the given random villager must have brown eyes. Villagers with blue eyes would observe 48 blue eyes and know that the fairy is lying. The chance for the given random villager to have brown eyes is 1 0 0 5 1 .
Therefore, the probability is ( 1 0 0 1 ) * ( 1 0 0 5 1 ) = 1 0 0 0 0 5 1 . The answer is 51 + 10000 = 10051 .
Consider situation with 51 villagers having blue eyes. When they are told that there are 50 villagers with blue eyes, they have to conclude that their eyes are brown and have to leave the island. Yet they would be wrong about their eye colour. Therefore, the correct answer is (51+51)/10000=102/10000=51/5000 =>5051.
What about factoring in the probability that the fairy lies? Wouldn't that make it 51/2000 and therefore 20051?
Probability that the fairy is lying - 1/2 Probability that there are 49 blue eyed villagers on the island that fairy visited - 1/100 Probability that the randomly chosen villager is brown eyed - 51/100 Probability that the given island is the smallest island - 1/100 ( last para of que says that randomly chosen villager is from the smallest village , so the village that the fairy visits must be smallest to make all calculations) Hence ans should be 51/2000000 (1/100 * 1/100 * 1/2 * 51/100)
First refer to this famous problem .
If the fairy told the truth, then eventually all islanders will leave in exile but correctly know their own eye colors.
If the fairy lied:
Thus, a villager will only exile themself and be incorrect if exactly 49 people have blue eyes (probability 1 0 0 1 ) and they have brown eyes (probability 1 0 0 5 1 , when 49 have blue eyes), so the probability is 1 0 0 1 1 0 0 5 1 = 1 0 0 0 0 5 1 .
Therefore, the answer is 1 0 0 5 1 .