"Задача про концлагерь"
От: gbear Россия  
Дата: 26.05.04 08:26
Оценка: 2 (1)
Сильно не пинать если задачка уже мелькала...

См. задачу "Геноцид мудрецов", http://www.rsdn.ru/Forum/?mid=206124
Автор: vvaizh
Дата: 03.03.03

— Кодт

Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.

Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.

Вопрос — воспроизвести это решение

---
С уважением, Сиваков Константин.
Re: "Задача про концлагерь"
От: Andy_MAN Россия  
Дата: 26.05.04 08:32
Оценка: :)
Здравствуйте, gbear, Вы писали:

G>Сильно не пинать если задачка уже мелькала...


G>Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.


G>Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.


G>Вопрос — воспроизвести это решение


G>---

G>С уважением, Сиваков Константин.



Каждый называл цвет шапочки, стоящего перед ним человека? Так что-ли?
Re[2]: "Задача про концлагерь"
От: rus blood Россия  
Дата: 26.05.04 09:05
Оценка:
A_M>Каждый называл цвет шапочки, стоящего перед ним человека? Так что-ли?

Конечно... Если надеть на них шапочки попеременно черная-белая-черная-белая-... и т.д., то с таким советом всех убьют с первого раза, кроме, может быть первого, которому придется гадать.
Имею скафандр — готов путешествовать!
Re: "Задача про концлагерь"
От: UGN  
Дата: 26.05.04 09:16
Оценка: 20 (2)
Здравствуйте, 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 -- получает свой цвет.
Далее аналогично.
Re: "Задача про концлагерь"
От: Andir Россия
Дата: 26.05.04 09:16
Оценка:
Здравствуйте, gbear, Вы писали:

G>Сильно не пинать если задачка уже мелькала...


G>Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.


G>Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.


G>Вопрос — воспроизвести это решение


Тут чисто на игре слов можно построить решение.

Первый называет цвет шапочки следующего.
Следующий называет свой цвет шапочки например так:
называет цвет такой какой назвал первый — это означает у следующего такая же.
говорит "Бамбарбия киркуду" + называет цвет такой какой назвал первый — это означает что у следующего противоположный.
Далее пошла рекурсия

С Уважением, Andir!
Re: "Задача про концлагерь"
От: UGN  
Дата: 26.05.04 09:17
Оценка:
Здравствуйте, gbear, Вы писали:

G>Сильно не пинать если задачка уже мелькала...


Кажется была интересная задачка с 3-х цветными шапочками...
Re[2]: "Задача про концлагерь"
От: gbear Россия  
Дата: 26.05.04 09:40
Оценка:
Здравствуйте, 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 человек) вдруг кто ошибется...

Всмысле, решение верное — но хотелось бы его озвучить на уровне арифметики

---
С уважением, Сиваков Константин.
Re: "Задача про концлагерь"
От: Tan4ik Россия  
Дата: 26.05.04 10:02
Оценка:
Здравствуйте, gbear, Вы писали:

G>Значит так... В одном концлагере бытовал оригинальный метод расстрела. Заключенных выстраивали в косую колонну по одному. После чего, каждому на голову надевали шапочку — черную или белую (какую именно заключонный не видел... но видел какие шапочки на тех, кто стоит перед ним). Далее, начиная с хвоста колонны, к заключенному подходил палачь, приставлял к затылку пистолет и спрашивал: "какого цвета у тебя шапочка?" — если заключенный угадывал — он оставался жить, если нет — его убивали.


G>Дык вот, заключенные довольно быстро отыскали решение, при котором погибал только один человек... да и то не всегда. Хотя кол-во черных и белых шапочек, и их порядок постоянно меняли.


G>Вопрос — воспроизвести это решение


Одно решение уже привел UGN. Приведу некоторые более общие рассуждения.

Утверждение 1. Первый заключенный не может знать своего цвета, т.к. у него нет никакой информации.

Утверждение 2. Решение с одним трупом с вероятностью 50% оптимально, т.к. такое решение уже привел UGN, а лучше нельзя сделать из-за Утверждения 1.

Пусть цвета шапок с конца — x1,x2,x3...xN
Осталось определить функцию f, такую что
f(g(x1,x2,...,xN), x2,...,x(K-1),x(K+1),...,xN) = xK


