Это здорово! Я себе посадил зрение еще в далеком 88-м, когда обзавелся БК-0010 с совковым телевизором наидурнейшего качества. Так увлекся программированием на Фокале, что посадил в телеке красную пушку, ну и глаза (еще) на три с половиной пункта...



А я хотел предложить задачку посетителям твоего дневника (за неимением своего собственного ). Думаю. ты не будешь против - тебе ведь нравится устраивать разминки для мозгов? (Задачку мне предложила Obo-irina )http://www.diary.ru/~obo-irina/



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

Вопрос: можно ли заключенным разработать выигрышную тактику, если им позволят перед началом эксперимента собраться и обговорить ее? Если возможно, то в чем она заключается? Если нет, то чем это можно доказать?



=)

Apprehension приветствую

Ну, у меня зрение тоже не идеальное, посадила в старших классах, потом ухудшалось ещё и ещё. Наконец остановилось на -3/-1,5 (с такой вот разницей). Эх... комп с телеком - самые весёлые детские воспоминания. Даже программила в бейсике, Синклер у меня был



Задачка интересная, прорекламирую в новой записи, чтобы любители головоломок не пропустили Чёрт, сама с ходу не решу, это точно

Решение - заключённым вести свой собственный список и записывать каждого вызванного.



А с помощью лампочки по-моему нельзя. Потому что порядок случайный. То есть надо запомнить про каждого заключённого прошёл он или нет, а лампочка может "запомнить" только одного (если он сам её включит/выключит), или она может запомнить, например, чётный этот человек или нечётный.

Но вобщем 100 битов не влезают в 1 бит.



Ты никогда не знаешь, кто был последний. А последний должен сделать утверждение. Значит предпоследний должен дать ему знак, что больше никого не осталось. Но предпоследний никак об этом не может узнать, кроме как получив знак от предыдушего. А лампочка только одна - поменяв предпоследнего с последним, предпоследний получит чужой сигнал и закончит игру... все будут расстрелены.

Я уверен, решение должно быть...

Иначе-бы ни Ира ни Apprehension её не задали бы...



Я вот пока так подумал: если бы заключённых быфло двое, то решение - очневидное. А что делать если их больше - пока не понимаю...

Ну в принципе доказательство от обратного...



Допустим, что последний успешно отгадал, что он последний и закончил игру.



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



Значит по включённой лампочке он должен определить прошло перед ним всех 99 людей или меньше. Соответственно предыдущие должны таким способом включать и выключать лампочку, чтобы она была в нужном положении после 99 людей.



Но если учесть, что сначала лампочка выключена, то значит последний должен её получить включённую, иначе бы он закончил игру, прийдя первым.



Значит 99ый должен оставить после себя лампочку включённой. Но узнать, что он 99ый, он может только по лампочке - другой информации ему не даётся. Соответственно, он должен её включить, потому что если бы она уже была включена до него, то он бы закончил игру, думая что он последний.



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



Следовательно они не могут гарантировать победу.





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



Вобщем, если это доказательство правильное, то решение не существует.

Я раздумываю о том, что во времени мы не ограниченны. Можно подождать пока заключеного вызовут несколько (100) раз...

И этот заключённый может сам запоминать состояние лампочки... Может включать-выключать её в определённой последовательности...



У меня пока никаких конкретных идей, но думаю - это путь.

Сколько бы раз его не вызывали, всё названное мною остаётся верно.



Даже если организаторы могут вызвать кого-то несколько раз, никто их не заставляет так делать.

Они могут вызвать каждого по одному разу, а значит моё доказательство справедливо.

Sky Cry

Если всё сказанное тобой верно, то 3 заключённых тоже не смогут решить задачу. Тем не менее решение есть... не идеальное, но...



Пусть заключенных зовут Саша, Петя и Вася.

Решение о том, что в кабинете побывали все должен принять Вася.

Когда он зайдет в кабинет и увидит горящую лампочку - он запомнит.

Если зайдя в кабинет в следующий раз он увидит потухшую лампочку, значит побывали все.

С лампочкой он ничего делать не должен.



Саша, зайдя в кабинет в первый раз, должен включить лампочку.

