Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.
Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.
Здравствуйте, gbear, Вы писали:
G>Сильно не пинать если задачка уже мелькала...
G>Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.
G>Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.
G>Вопрос — воспроизвести это решение
G>--- G>С уважением, Сиваков Константин.
Каждый называл цвет шапочки, стоящего перед ним человека? Так что-ли?
A_M>Каждый называл цвет шапочки, стоящего перед ним человека? Так что-ли?
Конечно... Если надеть на них шапочки попеременно черная-белая-черная-белая-... и т.д., то с таким советом всех убьют с первого раза, кроме, может быть первого, которому придется гадать.
Здравствуйте, gbear, Вы писали:
G>Вопрос — воспроизвести это решение
Последний ксорит цвета шапочек ( 0 — черный, 1 — белый )
всех впереди стоящих и называет результат (R n-1).
Если повезет, результат совпадет с цветом его шапочки ( C n).
Предпоследний ксорит названный предыдущитм оратором цвет (R n-1)
с цветом шапочек всех впереди стоящих (R n-2) -- получает свой цвет.( C n-1 )
Называет. Следующий делает R n-1 ^ C n-1 = R n-2.
Затем R n-2 ^ R n-3 = C n-2 -- получает свой цвет.
Далее аналогично.
Здравствуйте, gbear, Вы писали:
G>Сильно не пинать если задачка уже мелькала...
G>Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.
G>Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.
G>Вопрос — воспроизвести это решение
Тут чисто на игре слов можно построить решение.
Первый называет цвет шапочки следующего.
Следующий называет свой цвет шапочки например так:
называет цвет такой какой назвал первый — это означает у следующего такая же.
говорит "Бамбарбия киркуду" + называет цвет такой какой назвал первый — это означает что у следующего противоположный.
Далее пошла рекурсия
Здравствуйте, UGN, Вы писали:
UGN>Здравствуйте, gbear, Вы писали:
G>>Вопрос — воспроизвести это решение
UGN>Последний ксорит цвета шапочек ( 0 — черный, 1 — белый ) UGN>всех впереди стоящих и называет результат (R n-1). UGN>Если повезет, результат совпадет с цветом его шапочки ( C n). UGN>Предпоследний ксорит названный предыдущитм оратором цвет (R n-1) UGN>с цветом шапочек всех впереди стоящих (R n-2) -- получает свой цвет.( C n-1 ) UGN>Называет. Следующий делает R n-1 ^ C n-1 = R n-2. UGN>Затем R n-2 ^ R n-3 = C n-2 -- получает свой цвет. UGN>Далее аналогично.
Угу... Только мне "ксорит" не нравится. Етож заключенные, что такое сложение по модулю 2 они не знають
Да и ксорить в уме (если их 100 человек) вдруг кто ошибется...
Всмысле, решение верное — но хотелось бы его озвучить на уровне арифметики
Здравствуйте, gbear, Вы писали:
G>Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.
G>Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.
G>Вопрос — воспроизвести это решение
Одно решение уже привел UGN. Приведу некоторые более общие рассуждения.
Утверждение 1. Первый заключенный не может знать своего цвета, т.к. у него нет никакой информации.
Утверждение 2. Решение с одним трупом с вероятностью 50% оптимально, т.к. такое решение уже привел UGN, а лучше нельзя сделать из-за Утверждения 1.
Пусть цвета шапок с конца — x1,x2,x3...xN
Осталось определить функцию f, такую что
Заметим, что каждый заключенный использует один бит информации и дает один бит информации. Чтобы выжили все (кроме возможно первого) нужно, чтобы все эти биты использовались, т.е.
Другими словами, решение UGN является оптимальным и единственным с той лишь разницей, что мы для каждого заключенного можем выбрать какая шапка у него считается 1, а какая 0. Т.е. существует 2^(N-1) стратегий поведения заключенных.
Здравствуйте, rus blood, Вы писали:
RB>Конечно... Если надеть на них шапочки попеременно черная-белая-черная-белая-... и т.д., то с таким советом всех убьют с первого раза, кроме, может быть первого, которому придется гадать.
Вы условие-то читали? Начинают с [b]последнего[b].
Он называет цвет шапочки впередистоящего. Так что тот уже знает,
какой у него цвет. Теперь его задача — не умереть самому и передать
великое знание о цвете впередистоящему.
Если его цвет совподает с цветом впередистоящего, он говорит "черный" или "белый"
Если нет, то "у меня черный" или "у меня белый".
Вот и все. Угадывать должен только самый последний.
--Павел.
Здравствуйте, rus blood, Вы писали:
RB>Это слишком просто. Могли пристреливать за доп. слова. RB>Т.е. называть можно одно из двух слов — "черная" или "белая" (шапочка).
Тогда нужно, что какждый видел __всех__ впередистоящих.
В этом случае последний ничего не угадывает, от просто говорит "белая"
если впереди ЧЕТНОЕ количество белых и "черная" иначе.
То есть ставит флаг четности.
Тогда если 2-й с конца видит тоже ЧЕТНОЕ количество белых — значит у него черная.
иначе — белая. Он называет свой цвет. Если он назвал "белая" то флаг переключается.
Теперь чтобы у 3-го оказалась черная он должен видеть перед собой нечетное количество
белых.
G>Здравствуйте, UGN, Вы писали:
G>Угу... Только мне "ксорит" не нравится. Етож заключенные, что такое сложение по модулю 2 они не знають G>Да и ксорить в уме (если их 100 человек) вдруг кто ошибется...
G>Всмысле, решение верное — но хотелось бы его озвучить на уровне арифметики
последний считает количетво черных и, если оно четное, то говорит "черная", иначе — "белая".