Заметим, что каждый заключенный использует один бит информации и дает один бит информации. Чтобы выжили все (кроме возможно первого) нужно, чтобы все эти биты использовались, т.е.
f(g(x1,x2,...,xN), x2,...,x(K-2),0,x(K+1),...,xN) != f(g(x1,x2,...,xN), x2,...,x(K-2),1,x(K+1),...,xN)

Значит единственная возможная форма функции f —
f(g(x1,x2,...,xN), x2,...,x(K-1),x(K+1),...,xN) = g(x1,x2,...,xN) XOR x2 XOR ... XOR x(K-1) XOR x(K+1) XOR ... XOR xN
или
f(g(x1,x2,...,xN), x2,...,x(K-1),x(K+1),...,xN) = g(x1,x2,...,xN) XOR x2 XOR ... XOR x(K-1) XOR x(K+1) XOR ... XOR xN XOR 1


Другими словами, решение UGN является оптимальным и единственным с той лишь разницей, что мы для каждого заключенного можем выбрать какая шапка у него считается 1, а какая 0. Т.е. существует 2^(N-1) стратегий поведения заключенных.
---
С уважением,
Лазарев Андрей
Re[3]: "Задача про концлагерь"
От: Блудов Павел Россия  
Дата: 26.05.04 10:07
Оценка: :)
Здравствуйте, rus blood, Вы писали:

RB>Конечно... Если надеть на них шапочки попеременно черная-белая-черная-белая-... и т.д., то с таким советом всех убьют с первого раза, кроме, может быть первого, которому придется гадать.


Вы условие-то читали? Начинают с [b]последнего[b].
Он называет цвет шапочки впередистоящего. Так что тот уже знает,
какой у него цвет. Теперь его задача — не умереть самому и передать
великое знание о цвете впередистоящему.

Если его цвет совподает с цветом впередистоящего, он говорит "черный" или "белый"
Если нет, то "у меня черный" или "у меня белый".

Вот и все. Угадывать должен только самый последний.
--Павел.
... << RSDN@Home 1.1.3 beta 2 >>
Re[4]: "Задача про концлагерь"
От: rus blood Россия  
Дата: 26.05.04 10:19
Оценка:
БП>Вот и все. Угадывать должен только самый последний.
БП>--Павел.

Это слишком просто. Могли пристреливать за доп. слова.
Т.е. называть можно одно из двух слов — "черная" или "белая" (шапочка).
Имею скафандр — готов путешествовать!
Re: От модератора
От: Кодт Россия  
Дата: 26.05.04 10:34
Оценка:
Здравствуйте, gbear, Вы писали:

G>Сильно не пинать если задачка уже мелькала...


См. задачу "Геноцид мудрецов", http://www.rsdn.ru/Forum/?mid=206124
Автор: vvaizh
Дата: 03.03.03
Перекуём баги на фичи!
Re[5]: "Задача про концлагерь"
От: Блудов Павел Россия  
Дата: 26.05.04 11:19
Оценка: +2
Здравствуйте, rus blood, Вы писали:

RB>Это слишком просто. Могли пристреливать за доп. слова.

RB>Т.е. называть можно одно из двух слов — "черная" или "белая" (шапочка).

Тогда нужно, что какждый видел __всех__ впередистоящих.

В этом случае последний ничего не угадывает, от просто говорит "белая"
если впереди ЧЕТНОЕ количество белых и "черная" иначе.

То есть ставит флаг четности.

Тогда если 2-й с конца видит тоже ЧЕТНОЕ количество белых — значит у него черная.
иначе — белая. Он называет свой цвет. Если он назвал "белая" то флаг переключается.
Теперь чтобы у 3-го оказалась черная он должен видеть перед собой нечетное количество
белых.

Вот и все.
Павел.
... << RSDN@Home 1.1.3 beta 2 >>
Re[3]: "Задача про концлагерь"
От: achmed Удмуртия https://www.linkedin.com/in/nail-achmedzhanov-9907188/
Дата: 27.05.04 12:39
Оценка:
G>Здравствуйте, UGN, Вы писали:

G>Угу... Только мне "ксорит" не нравится. Етож заключенные, что такое сложение по модулю 2 они не знають

G>Да и ксорить в уме (если их 100 человек) вдруг кто ошибется...

G>Всмысле, решение верное — но хотелось бы его озвучить на уровне арифметики


последний считает количетво черных и, если оно четное, то говорит "черная", иначе — "белая".
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.