Solution to: Colorful Dwarfs
Let the dwarfs construct a sorted row, with all blue hats on the left and all red hats on the right. One dwarf starts by positioning himself somewhere, and then one by one the other dwarfs place themselves in the row at a position conforming to the following rules:
- if there are only dwarfs with blue hats in the row, the dwarf positions himself at the right side;
- if there are only dwarfs with red hats in the row, the dwarf positions himself at the left side;
- if there are both dwarfs with red and blue hats in the row, the dwarf positions himself at the spot between the blue and red hats.
In this way, the row is filled from the boundary between blue and red hats, with blue hats to the left and red hats to the right. Once all dwarfs are in the row, all dwarfs that are at the right side of a red hat know they also wear a red hat, and all dwarfs that are left of a blue hat know they also wear a blue hat. Only the dwarf that was the last one entering the row does not know his own color yet. However, as the dwarfs know that at least 1 dwarf has a red hat, the most right sided dwarf in the row knows he has a red hat. This dwarf with a red hat steps from the end of the row and re-inserts himself again following the above rules. Therefore, also the previous dwarf now knows his color (red if the dwarf with the red hat re-entered the row left of him, blue otherwise).