12
$\begingroup$

Each resident of Dot-town carries a red or blue dot on his (or her) forehead, but if he ever figures out what color it is he kills himself. Each day the residents gather; one day a stranger comes and tells them something — anything — non-trivial about the number of blue dots. Prove that eventually every resident kills himself, no matter what the stranger said.

Comment: “Non-trivial” means here that there is some number of blue dots for which the statement would not have been true. Thus we have a frighteningly general version of classical problems involving knowledge about knowledge.

$\endgroup$
  • 6
    $\begingroup$ Isn't this really another form of that XKCD problem with the blue eyed people and the guru? $\endgroup$ – Conor O'Brien Aug 10 '15 at 6:47
  • 4
    $\begingroup$ It's a generalization of the blue eyes problem. I don't think this is a duplicate of the linked question or vice versa. $\endgroup$ – f'' Aug 10 '15 at 8:40
  • 4
    $\begingroup$ You should probably add that the residents are all perfect logicians. If I lived in a place populated by lots of people with red and blue dots on their heads, I don't think think I'd feel at all suicidal on learning that the number of people with blue dots is more than zero. $\endgroup$ – squeamish ossifrage Aug 10 '15 at 11:34
  • 3
    $\begingroup$ This is certainly NOT a duplicate. It is more general than every other [blue-eyes] question asked so far. The solution method is also somewhat trickier for this problem, so it is a good addition to the site. $\endgroup$ – Mike Earnest Aug 10 '15 at 17:08
  • 4
    $\begingroup$ I agree that it's not a duplicate, but you're missing the critical "exactly at midnight" part. Without that, the residents can't tell how many cycles of "if he sees I have a blue dot, he'll think "if he sees I have a blue dot, he'll think "if he sees I have a blue dot...""" everyone else has been through, and the puzzle breaks. Also, even with that, I don't think anyone would kill themselves if the stranger said something like "between 40 and 60 percent of you have blue dots," which is perfectly allowable as written. $\endgroup$ – user1618143 Aug 10 '15 at 18:35
4
$\begingroup$

The minimal statement, that suffices is I think:

There are not $n$ blue dots. This removes only one option for the blue dots and thus it seems minimal in terms of information

From there on:

If there are $n+1$ blue dots. After one day, every blue-dotter has realized that he is also a blue-dotter (after seeing the $n$ blue dots) and kills himself.
If there are $n+2$ blue dots. After one day, none of the blue-dotters have killed themselves, because they have seen $n+1$ blue dots. They however realize that they also have blue dots, so they kill themselves on the next day.
This is generalized for $n+x$. After all blue-dotters have died, the red-dotters kill themselves on the next day.

But what if?

If there are $n-x$ blue dots? Things play out identically for the red dots as they now know that there are not $p-n$ red dots where $p$ is the population size. In the mean time the blue dots are happily waiting, as they don't gain information until the red ones are dead.

The only flaw I see is that the statement may not be minimal, so I would love to see your comments.

$\endgroup$
  • $\begingroup$ How would this work if there were 30 of each and I said "There are not 2 blue dots." That information is technically already known by the group. $\endgroup$ – Kingrames Aug 11 '15 at 11:46
  • $\begingroup$ @Kingrames You also say "there are not $p-2$ red dots". This gets the red dots thinking. $\endgroup$ – dmg Aug 11 '15 at 11:56
  • $\begingroup$ To be more specific because I just realized you might misread my comment because I wrote it ambiguously... If that information was already known then the group would be dead already. Right? So the group has to be small enough that they can't have that kind of information to start off with? Logic is confusing. $\endgroup$ – Kingrames Aug 11 '15 at 11:57
  • 1
    $\begingroup$ This is only a specific case: it doesn't work "no matter what the stranger said." $\endgroup$ – 2012rcampion Aug 11 '15 at 20:36
  • 1
    $\begingroup$ @2012rcampion But by the definition of trivial in the question, every non-trivial statement gives at least this much information. $\endgroup$ – Cain Aug 11 '15 at 22:36
3
$\begingroup$

Let's say there are $n$ residents, $b$ of which have blue dots.

The stranger's statement is something like

"The number of blue dots is in the set $B$".

where $B$ is a subset of $\{1,2,\dots,n\}$ which is neither empty nor the whole set. We will assume the statement is true, namely, that $b\in B$.

Let's investigate which values of $b$ will cause a resident to kill themself on their first day.

  • If a resident has a blue dot, they will see $b-1$ blue dots, so they know the number of blue dots is $b-1$ or $b$. If $b-1\notin B$, the stranger's statement eliminates the $b-1$ case, so the resident learns their eye color is blue and kills themself.

  • Similarly, a red-dotted resident will suicide if $b+1\notin B$.

This means that a suicide will happen if $b$ is "near the boundary" of $B$. Below is an example, where the $\color{blue}{\text{blue}}$ numbers are in $B$, and the underlined values are the ones which result in a suicide: $$ {\color{blue}{0}}\,\,\color{blue}1\,\, \color{blue}2\,\,\underline{\color{blue}3}\,\,{4}\,\,5\,\,{6}\,\,\underline{\color{blue}7}\,\,\color{blue}8\,\,\color{blue}9\,\,\color{blue}{10}\,\,\color{blue}{11}\,\,\underline{\color{blue}{12}}\,\,{13}\,\,\underline{\color{blue}{14}}\,\,\underline{\color{blue}{15}}\,\,16\,\ \underline{\color{blue}{17}} $$

If there are no suicides, then none of the underlined values are possible, so the set of possible values of $b$ shrinks. On the next day, there will be a suicide if $b$ is near the boundary of this shrunken set, and no suicide causes the set to shrink again.

Eventually, the boundary will shrink to be next to the true value, $b$, causing one of the colors to suicide, and the other color to suicide on the next day.

$\endgroup$
1
$\begingroup$

When someone says they have at least one blue dot: From everyone's PoV, there are two possibilities re: how many blue dots they all have. When someone reduces it to 1, it means (s)he's figured out his/her dot color. They can also make guesses about others' PoV, guess their guesses... If someone sees x blue dots and assumes he's blue-dotted too, (s)he has to assume (s)he knows how many blue dots someone else sees, but that that person might think there are two possibilities re: how many blue dots they all have. Same for when the first person assumes (s)he has a red dot.

It can be represented with a tree. A non-trivial comment would imply at least one is red/blue at worst, so if no blue-dotted people assume they're blue-dotted, the number of seen/existing blue dots in the tree will fall to 0 too early, which they can't assume. A blue-dotted person will eventually figure out (s)he's one, and since it doesn't matter who it is, it would be every blue-dotted person. If the red-dotted ones survive, they'll realize that's because they're red-dotted and they'll die too.

If the stranger includes 0 but excludes some other numbers, it eliminates them and the numbers less than them, including 0. The reasoning will be similar to the classic case above.

$\endgroup$
  • $\begingroup$ Is it just me, or does this answer not include anything to do with a stranger visiting and declaring some arbitrary non-trivial information about the dots? $\endgroup$ – Jamie Barker Aug 11 '15 at 20:44
  • $\begingroup$ Edited to make it clear it's said by the stranger. $\endgroup$ – Nautilus Aug 12 '15 at 9:06
1
$\begingroup$

Even ignoring the midnight issue, with a little bit of lateral thinking, this breaks down. It only works if we assume the stranger must make a statement that covers the entire population. If we allow statements involving subdivisions among the villagers, he can say "At least one left-handed villager has a blue dot," and only the left-handed villagers will kill themselves.

In fact, It's possible to say something about the entire population that won't cause any suicides:

"Dividing the villagers into men, women, and children under 18, there is at least one pair of villagers who are in different groups and have the same color dot."

Because:

As long as no group is empty, there is no possible arrangement of dots that will result in a suicide on the first day. WLOG, consider a man. If he sees that all women and children have the same color dot, then there's the pair right there. Otherwise, there's at least one woman or child with a red dot and one with a blue dot, so even if the men are monochrome there's a valid pair with one of them.

$\endgroup$
  • $\begingroup$ Good point, but the statement in your spoiler doesn't satisfy the condition that "there is some number of blue dots for which the statement would not have been true." $\endgroup$ – f'' Aug 12 '15 at 21:07
  • $\begingroup$ I think you're right about needing to cover the entire population equally. If the stranger pointed to one person and said, "this person has a blue dot", that would satisfy the question's requirements (since it rules out 0 blue dots) but only that person would die. $\endgroup$ – f'' Aug 12 '15 at 21:08
0
$\begingroup$

I think all he has to say is "The number of red dots is greater than or less than the number of blue dots."

If there are 600 blue dots and no red dots, everyone panics and says "oh crap I'm the red dot!" But then they don't instantly kill themselves, and think "Phew, that means I'm not a red dot. oh shiiii" and die.

If there are an equal number of each, the same logic applies. Everyone sees the number of other dots, and concludes either truly or falsely about their dot coloration. if true, they suicide, if not, they still suicide.

Cletus wonders what it is he said.

Edit 1: You know, come to think of it, he can say anything at all.

If he says, truthfully or falsely, anything about the number of blue dots, then both the red dot people and the blue dot people suddenly become aware that they are one or the other and not some other color like green.

The first day (or in this case, infinitely tiny fraction of a second) they either come to the correct conclusion about their dot coloration and die, or they come to the false conclusion, and then realize they are incorrect, and that their dot coloration is the opposite. Then they die.

The only thing necessary to begin this catastrophe is for the people to be aware of the binary nature of the dot coloration and for someone to introduce them to the idea that other people now know something about each other's dot coloration.

$\endgroup$
  • 1
    $\begingroup$ This is only a specific case: it doesn't work "no matter what the stranger said." $\endgroup$ – 2012rcampion Aug 11 '15 at 20:37
0
$\begingroup$

Couldn't it be as simple as understanding that there is no specified population of Dot-town. There could just be two.

If the stranger says there are two blue dots, both residents know. If the stranger says there is only one blue dot, both residents know. If the stranger says there are no blue dots, both residents know.

Everybody dies.

$\endgroup$
-1
$\begingroup$

The dim-witted traveler turns up to Dot-town and says after seeing only 4 townsfolk:

Hey guys, why do all the women have red dots and the men have blue dots? (I believe this stipulates as non-trivial?)

Then:

All the women with red dots and the men with blue dots kill themselves.

Which causes:

All the surviving town members to realise they must have the opposite colour, and therefore kill themselves. The dim-witted traveler then goes "Woohoo! I own a whole town!"

Generalized:

Having a red (or blue) dot is a boolean value, therefore you know what you have when you know what you don't have. I'm surprised the townsfolk were able to live long enough to create a town in the first place ;).

$\endgroup$
  • $\begingroup$ I'm not sure this works. We don't know what happens when the townspeople receive false information. $\endgroup$ – Kingrames Aug 11 '15 at 11:23
  • $\begingroup$ @Kingrames The point is, that a boolean statement that is true for some and false for the rest, will cause all to know what they have, so it's not entirely false information. The "dim-witted traveller" and the scenario was only for amusement purposes. I imagined Cletus from The Simpsons :P $\endgroup$ – Jamie Barker Aug 11 '15 at 11:29
  • 1
    $\begingroup$ This doesn't work. All the women with red dots and the men with blue dots kill themselves.. Nobody of them knows whether they really are part of this group. Everyone who believes the traveller would kill him-/herself. $\endgroup$ – Atmocreations Aug 11 '15 at 12:16
  • 1
    $\begingroup$ All the surviving town members to realise they must have the opposite colour, and therefore kill themselves. The dim-witted traveller then goes "Woohoo! I own a whole town!" It still could be someone who didn't realize he was actually part of the first group. $\endgroup$ – Atmocreations Aug 11 '15 at 12:17
  • 1
    $\begingroup$ This is only a specific case: it doesn't work "no matter what the stranger said." $\endgroup$ – 2012rcampion Aug 11 '15 at 20:36
-3
$\begingroup$

The stranger said..

"There are NO blue dots."
So, everyone realized that they all have red dots on their forehead and killed themselves!

The end~

$\endgroup$
  • 2
    $\begingroup$ This question is asking about the stranger saying any statement, not a specific one. $\endgroup$ – KoA May 17 '16 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.