A group of cave gnomes, while in a dark cave, have their foreheads painted red or blue. They cannot see the color of their own foreheads, or anything else while they are in the cave. The gnomes are asked to exit the cave one by one and automatically sort themselves by color without communicating in any way after they leave the cave (verbal or non-verbal).
1. How did they do this?
The best way to achieve the solution is to have the gnomes form a line when they exit the cave. The order of the first two gnomes is irrelevant because they must stand next to each other regardless of their color. It is the third and then each sequential gnome that will be responsible for sorting. As the third gnome emerges from the cave, the colors of the previous two gnomes will be in one of the following possible combinations: rr, bb, or rb or br. If the first two gnomes are the same color, it wouldn't matter which gnome the third gnome decides to stand next to because they would be sorted regardless (rrr, brr, rrb, bbb, rbb, bbr). Given that the gnomes are able to discuss a solution while inside the cave, they would agree to do the following: if the first two gnomes are different colors, then the third gnome would know to stand between the colors (rrb, rbb, brr, bbr) thus sorting themselves by color. Each gnome after the third would do the same, stand in between the two colors, so that this way no matter the number of gnomes or the color, they are always sorted, automatically. It should be noted that I assigned the third gnome to be first/main sorter as an example, but really it would be the first gnome to emerge that sees two colors in front of him that starts the process.
2. How did you arrive at that answer? Show your process.
After pulling the majority of my hair out and being unsatisfied with my original solutions, I decided to do a simulation. I was lacking volunteers, so I turned to my beloved nail polish collection that contains an absurd number of polishes you can’t tell the difference between, alas my volunteers. I picked a few blues and a few orange shades (my substitute for red), mixed them up, and started to form a line one by one. The first few I grabbed were blue, and my fourth selection was orange. Unsure what to do with it, I just stuck this particular polish at the end of the line for now, to be dealt with later when I hoped a better idea would come to me. The fifth polish again was blue. I started to place the polish at the end of the line next to the orange polish when it occurred to me that all I needed to do was place it at the end of the string of blues to keep the colors sorted. When the next polish I grabbed was orange, I saw that the end of the string of blues was also the beginning of the string of orange polishes. So no matter which color came next, the colors would always remain sorted if I placed the next polish where the two colors met. Yay! An answer that I finally liked.
3. What other possible answers are there?
So originally I thought the best solution was that while in the cave the gnomes touch their hands to their foreheads so that as the exit the cave they would be able to automatically tell what color they were and create sorted groups based on this information. This solution adheres to all the stipulations in the question and solves the problem with minimal additions; however, things could go wrong, the paint could have already dried, or somehow not be transferred properly. This is why I chose my final answer.
Another possibility that I liked but felt like I was taking the easy way out is that all the gnomes only got painted one color. The problem states that the group of gnomes have their forehead painted red or blue. The use of “or” implies three possible things: all gnomes were painted red, all were painted blue, or some were painted red and some were painted blue. Theoretically, if the gnomes were painted all one color, they would be sorted automaticity after they leave the cave due to the fact that they are all the same.