Chyba mam pomysł na rozwiązanie. Spróbuję to ładnie przedstawić dla 12 osób. Dla naszej wiedzy ponumerujemy je od 1 do 12 i przypiszemy im kolory w jakiś losowy sposób. Osoby usiądą w kręgu tak że 12 siedzi obok 1. A więc:
1 2 3 4 5 6 7 8 9 10 11 12
Teraz wstaje dowolna osoba siedząca pomiędzy takimi samymi kolorami i przesiada się między dwa różne kolory. Powiedzmy, że będzie to 2, która przesiądzie się między 7 i 8. Układ wygląda tak:
1 3 4 5 6 7 2 8 9 101112
Klucz według którego nastąpiła przesiadka znają wszyscy oprócz starych i nowych sąsiadów dwójki. A więc klucza nie znają 1 3 7 i 8. Żeby im to umożliwić wstaje 11 i siada pomiędzy 5 i 6. Mamy następujący układ:
1 3 4 5 11 6 7 2 8 9 1012
Teraz wszyscy znają klucz więc do przesiadki wstają: 3 4 5 7 8 10 którzy mają swoich sąsiadów w jednakowych kolorach. Rozumując 1 wie że jest tego samego koloru co 4, 3 co 5 itd.. W efekcie 1 3 4 5 11 przechodzą do grupy czerwonych, a 6 2 9 i 12 do zielonych. Zostaje nam:
7 8 10
8 się przesiada i teraz 7 i 10 wiedzą że są zieloni, a 8 wie że jest czerwona, bo inaczej 7 i 10 też by wstały do przesiadki. Każdy dołącza więc do swojego obozu i zadanie wykonane.
Jak widać przy dwunastu osobach idzie to bardzo szybko, ale przy setce oceniam że nie zajmie to więcej niż 6 tur przesiadek.
Edit: Widzę, że ta ostatnia przesiadka nie jest nawet potrzebna. Turę wcześniej 7 widzi że 2 nie wstał do przesiadki, zatem 7 nie jest jednakowej barwy z 8. 7 wybiera więc obóz zielonych. 8 widzi że ani 2 ani 9 nie wstaje do przesiadki więc wie , że nie jest zielony. Podobnie 10 widzi że nie wstają ani 9 ani 12, rozumie więc że nie jest czerwony. Tak więc w grupie 12 osób udało się podzielić uczestników po dwóch turach.