Во все остальные разы он не должен ничего делать.



Петя, зайдя в кабинет и увидев включённую лампочку, может её выключить.

В этом месте план уходит от строгой формальности к вероятностям.

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

Если окажется так, что Вася включённой лампочки не увидел, то подождав некоторое время Петя может снова её включить...

Тогда что если сначала зайдёт Вася, а потом по очереди будут заходить Саша и Петя? Кто закончит игру? Никто и никогда.



Или даже просто зайдёт Вася, потом Петя, а потом через каждых 10 минут будут вызывать Сашу?



Получается нет гарантии, а то что при каком-то особенном случае можно выйграть - это никто не сомневался.

Sky Cry

Гарантии действительно нету. Но гарантии нет ни в каком случае, ведь Васю могут вообще никогда не вызвать вне зависимости от лампочки.



Решение существует только в предположении, что окранникам тоже нужно избавиться от заключённых. И они будут вызывать их в случайном порядке.



Решение которое я предложил, позволяет из фатального выбора - ошибка=смерть, сделать нефатальный: ошибка=ожидание.



при каком-то особенном случае можно выйграть - это никто не сомневался.

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

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



Мы, конечно, учитываем, что все честные, значит предположим, что игра заканчивается в определённое время, но заключённые не имеют часов, иначе бы просто напросто последний сказал, что все прошли.



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



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



Всё приводит к тому, что заключённым *надо* знать, когда придёт последний, чтобы сразу же закончить игру.

Заключённые просто напросто не могут расчитывать на повторения. Соответственно даже 3 бы не могли гарантировать выйгрыш.

Sky Cry

Заключённые просто напросто не могут расчитывать на повторения.

Увы, в этом случае я не знаю как им помочь.



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

Вечер добрый!

Интересно читать ваш ход мыслей =)

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



Прошу обратить внимание на условие: там не говорится, что тактика должна быть оптимальной и последний, вызванный сотым заключенный, должен тут же сделать заявление. Речь идет о только том, как и когда можно дать ГАРАНТИРОВАННО ИСТИННОЕ заявление. (Будем считать, что ни охранники, ни заключенные во времени не ограничены - ведь это не настоящая тюрьма, а просто задачка. =)) Ответ: ждать 10 лет, а после делать заявление не катит - охранники могут эти 10 лет вызывать одного и того же человека).



Скажу, что я вначале решил задачку для двух (гарантированно), для трех (гарантированно), на четырех вошел в ступор, а потом догадался =) А решение, как и все гениальное, очень простое =)))

И чтобы не было кривотолков, давайте считать, как и предлагал Паша, что охранники вызывают заключенных случайным образом. ))

Но повторяю, что по условию задачи тактика должна позволять давать ответ гарантированно, со стопроцентной вероятностью истинный.

То есть охранники обязаны всё время вызывать кого-то в любом порядке, хоть до бесконечности, пока заключённые не закончат игру?



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



Все остальные должны включить лампочку в первый же раз, когда они увидят её выключенную. (В первый и только первый раз.)





Ты про это решение говоришь?

Sky Cry

О! А ты чудесное решение предложила!

Я мужского пола

Sky Cry

сорри, не подумал

Ничего, не в первый раз... почему-то...

Sky Cry, да, именно про него! =)))

Более "оптимального" у меня тоже не получилось.

Да, а решение оказалось как всегда простым но далеко не очевидным Люблю я такие задачки, только вот решать разучилась, а жаль.



Apprehension, спасибо за задачку.



pash_ka, Sky Cry - интересная дискуссия



Sky Cry Ничего, не в первый раз... почему-то...

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



Приз в студию!!! Правда он, как всегда со странностями, приз-то

Аватарка(и) со скрытым смыслом, а вы как всегда не туда смотрели!





А приз похоже тоже расчитан не на мой пол.

Sky Cry аватарки романтичные такие редко бывают у парней. А смысл у них красивый не спорю, правда, наверное, каждый видит свой смысл



А приз я же сказала - со странностями Они, призы такие - чего хотят вытворяют.

Тебе они кажутся романтичными? Хммм, может по тому мне и нравятся...