:: Игры Разума
Re: Заключенные
vk65

Сообщений: 402
Дата регистрации: 08.04.2008
Согласен. Каждый будет способен просчитать чётность/нечётность впередистоящих и вычислить своё число.
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

Сообщений: 4203
Откуда: Москва
Дата регистрации: 11.11.2008
Цитата:
Первый называет чётность, после этого второй и третий назовут свои числа. А четвёртому снова придётся называть чётность и т.д.
Да нет, после уточнения условия задача существенно упростилась, и, действительно, гарантированно спасутся все, кроме первого.

Первый назовет "общую" четность.
Следующий видит четность впередистоящих и знает (от первого) четность с учетом своего номера - значит может узнать свой номер.
Остальные, зная общую четность, четность впередистоящих, и ответы предыдущих, вычисляют свой номер.
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!"(с)
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

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

Последний в очереди (начинающий) называет четность всех предыдущих заключенных. Допустим, четность единиц у них на затылках.

Он говорит "1", что означает, что количество единиц у впередистоящих нечетно (они так договорились).
Или он говорит "0", что означает, что количество единиц впередистоящих четно.

После этого его расстреливают с вероятностью 0,5 (R.I.P.)

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

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

И т.д. и т.п.

На примере 3 заключенных (их номера от последнего (начинающего) к первому):
1 - 1 - 0

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

Второй видит впереди четное количество единиц (ни одной). То есть для него получается вариант "нечетно-четно". Это означает, что у него "1", которую он и называет.

Третий никого перед собой не видит, но может вычислить "свою цифру". Количество единиц, названное первым, было нечетным, а второй назвал "1". Значит, количество единиц впередистоящих (их нет) + количество единиц в его собственном номере четно. Следовательно, у него самого может быть только "0".

Думаю, что можно сформулировать этот алгоритм и как-то попроще...



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

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Цитата:
Последний в очереди (начинающий) называет четность всех предыдущих заключенных.

Ога, все верно. Последний называет общую четность заключенных от 1 до n-1 (свою цифру ведь все равно не знает).


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




Исправлено 1 раз(а). Последнее : sphinx, 14.08.12 07:18
Ratings: 0 negative/0 positive
Re: Заключенные
Extortioner

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005
Нашёл аналог этой задачи на сайте www.braingames.ru - оказывается у неё сложность = 2 (максимальная на этом сайте - 5).
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

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

После того, как очередь выстроилась, и номера у всех были написаны, каждый заключенный делает следующее:

Исходное положение - пальцы руки, сжатые в кулак.

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

Далее, когда предыдущие заключенные начинают называть свои номера, эта процедура продолжается - если называется "1", его палец "переключается" (а нули игнорируются).

При этом когда очередь доходит до него самого он просто смотрит на свой палец - если тот отжат, называет "1", если прижат - "0".

На примере 4 человек с номерами:
1 - 1 - 0 - 1

Например, для 3-го с конца заключенного (у которого "0"):

- "обработал" единицы впередистоящих (палец стал в положение "отведен");
- первый назвал свое число = "0" и его увели на расстрел (палец остался в положении "отведен");
- следующий назвал свое число = "1" (палец стал в положение "прижат");
- подошла очередь нашего зека - он видит прижатый палец и называет свое число - "0".

Можно проверить - этот способ будет работать для каждого заключенного при любых комбинациях их цифр, так как основан на выведенной ранее формуле:
четность своего числа = (общая четность - четность впередистоящих - четность позадистоящих)
Для 3-го зека (0 - 1 - 1) = 0



Исправлено 1 раз(а). Последнее : akvvohinc, 14.08.12 13:50
Ratings: 0 negative/0 positive
Re: Заключенные
vk65

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

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

Ога. Или слепой.


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

Сообщений: 402
Дата регистрации: 08.04.2008
Не, это противоречит постановке задачи.
Все видят, что нарисовано у впередистоящих и слышат, кто что сказал.
А про конечности ничего не было.
Ratings: 0 negative/0 positive
Re: Заключенные
akvvohinc

Сообщений: 4203
Откуда: Москва
Дата регистрации: 11.11.2008
Раз они могут говорить, значит, у них есть хотя бы язык - он будет для него тумблером.
Ratings: 0 negative/0 positive
Re: Заключенные
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
Что мешает последнему заключенному назвать полное число в hex коде? Тогда каждый будет знать 0 или 1 у него на голове.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.




Исправлено 1 раз(а). Последнее : Влад Колосов, 15.08.12 13:50
Ratings: 0 negative/0 positive
Re: Заключенные
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Влад Колосов
Что мешает последнему заключенному назвать полное число в hex коде? Тогда каждый будет знать 0 или 1 у него на голове.
Ограничение задачи - я именно про это и спрашивал ранее


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Заключенные
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
А, понятно! Слона-то не приметил.
Хм, гарантировано выживет 50%, как мне кажется, плюс половина оставшихся наудачу (если работают большие числа). Т.е. до 75% в пределе.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.




Исправлено 2 раз(а). Последнее : Влад Колосов, 15.08.12 18:43
Ratings: 0 negative/0 positive
Re: Заключенные
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Влад. Читай тему полностью, тебя ждёт приятный сюрприз


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

Сообщений: 7
Дата регистрации: 20.08.2012
Ну впринципе 50/50 спсутся в любом случае)зэков не жалко
Ratings: 0 negative/0 positive
Re: Заключенные
sphinx
Автор

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

Зэки разные бывают. Есть педофилы и террористы, а есть и те, из кого признание силой выбили. И многие из зэков - прежде всего люди.


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




Исправлено 1 раз(а). Последнее : sphinx, 20.08.12 12:49
Ratings: 0 negative/0 positive


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

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

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