KRAK сказав(ла):Хоть и боян, но интересный Если кто-то уже знает ответ - не спешите хвастаццо, дайте другим подумать Также желательно решать головой, а не Гуглом или Яндехом
В тюрьму прибыли 17 преступничгов. Начальник тюрьмы сказал им, что завтра их посадят в изолированные камеры, они не смогут общаться друг с другом. Время от времени стражник будет кого-то из них отводить в специальную комнату. В этой комнате есть два выключателя, на одном написано "А", на другом - "В". Каждый из выключателей имеет два положения - вкл и выкл. Урик должен будет изменить положение только одного выключателя. Стражник может выбирать преступничгов в стихийном порядке, но наступит такой момент, когда каждый уголовничег побывает в комнате, может и не один раз.
Если ко мне подойдет один из преступничгов и скажет, что все мы, все 17 человек, уже побывали в комнате, я тотчас отпущу всех, в случае, если это правда. Если же нет, то всех вас немедленно кознят. Никто кроме вас не будет посещать комнату с выключателями. В каком положении выключатели находятся сейчас, я не помню. Итак, у вас есть сегодняшний день для обдумывания вашего положения. Завтра вас уже разведут по камерам. С этими словами начальнег ушел.
Предложите стратегию позволяющую уголовничгам НАВЕРНЯКА выиграть, считая, что они будут жить достаточно долго, чтобы побывать в этой комнате как угодно много раз каждый.
Учет конечно имеет место быть, однако самими зеками, причем одним человеком, но если он даже будет знать, что он - первый, это ведь не будет означать, что другие это будут знать, да и заходить они будут в комнату случайным образом: "в стихийном порядке" ...
Ferox сказав(ла):Ну, в принципе, я знаю как организовать учет в том случае если первый входящий знает что он первый, а остальным совершенно не обязательно знать кто именно первый, остальные действуют по алгоритму.
Dimoks сказав(ла):КРАК незримо с нами...
что я или совсем отупел... я даже не понял задание
ну предположем пусть клацают только один левый выключатель. через 50 дней скажут что уже 17 человек побывали там. никогда и никак надзиратель не вычилист говорят они правду или нет (могу поспорить) т.к. там всего 4 положения:
A:On, B:On
A:On, B:Off
A:Off, B:On
A:Off, B:Off
плюс надзиратель незнает начального положения.
Пусть начальное значение A:On, B:On (надзиратель его незнает)
1 A:On, B:On - первый пришел увидел и переключил.
2 A:Off, B:On - второй пришел
3 A:On, B:On - третий
.......
48 A:Off, B:On - может опять первый пришел (неважно)
49 A:On, B:On - может опять пришел второй (неважно)
50 A:Off, B:On
И говорят что все там были. А несколько человек из 17 никогда там не были. Ну и........... ?
Ну и как надзиратель догадается если он даже начального значения не знал?
Ну он и так всегда знает что он первый, т.е. первый раз в комнате, а следовательно дальше можно строить теории ...
Опиши алгоритм ...
Надзератель знает кого он пускал/не пускал в комнату, иначе зачем он нужен?, он
бред какойто...Нет. Мне нужно чтобы он знал, что он вообще первый, а не первый раз лично он в комнате.
Алгоритм очень простой - первый кого заводят в комнату - назначается счетчиком - он переводит выключатель А в положение "вверх" (а если он уже там, то просто клацает вторым выключателем).
Каждый заключенный кроме счетчика приходя в камеру первый раз, если выключатель А в положении "вверх" - клацает его "вниз", в противном случае клацает Б.
Приходя в комнату второй и последующие разы в любом случае клацает "Б".
Счетчик приходя в камеру, если А - "вниз" - клацает его, в противном случае - Б.
Счетчик считает число раз, которые ему пришлось клацнуть выключатель А. Когда клацнет 16 раз не считая первого - все заключенные побывали в камере.
Даже если "человек-счётчик" наклацает сам на первым выключателе 100000000 раз это не говорит о том что в комнате побывали всеСчетчик считает число раз, которые ему пришлось клацнуть выключатель А. Когда клацнет 16 раз не считая первого - все заключенные побывали в камере.
Чтобы обойти неопределенность в начальном положении выключателей, все заключенные вместо одного должны клацнуть по 2 раза, тогда знаком того, что все заключенные побывали в камере, хотя бы один раз, будет 2*(n-1) изменений выключателя А, насчитанных счетчиком.
Преступники договариваются,кто завтра пойдет,тот и счечик.Итак, у вас есть сегодняшний день для обдумывания вашего положения.
...сказал им, что завтра их посадят в изолированные камеры, они не смогут общаться друг с другом. Время от времени стражник будет кого-то из них отводить в специальную комнату...
... В каком положении выключатели находятся сейчас, я не помню...
Преступники не знают кто завтра пойдет и пойдет ли вообще.Октябренок сказав(ла):Преступники договариваются,кто завтра пойдет,тот и счечик.
Не зная кто счетчик, каждый может считать себя первым и сбрасывать выключатель А.Октябренок сказав(ла):На следующий день,зайдя в комнату он: если первый выключатель в положении "вкл." переводит его в "выкл."; если первый выключатель в положении "выкл.", дергает 2-й... и ВСЕ... начинает отсчет... 16 положений "вкл."