bagi
участник
Регистрация: 03/02/2004
Сообщения: 77
Из: С-Пб,Выборгский район
|
|
Имеется тюрьма. В нее посадили несколько человек, причем пожизненно. Но тюремщики предложили такой вариант спасения: вы сейчас на один день собираетесь вместе и принимаете какое-то решение. Задача для вас простая: в тюрьме есть комната с лампой и обыкновенным выключателем. В эту комнату мы будет совершенно произвольным образом водить каждый день одного из заключенных. Все что он может, это включить или выключить лампу. Может ее не трогать, как хочет. Если заключенные в какой-то момент времени скажут, что вот все, все были в комнате хотя бы по разу, то их всех выпускают. Если неправильно скажут, всем расстрел. Изначально лампа выключена. После одного дня договоренностей их всех посадят в разные камеры, и водить будут так, что другие не будут знать, кого водили. Как заключенные поймут, что в комнате с лампой были все?
По многочисленным просьбам ОТВЕТ: Заключенные выбирают человека, который будет считать. Назовем его "счетчик". "Счетчик" может ТОЛЬКО ВЫКЛЮЧАТЬ лампочку. Если лампочка не включена, то он ничего не делает. Остальные могут ТОЛЬКО ВКЛЮЧАТЬ лампочку (и ТОЛЬКО один раз), если лампочка уже горит, то остальные просто сидят. И если человек уже включал лампочку, то он ее не включает. Таким образом, когда "счетчик" выключит лампочку столько раз, сколько в камерах людей (без него), то это будет означать, что они все там побывали.
http://www.rus-net.org/forum/index.php?s...c=972&st=75 там много таких задач
-------------------- Лизуся(23.06.94) и Евгений(03.08.99)
|
eugen
ветеран
Регистрация: 04/04/2004
Сообщения: 654
Из: С-Пб, Техноложка
|
|
Разводка! Про счетчика ничего в условиях не было. С таким же успехом можно сказать: ОТВЕТ-"Пахан" договаривается с надзирателем, что каждого зэка посетившего заветную комнату первый раз вечером "метелят" дубинками. "Пахан" слышит крики и делает зарубки на стене камеры. Когда у "пахана" накопится зарубок по числу заключенных-он попадает под амнистию.
-------------------- Наверное, при ценах на нефть выше $50/барр. управлять Россией могла бы и лошадь.(с)
|
Михаил
Регистрация: 16/01/2002
Сообщения: 4111
|
|
Я не понял, если закодит зэк 1, включает лампочку, после заходит зэк 2, что ему делать?
-------------------- фотогалерея цифровых фотографий
|
Olia
активный участник
Регистрация: 15/01/2004
Сообщения: 372
Из: Питер, Охта
|
|
Ничего не делать.
Когда-нибудь (они же сидят бесконечно) может случиться такое событие, что он войдет в очередной раз и лампочка будет выключена, и он сможет 1 раз за свою жизнь ее включить.
Таким алгоритмом можно добиться, что ведущий будет рапортовать только тогда. когда каждый и зеков хотя бы раз (а может и больше) побывал в камере.
-------------------- Оля
|
Селена
активный участник
Регистрация: 11/12/2002
Сообщения: 394
|
|
ннп За один день в комнату заводят только одного из 100 заключенных. Чтобы понять, что в комнате побывали все из 100 заключенных, счетчик-ведущий должен будет побывать в комнате не менее 99 раз. По теории вероятностей на это ему потребуется не менее 9900 дней, т.е. более 27 лет. За это время кто-то из заключенных умрет и понять был ли он до смерти в комнате или нет не представляется возможным. Т.е. теоретически алгоритм решения задачи верен, но при допущении, что все заключенные молоды и здоровы и точно проживут столько лет. Или нужно меньшее количество заключенных или более частое посещение комнаты.
|
mamamasha
элита
Регистрация: 07/04/2004
Сообщения: 1594
Из: м "Техноложка"
|
|
а по какому предмету эта задача? Какой возраст ребенка? Я думала так: Каждый зк проводит манипуляцию с выключателем только 1 раз (в следующие разы ничего не делает). Ведкщий при этом считает, сколько раз загорелась-выключилась лампочка. Соотв-но 100 манипуляций - 100 зк.
-------------------- Заходите к нам http://www.ser-shabalin.narod.ru
Маша+Сергей=Юля и Никуля (5.11.2001)
|