[kenberg]

When there are k colors in use and the colors are known, it's clear that there are at least k factorial ways for the dwarfs to code the information (take and successful coding and any permutation of the colors, the composition will give another successful coding assuming the remaining dwarfs know what the permutation is so they can undo it). When k=2 this gives 2 ways of coding and that is (or so I think) correct. I am finding the proof that k factorial is the right general answer to be elusive enough so that I am not confident that it is correct. I'll give it some more thought. It's a nice counting problem.

As probably is clear, by successful coding I mean a way for the rear dwarf to announce a color, based n which other dwarfs have which color hats, that will provide the other dwarfs who know the code to identify their own color hat.

The basic example is to identify the colors with the numbers 0 through k-1. The rear dwarf adds the numbers, divides by k, converts the remainder back to a color, and announces the color. Each dwarf in turn convert the colors to a number, calculates the sum of the numbers (from colors) that he either he sees on dwarfs in front of him or hears from the other non-rear dwarfs, calculates what number must be added to this sum so the remainder upon division by k will be correct, converts back to a color, announces that color.

In this telling the k factorial arises directly from the fact that there are k factorial ways to assign the numbers 0 through k-1 to the k different colors.


I have a nagging feeling I have missed some ways.


I have to clear my mind of this since we are about to have company and they would, I am pretty sure, not care.