:: Игры Разума
Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
В общем в одной из тюрем заключенным предложили такую схему - есть шанс освободится досрочно (но не всем, как повезет или как продумают), прямо сегодня. Но для этого играем в небольшую игру - заключенные выстраиваются в одну колонну, каждому на затылке пишут число 0 или 1. Каждый, кроме первого, видит числа впередистоящих, но не знает свое число. Начиная с хвоста надзиратели подходят и спрашивают, какое число у этого зэка на затылке. Если он называет правильное число - его отпускают, если нет - расстреливают (ну, такой русский рулетка). Свое число он называет громко, все остальные слышат его ответ. До начала игры заключенные могут посовещаться и выбрать стратегию для спасения наибольшего числа своих собратьев.

А какую стратегию предложили бы вы?

P.S. В зависимости от четности числа заключенных гарантированный успех при тупой стратегии составляет около 50%.


------------------
"Veni, vidi, vici!"(с)




Исправлено 1 раз(а). Последнее : sphinx, 13.08.12 12:33
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

Сообщений: 4203
Откуда: Москва
Дата регистрации: 11.11.2008
Ну если они знают правила и могут договориться, то спасутся либо все, либо все, кроме первого (в смысле того, кто называет свое число первым), если ему не повезет.



Исправлено 5 раз(а). Последнее : akvvohinc, 12.08.12 05:16
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

Сообщений: 4203
Откуда: Москва
Дата регистрации: 11.11.2008
По этой (как ты написал - тупой) стратегии точно спасутся 50% человек, а остальные спасутся с вероятностью 0.5, то есть в среднем могут спастись 75% заключенных.

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

Подтверди, если это так.



Исправлено 4 раз(а). Последнее : akvvohinc, 12.08.12 03:02
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

Сообщений: 4203
Откуда: Москва
Дата регистрации: 11.11.2008
А может, все же выживут все, кроме, возможно, первого?

Например, так:
1) первый сообщает второму его номер и его расстреливают с вероятностью 0.5.
2) каждый последующий, называя свой номер, каким-либо кодом сообщает впередистоящему его номер.
Например, "ноль" означает, что у впередистоящего 0, а "нуль", что у него 1.
"Один" - что у впередистоящего 1, а "единица" (или "адын"), что у него 0.

Или все по-честному и в этом направлении копать не надо?



Исправлено 1 раз(а). Последнее : akvvohinc, 12.08.12 05:12
Ratings: 0 negative/0 positive
Re: Заключенные
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
sphinx
заключенные выстраиваются в одну колонну
И после "маркировки" они не могут перемещаться?
sphinx
Каждый, кроме первого, видит число впередистоящего
Только одного впередистоящего, или всех кто впереди?
sphinx
Если он называет правильное число - его отпускают
Что конкретно он может говорить? Или делать (скажем присядать, подпрыгивать, кашлять или по иному "семафорить" соседу)?
Т.к. например, если видны числа ВСЕХ впередистоящих, и говорить можно что угодно, то банально последний в очереди переводит 0/1 всех впередистоящих (это по сути двоичное число) в десятичное число и называет его - его шлёпают, зато все остальные (предположим что они с арифметикой все знакомы, хоть и зэки) спасаются

"Гарантированый успех при тупой стратегии" - это я так понимаю число гарантированно спасающихся, но, как справедливо заметил Сергей, к этим 50% следует добавить ещё 25% которые спасутся по теории вероятности - т.е. называя "чужое" число случайно попадут в своё - конечно, если надзиратели случайно пишут числа, а не намеренно их "строго чередуют".


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Заключенные
Extortioner

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005
В принципе, если самый задний видит номера всех кто стоит впереди, то он может назвать число, которое соответствует максимально часто встречающемуся значению. Тогда, если каждый последующий будет повторять это число, большая часть заключённых выживет.
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

Сообщений: 4203
Откуда: Москва
Дата регистрации: 11.11.2008
Цитата:
Т.к. например, если видны числа ВСЕХ впередистоящих, и говорить можно что угодно, то банально последний в очереди переводит 0/1 всех впередистоящих (это по сути двоичное число) в десятичное число и называет его.
Если б это было так, то ему даже не нужно было бы получать десятичное число - он бы мог просто назвать двоичное (чем оно хуже?).
Если только для "потянуть время перед расстрелом"

PS
А вообще даже при не слишком длинной очереди безошибочный перевод в уме двоичного числа в десятичное и обратно, да еще под угрозой расстрела... Это ж какие умы там должны сидеть?
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Цитата:
Возможно, для них это и есть лучший выход, но я подозреваю, что задача - максимально повысить гарантированное количество спасенных, даже если для этого остальным придется "пожертвовать собой".

Да, все верно.


------------------
"Veni, vidi, vici!"(с)
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
-


------------------
"Veni, vidi, vici!"(с)




Исправлено 1 раз(а). Последнее : sphinx, 13.08.12 12:36
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Цитата:
"Гарантированый успех при тупой стратегии" - это я так понимаю число гарантированно спасающихся, но, как справедливо заметил Сергей, к этим 50% следует добавить ещё 25% которые спасутся по теории вероятности - т.е. называя "чужое" число случайно попадут в своё - конечно, если надзиратели случайно пишут числа, а не намеренно их "строго чередуют".

Нет, не будет дополнительных 50% (от 50%) - ибо это вероятность, а не гарантия. Они все могут НЕ угадать, тогда спасутся только те, кто слышал свою цифру. По теории вероятности может много разных казусов произойти - например, пройти рота солдат - для спорящих, какова вероятность, что первые 40 человек окажутся мужчинами.


------------------
"Veni, vidi, vici!"(с)
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Цитата:
И после "маркировки" они не могут перемещаться?

