The Dwarves' Test

Question

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 N^th 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 N^th 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.

In this instance, wouldn't every dwarf that found a red dot on themselves just show up on the first day in the dining hall (human, well dwarf, nature and that would show that N >= 1) - then just count each other - since they do not have to worry about showing up on a blue day? — LinkBerest, Feb 09 '16 at 03:00
@JGreenwell: No dwarf knows the color of his own dot. If he/she did, this wouldn't be much of a problem. — dma1324, Feb 09 '16 at 03:15
@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 09 '16 at 05:36
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 09 '16 at 05:48
The solution for the blue eyes problem works perfectly for this one. — Deusovi, Feb 09 '16 at 06:01
@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 09 '16 at 06:18
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 09 '16 at 06:48
@dma1324 What other strategies are there that are different from the solution to the blue eyes problem? The solution to the blue eyes problem requires induction to solve, but the final answer is the same; count the number of blue eyes. If no one leaves on that day, leave the next day. How you get there is different, but the solution is the same. I don't see any solutions for this puzzle that are substantially different. — Trenin, Feb 09 '16 at 19:06
The dwarves outsmart their chief. They agree ahead of time that they will all go to the dining hall with the most ale. Then when they run out of food and ale, they will all head to the next dining hall. Dwarves are after all, a very social bunch and far too stubborn to resort to any elven trickery.
Failure or not, the dwarves are quite full and inebriated. That's a win in any dwarven book. — Kingrames, Feb 10 '16 at 13:05
@dma1324 In order to make it necessarily distinct from the eye's island problem, the dwarves may be separated accross the land after the 0th day, so they CAN'T know who goes to the dinning room and when! (It also solves the issue about having to not communicate, since they are separated, they cant!) — GettnDer, Feb 11 '16 at 16:00
@dma1324 , can all dwarves have a blue dot painted on their back ? — Hemant Agarwal, Oct 17 '20 at 16:12

f'' · Accepted Answer · 2016-02-09T03:13:04.343

50

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.

edited Feb 09 '16 at 03:13

answered Feb 09 '16 at 03:04

f''

33,665
4
120
165

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 09 '16 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 09 '16 at 16:41
2

@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 09 '16 at 19:01
@Trenin: Ask yourself which dwarves see something particularly odd. – CR Drost Feb 09 '16 at 21:38
1

@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 '16 at 12:46
@Trenin: Reread my comment with the idea that I'm trying to hide a spoiler, or we can talk in chat. – CR Drost Feb 10 '16 at 15:04
@CRDrost OK. I see what you have done. But you have changed the question completely. Not sure why you care about spoiling it since it is a different question entirely from this puzzle, unless you intend to ask it as your own question. – Trenin Feb 10 '16 at 15:44
@Trenin Re-reading your comments, I see what you're saying now. I too do not see how {0,1} would work. This method depends on the fact that the "right" answer comes a day before the "wrong" answer; {0,1} does not have that feature. (I've deleted my comment accordingly.) – Monty Harder Feb 10 '16 at 15:59
@Trenin That would be why I said, "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.'" I stated up-front that this was an additional problem with a weaker requirement. I still believe in not spoiling the answer, because it's not, in fact, a "different question entirely" but actually is quite related, and has a related solution, and if you're glancing through these comments then you might be sufficiently spoiled to feel cheated out of your chance to solve it. – CR Drost Feb 10 '16 at 16:20
@MontyHarder I'll also spoil it in chat for you, if you want. – CR Drost Feb 10 '16 at 16:23
@CRDrost So you are implying that the solution to your problem will spoil the solution to this one? But the solution to your problem doesn't work for this problem, so there is nothing to spoil. There is no way (that I can see) to generalize the solution to your problem to this one. Besides, anyone reading the comments of an answer without reading the answer cannot complain about being spoiled. – Trenin Feb 10 '16 at 17:31
@Trenin: Okay, fine, I'll stop protecting people from spoilers. However I maintain and still very firmly believe that "Each dwarf should count the number of red dots they see as $x$ and then go on day $x+1$ modulo $2$" is a spoiler for this problem because it has the form (solution to this problem) + (2 words tacked on at the end). – CR Drost Feb 10 '16 at 23:10
@CRDrost It all comes down to the interpretation of "The presence of any blue-dotted dwarves at the dining hall on the Nth day constitutes a failure." when N is no longer defined. I assumed that an odd number of red-dotted dwarves, causing the blue-dotted dwarves to congregate on day 0, would translate to "failure" as the event would precede the red-dotted dwarves meeting on day 1. – Monty Harder Feb 11 '16 at 20:48
@MontyHarder: Why would you assume that? The purpose of that criterion is just to rule out "all the dwarves go on every day, haha you didn't say that the blue-dotted dwarves don't go on that day, I win." – CR Drost Feb 11 '16 at 20:57
@f" , what if all dwarves have a blue dot painted on their back ? – Hemant Agarwal Oct 17 '20 at 16:13

score 0 · Answer 2 · answered Feb 10 '16 at 19:25

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.

The Dwarves' Test

2 Answers2