5 ms·
The 'dot-town suicides' is a more general version of a puzzle I know, "The Island with Blue-Eyed People". The solution is an induction, which is unusual in thes
by JoeAltmaier 10y ago
The 'dot-town suicides' is a more general version of a puzzle I know, "The Island with Blue-Eyed People". The solution is an induction, which is unusual in these kinds of problems.
- adium 10y agoWhy can't the visitor say "There are X red, X blue, and 1 yellow?" No one knows about the yellow, thinks it is themself, they all commit suicide on the spot.
- JoeAltmaier 10y agoThat sounds about right. But the problem statement doesn't permit the information to be a lie? The info could be "somebody has blue eyes!"
- adium 10y agoThe comment elaborated on the explanation of "non-trivial" and didn't explicitly say you can't lie. Right? Or am I not hearing this correctly? Some of the questions incorporate a "new idea" or allow you to change elements. Triangle boxes, prisoners who can make requests, tired tennis players.... I introduced a yellow dot or am I supposed to change the variables to two?
- _archon_ 10y agoThere's a discrepancy between the number of visible blues and the number given. Say the person is a blue and doesn't know it. They can count b-1 blues on everyone else. Hearing "r reds, b blues, 1 yellow," he knows he must be either blue or yellow. He doesn't know which. Everyone survives. Edit: had a paren instead of opening quote.
- adium 10y agoI'm also thinking it would need to be at least a couple hundred people to be classified as a town. Which then the odds of someone subconsciously counting a number that high in their head is unlikely. In a classroom with 30 people right now and I couldn't tell you how many of each gender there are unless I actively try. If that meant certain death, why would I count?
- czr80 10y agoYou're being downvoted, which is a bit harsh. However, you are thinking about this as a practical problem, when it is actually a mathematics exercise. The distinction comes naturally to some people, it's a real struggle for others.
- PeterisP 10y agoThere are many things that the visitor can say, and the question is to prove that absolutely anything that the visitor says will result in complete suicide if it provides any information whatsoever about the dots.
- jordigh 10y agoYeah, it's an old chestnut: https://en.wikipedia.org/wiki/Common_knowledge_(logic) https://en.wikipedia.org/wiki/Common_knowledge_(logic) Spivak has a version of it in his Calculus book, phrased as 17 (heh!) professors who must resign if a flaw is found in their published work (hehehe), and all have a flaw in their papers, known to each other except each author.
- deleted 10y ago[deleted]
- albinofrenchy 10y agoI think the puzzle as phrased is slightly incomplete. The stranger must communicate something _new_ each day to make the induction work. For instance, if the number of blues is 25, and the (merciful) stranger says that the number of blues is not prime every day, no one ever has enough information. And in fact, even that doesn't seem to be enough. The non-trivial part must be that at least one person knows more than they did before the statement, otherwise a merciful stranger could say 'The number of blues is less than <big number>' each day, where the big number is more than the population. Unfortunately that stringent of a definition for non-trivial sort of ruins the problem since in the formulation is the idea that at least one person in the village gets (at least) one number closer to knowing the exact number of blues everyday, and as soon as they know the exact number of blues they are eliminated.
- JoeAltmaier 10y agoThe clock is certainly necessary. But for information, I think its as easy as "somebody has blue eyes!" said once. If only one person has blue eyes, they see no one else with blue eyes so kill themselves. If two people have blue eyes, they see the other guy and think "maybe its only him". Next day, that guy is still alive; they now know the only remaining blue-eye is themselves; midnight comes and they both suicide. Then nobody else has to - the two guys died on day 2 so only 2 blue-eyes can exist. And so on.
- tiglionabbit 10y agoIf two people have blue eyes, "Somebody has blue eyes" is not new information, because everyone has already seen that someone has blue eyes.
- x1798DE 10y ago> If two people have blue eyes, "Somebody has blue eyes" is not new information, because everyone has already seen that someone has blue eyes. The new information in that scenario is that the other guy with blue eyes knows that someone has blue eyes.