Не могут.


------------------
"Veni, vidi, vici!"(с)
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Цитата:
Только одного впередистоящего, или всех кто впереди?

Всех впередистоящих.


------------------
"Veni, vidi, vici!"(с)




Исправлено 1 раз(а). Последнее : sphinx, 13.08.12 12:31
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Цитата:
Что конкретно он может говорить? Или делать (скажем присядать, подпрыгивать, кашлять или по иному "семафорить" соседу)?
Т.к. например, если видны числа ВСЕХ впередистоящих, и говорить можно что угодно, то банально последний в очереди переводит 0/1 всех впередистоящих (это по сути двоичное число) в десятичное число и называет его - его шлёпают, зато все остальные (предположим что они с арифметикой все знакомы, хоть и зэки) спасаются

Он может только назвать цифру, наугад, или исходя из какой-либо стратегии.

P.S. Подумайте для начала для троих заключенных. ;)


------------------
"Veni, vidi, vici!"(с)
Ratings: 0 negative/0 positive
Re: Заключенные
Extortioner

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005
Не, ну если так подходить, то смысл кодировать очень даже есть -

Петя

Вася

Серёжа

Серёжа не знает какая у него цифра, но видит Васин 0, он говорит - "нОль" и тут уже что с Серёжей будет по идее без разницы - ну угадал он своё число, значит будет жить, не угадал, ну чтож, он будет единственным убитым. Вася видит, что у Пети 1, и знает, что "нОль", обозначает, что у него на затылке написано 0. Но ему надо донести до Пети информацию, что у того на затылке 1, он говорит "нУль", теперь Петя знает, что у него на затылке единица.

Это я, вроде бы как решение akvvohinc расписал для троих заключённых.

Ну, или, если без коверканья слов, то может можно слово "Тоже" говорить Типа "Тоже ноль", обозначает, что у тебя-то ноль, а вот у следующего единица.

Кстати, а если уж совсем извращаться, то можно длительностью слов кодировать или тембром речи кодировть. Типа "Н-о-о-о-ль!" это одно, а "Ноль!" это другое



Исправлено 2 раз(а). Последнее : Extortioner, 13.08.12 12:09
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Нельзя интонацией, тембром и пр. подавать условные сигналы - можно только ровным голосом назвать одну из цифр "0" или "1".


------------------
"Veni, vidi, vici!"(с)
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
akvvohinc
А может, все же выживут все, кроме, возможно, первого?
Например, так:
1) первый сообщает второму его номер и его расстреливают с вероятностью 0.5.
2) каждый последующий, называя свой номер, каким-либо кодом сообщает впередистоящему его номер.
Например, "ноль" означает, что у впередистоящего 0, а "нуль", что у него 1.
"Один" - что у впередистоящего 1, а "единица" (или "адын"), что у него 0.

Или все по-честному и в этом направлении копать не надо?

Там все по-честному.


------------------
"Veni, vidi, vici!"(с)
Ratings: 0 negative/0 positive
Re: Заключенные
Extortioner

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005
Хм, что-то мне подсказывает, что тут можно покопать в сторону использования логической функции AND... вот только что именно копать, пока не понятно

Можно попробовать оттолкнуться от того, что предыдущий человек знает (или предполагает) какая у него цифра на затылке, тогда тут прям интересные зависимости можно повыкавыривать.

К примеру самый задний человек всегда называет цифру впереди стоящего человека. Повезёт ему или нет, как я уже говорил, это дело случая, но после этого у второго человека уже будет какая-то определённость. Теперь надо думать в сторону объединения его цифры и цифры впередистоящего человека. Тут возможны два варианта - либо этот второй видит, что и у него и у третьего (с конца) цифры совпадают, и тогда одно развитие ситуации, либо он видит, что цифры не совпадают и тогда это другое развитие.
На самом деле дополнительным кодом для впереди-стоящего человека будет не только названная цифра, но и смерть предыдущего зэка.
То есть они могут договориться, о самопожертвовании ради впередистоящего человека. То есть если предыдущий сказал цифру и умер, значит это твоя цифра, и если перед тобой стоит зэк с такой же цифрой как у тебя, то ты её говоришь и живёшь, если же у впередистоящего зэка цифра отличается от твоей, то ты называешь его цифру и умираешь. Но это какой-то странный алгоритм То есть если последовательности 0 0 0 0 0 1 1 1 1 1 1 достаточно длинные, то хорошо, а если получится 0 1 0 1 0 1, то умрут все

Но основная мысль, что сигнал на самом деле можно зашифровать при помощи смерти предыдущего и названной цифры, мне кажется так.
Ratings: 0 negative/0 positive
Re: Заключенные
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Если "всё по честному", то ты оставляешь, пожалуй, единственный вариант решения (при нём гарантии выживания не имеет только первый зэк - остальные спасаются).


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Заключенные
vk65

Сообщений: 402
Дата регистрации: 08.04.2008
Igor Korolyov
Если "всё по честному", то ты оставляешь, пожалуй, единственный вариант решения (при нём гарантии выживания не имеет только первый зэк - остальные спасаются).
Думаю, при таком варианте спасутся двое из каждой тройки. Первый называет чётность, после этого второй и третий назовут свои числа. А четвёртому снова придётся называть чётность и т.д.
Ratings: 0 negative/0 positive
Re: Заключенные
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Нет, если они умеют считать до двух (ну или время на ответ не ограничено), и в условии таки дано что зэки видят ВСЕ числа перед собой (и соответственно могут узнать сколько перед ними "единичек"), и слышат ВСЕ сказанные ранее числа, то спасутся все кроме первого.


------------------
WBR, Igor
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 4 (Гостей: 4)

© 2000-2024 Fox Club 
Яндекс.Метрика