Gefangene im Bergwerk

In einem fernen Land wurden von einem Stamm der Ureinwohner 50 Gefangene gehalten. Diese mussten für den Stammesführer in einem Bergwerk arbeiten.
Als eines Tages der Stammesführer 50 Jahre alt wurde, entschloss er, seinen Gefangenen die Chance zu geben, ihre Freiheit zurückzuerlangen. Er brachte sie alle in die Dunkelheit des Bergwerks und setzte jedem einen Hut auf. Dann sagte er zu ihnen: "Ich habe jedem von euch einen Hut aufgesetzt - entweder einen schwarzen oder einen weißen. Gleich werdet ihr einer nach dem anderen aus dem Bergwerk gelassen. Eure Aufgabe ist es, euch in einer Reihe nach Farben sortiert aufzustellen: die mit den schwarzen Hüten links, die mit den weißen Hüten rechts. Ihr dürft euch weder unter einander verständigen noch euren eigenen Hut ansehen. Gelingt euch das, so werdet ihr die Freiheit erhalten."
Wie konnten die Gefangenen diese Aufgabe bewältigen?