danetka.ru

Тут было много задач про людей в шляпах, но этой задачи по-моему не было. Условия таковы:

1. 50 человек находятся каждый в своей отдельной комнате.
2. Каждому из них надевают на голову либо черную шляпу, либо белую. Каждый из них не знает, какого цвета шляпа у него на голове. При этом количество белых шляп не обязательно равно количеству черных, вплоть до того, что все шляпы могут быть одного цвета.
3. Из каждой отдельной комнаты есть выходы в огромный общий зал, и на полу зала напротив друг друга начерчены две параллельные линии.
4. Людей выводят из комнат в зал строго по одному. Первый человек имеет право встать в любое место возле любой линии (лицом ко второй линии). Второй и все последующие могут делать то же самое, но если они становятся в непустую шеренгу, то они должны становиться исключительно на какой-либо край шеренги, вплотную к уже стоящим в шеренге людям (то есть, без зазоров). Разумеется, каждый человек, войдя в зал, видит всех, кто уже находится в зале, и видит цвета их шляп.
5. В конечном итоге все люди должны выстроиться вдоль двух линий в виде двух плотных шеренг (шеренги лицом друг к другу) так, чтобы в одной шеренге были только белые шляпы, а в другой - только черные.
6. У каждого есть право в любой момент времени один раз переместиться либо из одной шеренги в другую, либо в другое место в своей шеренге. Если кто-то выходит из середины шеренги с целью перемещения, остальные должны сдвинуться, чтобы закрыть образовавшийся зазор, и такое закрытие зазора не считается перемещением.
7. Перед тем, как людей разводят по отдельным комнатам и надевают на них шляпы, они собираются все вместе и заранее разрабатывают стратегию. В тот момент, когда выполнение задания началось, любая передача информации, выходящая за рамки разработанной стратегии, запрещена. Когда люди находятся в зале, любая передача информации типа "у тебя на голове белая шляпа" запрещена, и вообще запрещены любые разговоры, перемигивания, сигналы и так далее. Можно лишь занимать свое место возле линии и при желании один раз переместиться.

Как им выполнить задачу?

Gibby писал(а):Входящий считает количество белых шляп. Если нечетное - встаёт на первую линию, иначе - на вторую.

По его действиям (по изменению четности) предыдущий человек точно узнает, какая шляпа на нем и перейдёт на нужную линию.

Интересно. Надо твой вариант покрутить и разобраться в нем. У меня есть другое решение, без проверки на четность.
А что делать последнему? Ему-то кто подскажет, правильно ли он встал?

Правильно.
Теперь усложнение ситуации: каждый входящий имеет право становиться только на линию 1. На линию 0 можно только переходить. Остальные условия остаются без изменений.
Как быть в этом случае?