Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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

EDIT: Note the question linked in the comments here is not quite the same as this problem. The blue-eyes problem is more of a induction-based problem, while the dwarf problem is a simple strategy-based problem.

In the blue-eyes problem, the main point is who leaves the island and when, whereas in this problem, the main point is how to create a strategy involving no communication in order to fulfill a specific condition.

share|improve this question
3  
@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. – Mike Earnest Feb 9 at 5:36
5  
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". – Zerris Feb 9 at 5:48
2  
The solution for the blue eyes problem works perfectly for this one. – Deusovi Feb 9 at 6:01
1  
@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"? – dma1324 Feb 9 at 6:18
1  
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. – Zerris Feb 9 at 6:48
up vote 44 down vote accepted

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.

share|improve this answer
    
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. – CR Drost Feb 9 at 14:30
    
Presumably they go to the dinning hall quite often if not every day so they should also not go on the xth day. – Paul Evans Feb 9 at 16:41
1  
@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? – Trenin Feb 9 at 19:01
    
@Trenin: Ask yourself which dwarves see something particularly odd. – CR Drost Feb 9 at 21:38
    
@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. – Trenin Feb 10 at 12:46

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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