И снова цветные шапки

[Шшок]

Очень простенькая и очень симпатичная задачка. Задавалась израильским пятиклассникам.

Есть 25 человек в красных шапках и 25 человек в черных шапках. Естественно, каждый из них не знает, какого цвета шапка у него на голове.
Эти 50 человек помещаются в одной комнате. Потом они все по одному в случайном порядке переходят в другую комнату. Их задача - построиться в другой комнате в шеренгу так, чтобы в шеренге стояли вначале 25 человек подряд в шапках одного цвета, а потом 25 человек подряд в шапках другого цвета.
Любое общение этих людей друг с другом после того, как на них надели шапки, запрещено. Однако, до того, как на них наденут шапки, они могут договариваться о чем угодно.
Как они должны действовать?

[Dendr]

Что-то не совсем понятно.
Каков алгоритм "Мастера Игры"?

1. В комнате стоят 50 человек.
2. Они договариваются о хитроумной стратегии.
3. Им одевают шапки на головы в случайном порядке, и никто не знает о цвете шапки, надетой на него. С этого момента все переговоры запрещены (да-да, даже перемигивания и общение на языке слепоглухонемых)
4. Их в случайном порядке запускают во вторую комнату, по одному.
5. Они выстраиваются в ряд нужным образом.

Где-то между 3-м и 5-м пунктом провал есть (или его нет?). Получается, что в какой-то момент каждый из подопытных видит остальных 49 человек, и соответственно, делает вывод, что у него "такая-то" шапка. Какие проблемы тогда?

Далее идут рассуждения о правильной постановке, в которых содержится спойлер к ответу.
Или так - ПЕРЕД третьим пунктом в первой комнате выключается свет, и следовательно, никто не знает, какая шапка надета на его соседа (и тем более, на него самого.
А МЕЖДУ 4-м и 5-м пунктами правило такое - каждый заходящий видит (ну, кроме первого, конечно) шеренгу вошедших ранее, видит их шапки (по-прежнему не видя своей) и, исходя из полученной информации, становится в шеренгу, и больше из нее не выходит. Иначе нельзя - потому как он увидит обязательно шапки новоприбывших, и может всегда перестроиться после всего.
Если так, то да, задача становится интересной. Хотя...
Пока все это печатал, уже нашел решение (ЛС). Для пятиклассника, пожалуй, простовата.

[molch64]

Заходит, видит шеренгу, слева красные, справа черные. Становится посередине на границе цветов.

P.S> А в задачу действительно надо ставить ограничение, что заходящий становится в уже существующую шеренгу, как стал - переходов быть не может. Иначе придет последний, все всё увидят, свои цвета поймут и всё:)
Или сделать так, что изначально НЕ известно сколько в каких шапках.

P.P.S> Для 5го задача как-раз

[Шшок]

Да, верно, тут есть недоговоренности. Лучше было бы сказать, что после того как они договорились о стратегии, каждого отвели в отдельную комнату, надели на него шапку, и уже из этой комнаты он входит прямо в ту комнату, в которой надо построить шеренгу. И до входа в общую комнату он не видит остальных.
Кроме того, пожалуй надо запретить перестановки в уже построенной части шеренги (перестановки - это когда кто-то меняет свое местоположение относительно своих соседей по шеренге).
Тогда все нормализуется...

[molch64]

Кроме того, пожалуй надо запретить перестановки в уже построенной части шеренги (перестановки - это когда кто-то меняет свое местоположение относительно своих соседей по шеренге).

Причем это будет баааальшой подсказкой к решению задачи

[Инна]

А кто-то так и не узнает свой цвет

[Dendr]

А кто-то так и не узнает свой цвет

С чего бы? Они же знают, что их - 50 человек.

[Инна]

С чего бы? Они же знают, что их - 50 человек.

А, ну да. Я в решении не использовала, что тех и других половина. Оно годится, даже если неизвестно, сколько каких