23
$\begingroup$

One day, the chief of the dwarves decided he wanted to test his tribe. So that night, he told the dwarves that he would paint on each dwarf's back a dot colored either red or blue. Each dwarf will know everyone else's dot color, but not their own.

Every dwarf with a red dot on his or her back is to go to the dining hall on the Nth day, where N is the number of dwarves with a red dot on their backs. The presence of any blue-dotted dwarves at the dining hall on the Nth day constitutes a failure.

Furthermore, after the dwarves get their backs painted, they are not allowed to communicate using any means, including (but not limited to) speaking, punching, and holding mirrors. No dwarf is allowed to know what color he is until after the trial is over. They do not also get to know if someone went to the hall on any of the 1 to N-1 days.

The dwarves can meet on the day before the trial in order to talk strategy. What strategy should they use?

Note the question is not the same as the blue-eyes puzzle . In the blue eyes puzzle, one would get get to know if someone went to the hall on days 1 to N-1 .Here, nobody gets to know this. This is a crucial difference.

Improve this question
$\endgroup$
12
  • 4
    $\begingroup$ @Zerris This is definitely not a blue eyes puzzle. Blue-eyes puzzles don't involve choosing strategies, only making logical deductions, while here the dwarves choose a strategy to try to guarantee success. $\endgroup$
    – Mike Earnest
    Feb 9, 2016 at 5:36
  • 5
    $\begingroup$ Couldn't the dwarfs solve this by having every dwarf assume that they're in a blue eyes puzzle where "blue eyes" is replaced with "red dot", and "not being on the island" is replaced with "doesn't leave their house the next day"? On day N, all the red dot dwarfs would show up to the dining hall. All the blue dot ones would do it on day N+1, but they've already passed the trial by then. That's what I meant by "minor tweak". $\endgroup$
    – Zerris
    Feb 9, 2016 at 5:48
  • 2
    $\begingroup$ The solution for the blue eyes problem works perfectly for this one. $\endgroup$
    – Deusovi ♦
    Feb 9, 2016 at 6:01
  • 1
    $\begingroup$ @Zerris The solution for the blue eyes problem is a solution, but there are other solutions (other strategies). That is what I'm asking here. Indeed, the problems are similar; maybe I should have edited a statement in saying something like "the dwarves don't know if and when the trial has ended until after x days have passed"? $\endgroup$
    – dma1324
    Feb 9, 2016 at 6:18
  • 1
    $\begingroup$ The question that would eliminate blue-eyes solutions would be along the lines of "ask each dwarf how many red dot dwarfs there are - the dwarfs win if and only if all the red dwarfs answer correctly and all the blue dwarfs answer incorrectly, without hearing each others' answers". That way you can't use induction, but non-inductive answers still work. $\endgroup$
    – Zerris
    Feb 9, 2016 at 6:48

2 Answers 2

Reset to default
50
$\begingroup$

Each dwarf counts the number of red dots they see on everyone else's backs. If that number is $x$, they go to the hall on the $x+1$th day only.

A dwarf with a red dot will

count $N-1$ red dots, and show up on the $N$th day.

A dwarf with a blue dot will

count $N$ red dots, and show up on the $N+1$th day.

Therefore, on the $N$th day, all dwarves with red dots are present, and all dwarves with blue dots are not.

Improve this answer
$\endgroup$
15
  • $\begingroup$ In addition they do not have to wait the full $N$ days if the requirement is just "you must all show up on the same day." It is sufficient to just use {0, 1} days. $\endgroup$
    – CR Drost
    Feb 9, 2016 at 14:30
  • $\begingroup$ Presumably they go to the dinning hall quite often if not every day so they should also not go on the xth day. $\endgroup$
    – Paul Evans
    Feb 9, 2016 at 16:41
  • 2
    $\begingroup$ @CRDrost How would that work? Lets say there are 10 Dwarves and 4 have red dots. If I am a red-dotted dwarf, I would see 3 red dots. What day would I go? How is that different than being a blue dotted dwarf in a 3 red dotted dwarf scenario? $\endgroup$
    – Trenin
    Feb 9, 2016 at 19:01
  • $\begingroup$ @Trenin: Ask yourself which dwarves see something particularly odd. $\endgroup$
    – CR Drost
    Feb 9, 2016 at 21:38
  • 1
    $\begingroup$ @CRDrost None of them see anything particularly odd. Some Dwarves see red dots and some see blue. You are going to have to explain how to do this in ${0,1}$ days. $\endgroup$
    – Trenin
    Feb 10, 2016 at 12:46
0
$\begingroup$

It's a little convoluted but...

Before they are painted, each dwarf agrees to be numbered sequentially (starting with 1) - let's suppose there are M dwarves in all, and every dwarf knows every other dwarf's number. On the first day after being painted, the odd numbered dwarves goes to the dining hall at a specific time. On the second day, the even numbered dwarves go to the dining hall if and only if the dwarf with the number 1 lower than their number was present the day before and had a blue dot. The odd numbered dwarves look into the hall and can then determine who among them has a blue or a red dot. The process can then be repeated with the odd dwarves acting as the signal on the third and fourth days. In the case where there is an odd number of dwarves - there will be one left out, but could be dealt with by assigning them an odd partner that will be present/absent on the second day.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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