Sortierende Agenten

In einem Raum laufen eine Anzahl von Agenten herum, die alle entweder einen roten oder einen blauen Hut aufhaben, den sie selber natürlich nicht sehen können. Die Hüte aller anderen Agenten dagegen kann jeder sehen. Es gibt nicht notwendigerweise gleich viele blaue und rote Hüte. Die Agenten können nicht mit einander kommunizieren und bestimmen ihre eigene Bewegung auch nur aufgrund der Position der anderen Agenten.

Wie müssen sich die Agenten verhalten, um am Ende eine Schlange zu bilden, in der vorne alle Agenten mit roten Hüten und hinten alle Agenten mit blauen Hüten stehen?

 

zurück