Очередная задачка из олимпиады для детей

В тюрьму поместили 100 узников. Надзиратель сказал им:
"Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной.

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

Придумайте стратегию, гарантирующую узникам освобождение.

предлагаю обратиться в Европейский суд по защите прав человека )))

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

Лично я думаю это горцы из одноименных кинопроизведений

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

3 узника... (на этом мысль останавливается))))

Можно предложить такую схему:

1 человек включатель, 99 человек выключатели. Включатель номер 100. каждый включает или выключает ко-во раз 2 в степени (номер человека - 1). Когда включатель придёт в комнату и лампа не горит и это будет его 2 в степени 99-й раз включить лампу, то он может смело заявлять, что все успели побывать в комнате.

Например, для 3-х человек.

Номер 1 - 1 раз выключить
Номер 2 - 2 раза выключить
Номер 3 - 4 раза включить

Это основано на свойстве сумм степенного ряда (2 в степени н = равно сумме всех меньших степеней без единицы, но т.к. начальное положение "выключено", то сумма становится точной)

думаю все проще:
1 человек выключатель, 99 человек включатели.
Те, которые включатели, могут включить лампу только один раз (если конечно она была выключена, когда "включатель" вошел). А "выключатель", собственно, выключает лампу и считает сколько раз лампа была включена, когда он входил. Ну и как только он насчитает 99 заходов, когда лампа была включена, то может смело бежать к охраннику. :)

ясно.


Это сообщение отредактировал Shrike - 28/07/2005, 18:19

По-моему, не прокатит. Из условий задачи не вытекает, что их будут водить по очереди. Включили 99 раз - не значит, что были ВСЕ. Это только значит, что было 99 человек.

--------------------

Нельзя молиться за царя Ирода. Богородица не велит!

Дык необязательно по очереди. Ну пусть их будет 3-е, а не 100.
1 - выключатель
2 - включатели.
Изначально лампа выключена.
Пусть заходит "включатель1". Включил лампу.
Пусть заходит "выключатель". Выключил лампу. (считает - 1)
Опять заходит "включатель1". Ничего не делает (так как может включить только один раз).
Пусть заходит "выключатель". Лампа выключена. Счетчик остался = 1.
Пусть заходит "включатель2". Включил лампу.
Пусть заходит "выключатель". Выключил лампу. (считает - 2). Насчитал двоих включателей, идет к охраннику.

Угу. Уяснил. Спасибо за разъяснение.

--------------------

Нельзя молиться за царя Ирода. Богородица не велит!