Der Gefangene, der ganz hinten steht und als erster seine Hutfarbe nennen soll, kennt seine eigene Hutfarbe nicht. Er könnte also nur raten. Das ist natürlich keine gute Strategie. Stattdessen nutzt er die beiden möglichen Farben, um seinen Mitgefangenen eine wichtige Information zu geben, mit denen diese ihre Hutfarbe bestimmen können.
Die zehn Gefangenen müssen sich jedoch vorher absprechen, welche Information der Mann ganz hinten mit seinen beiden möglichen Angaben “schwarz” und “weiß” kodiert.
Der Mann ganz hinten sieht neun Hüte. Die Anzahl der Hüte der einen Farbe muss eine gerade Zahl sein, die Anzahl der Hüte mit der anderen Farbe eine ungerade Zahl. Der Mann nennt die Farbe, die in gerader Anzahl vorkommt. Dies wissen alle anderen Gefangenen – und sie müssen nun genau mitzählen, damit sie ihre eigene Hutfarbe richtig angeben.
Der neunte Gefangene, der vor dem letzten steht, sieht vor sich acht Hüte. Aus der Farbangabe seines Hintermanns kann er schlussfolgern, welche Farbe sein Hut hat und diese nennen.
Der achte Gefangene sieht sieben Hüte, kennt zusätzlich die Hutfarbe seines Hintermanns und weiß zudem aus der Farbangabe des zehnten Mannes, welche Farbe unter den neun Gefangenen in gerader Anzahl vorkommt. So kann er seine eigene Farbe bestimmen.
Wie die Männer an Position neun und acht können auch alle Gefangenen davor ihre Hutfarbe aus den vorherigen Aussagen und den Hüten, die sie selbst sehen bestimmen. Neun der zehn Männer nennen also mit Sicherheit die richtige Farbe ihres eigenen Hutes – damit kommen sie frei.