Две тюремные задачки
Задача 1
В тюрьму собираются посадить 100 зэков в одиночные камеры. Каждого время от времени будут выводить прогуляться в коридор, где есть один большой рубильник. Во время прогулки каждому зэку разрешается только либо переключить рубильник, либо ничего не делать. Всех зэков отпустят, только если один из них однажды выйдя в коридор скажет, что все зэки уже здесь побывали и не ошибется. А если ошибется, то выпускать зэков на прогулку вообще перестанут. Какой должен быть алгоритм поведения зэков, чтобы их гарантированно отпустили, если:
1.1. известно, в каком положении рубильник будет изначально
1.2. это не известно.
Задача 2
2.1. Двух зэков приговорили к смертной казни. Но дали им один шанс: надели на каждого по колпаку с цифрой. Каждая цифра может быть либо единицей, либо двойкой. Зэки могут смотреть друг на друга, но не обмениваться никакой информацией. По команде они должны одновременно выкрикнуть по числу. Если хоть кто-то угадает свое собственное число, то обоих отпускают. Как им необходимо договориться, чтобы гарантированно выжить?
2.2. Предыдущий пункт может решить и восьмиклассник, если немного подумает. Если Вы тоже с ним справитесь, то попробуйте предложить решение для трех человек, каждый из которых видит всех остальных, но написанные цифры уже могут быть от одного до трех.
2.3. Если вы справились и со вторым пунктом, то придумайте решение для произвольного числа зэков.
Ответы
1.1. Допустим, изначально рубильник поднят. Тогда каждый из первых 99-ти зэков должен ровно один раз опустить рубильник, во всех остальных случаях они не должны вообще ничего делать. Сотый зэк каждый раз только поднимает рубильник, если он опущен. Тогда когда он поднимет его в 99-ый раз он может гарантировать, что все зэки побывали в коридоре.
1.2. Всё происходит аналогично, но каждый из первых зэков должен опустить рубильник ровно два раза. Тогда, когда сотый зэк поднимет рубильник в 198-ой раз, либо все остальные зэки уже опустили его по два раза, либо один раз он опустил рубильник из исходного положения, и один из первых зэков опустил рубильник только один раз. В любом случае можно гарантировать, что все зэки побывали в коридоре.
2.1. Первый зэк называет ту цифру, которую видит, а второй - ту, которой не видит.
2.2. см. решение 2.3.
2.3. Пусть зэков n штук. Тогда первый называет такую цифру, чтобы сумма всех чисел на колпаках плюс названная делилась на n. Второй такую, чтобы давало остаток один при делении на n. Третий - чтобы два. И т.д. Каждый может так поступить, так как видит все остальные числа, и все они не больше n.
Задачки прислал Димитрий
Dmitry 24.12.2008
40 комментариев
гаджи 05 (0)
04.01.2013 16:25
ну тут же все понятно:) каждый из них видет же номер своего напарника, если у одного на шлеме цифра 1 то соответственно у другого цифра 2 ! Простая логика товарищи:)
Tai (42)
18.07.2013 15:12
гаджи 05: в условии сказано ЛИБО1 ЛИБО 2 => может быть и две 2 и две 1 так что не катит.тут нужно тоньше действовать. как? пока не придумал.
алексей (67)
11.12.2012 13:17
1 задачка. Должден быть ведущий зэк только ему позволено опускать рубильник вниз и он всегда это делает если рубильник наверху. Каждый должен залрать рубильник вверх по одному разу. Ведущий считает. 2. Для N зэков. Зная истинное значение суммы всех номеров по модулю N легко вычислить собственный. Сумма по модулю N имеет N возможных значений. Каждому по значению и пусть считают. Один наверняка угадает. Остальные наверняка не угадают. На самом деле именно этим занимаются в случае N=2 две один из которых повторяет номер, другой инвертирует. Только здесь лучше не 1, 2 а 0, 1
Саня97 (0)
25.05.2012 02:56
Зачем все так усложнять? Алгоритмы-шмалгоритмы…(для второй задачи), правильный по моему мнению ответ - ВСЕ зеки ,независимо от их колличества, должны называть ОДНУ И ТУ ЖЕ ЦИФРУ(будь то один, два…двадцать два)!;)
ыфф (0)
10.11.2011 11:56
Собака съедает гражданку лошадку, И с ней - гражданина кота
лёха (-16)
28.07.2011 16:17
Надо начальника подкупить.
Александр (0)
11.02.2011 17:35
2.1. Они должны договориться, что один скажет то число, которое на кепке у второго, а второй число, противоположное тому, что у первого.
Сухич (51)
21.03.2010 14:01
Интересные развлечения у нас в тюрьмах… Медведев в курсе?
Monomah (0)
16.03.2010 13:54
да не интересно и мутно
Monomah (0)
16.03.2010 13:54
да не интересно и мутно
Hypuk (0)
15.12.2009 15:00
Очень запутанно, и нудные задачи.. не вызывает интереса..
Jinx (0)
25.11.2009 15:57
"Вор должен сидеть в тюрьме, вот что людей интересует" (с) Так что не отпускать ни кого)) Если по существу - задачки бред.
М (0)
04.03.2009 15:48
Да бред какой то, загадки неинтересные, ответы неоднозначные, ЧУШЬ, беее…
НИКИ (0)
11.02.2009 08:30
По задаче 2.1: -зек знает что их всего двое, - видя нумерацию на колпаке товарища он поймет, что тоже пронумерован,и нумерация будет порядковая, -если друг "1-й", значит он по чифрой "2".Ничего сложного в задаче нет
Мосинька (-150)
02.10.2010 02:17
НИКИ: Каждая цифра может быть либо единицей, либо двойкой. Могут быть две единицы. Могут быть две двойки. Может быть единица и двойка. То же самое - для трёх
НИКИ (0)
10.02.2009 12:57
Чё париться, вопрос был в том, что один скажет, что здесь все были. имеется ввиду в коридоре. ПОНЯТНО, ЧТО ТАМ БЫЛИ ВСЕ, ВЕДЬ НЕ ПО … ПРОВЕЛИ В КАМЕРЫ, А ПО ЭТОМУ КОРИДОРУ!. и если их выводят на прогулку, то выводят всех.Никаких рубильников никто дергать не будет- руки в наручниках!, а единственный зэк никогда не выйдет в коридор, т.к. он зэк и шарахаться по коридорам ему никто не даст.
R0mka (18)
30.12.2008 03:01
По поводу формулы которую я написал ранее : x=(N-1)-(S mod N)+i. Если i брать не (1, 2,3 и тд.), а (0, 1, 2 и тд.) то: x = N - (S mod N) + i Или (S mod N) -N + x = i Если не вычитать N, то можно x внести в кообки и прибавить к сумме(так как вычисляется отстаток от деления на N), то ((S+x) mod N) = i Получилось как в ответе: называть такую цифру, чтобы сумма всех чисел на колпаках плюс названная давало остаток один при делении на N (0, 1, 2 и тд).
Димитрий (23)
29.12.2008 17:01
Да, пожалуй Ваш алгоритм правелен, но с оговоркой на неопределённо-долгое время.
R0mka (18)
29.12.2008 03:42
Димитрий, возможно в ответе задачи более простой и быстрый алгоритм решения чем мой, но в своем я пока не увидел проблемы которая бы делала его невыполнимым.
R0mka (18)
29.12.2008 02:34
Дмитрий, посмотрите что я писал: "1.2: 99 зэков будут только включать, только 1 раз и только если ВИДЕЛИ рубильник включеным… ". Если изначально рубильник выключен то ни один из 99 зеков его трогать НЕ будет, так как они НЕ ВИДЕЛИ его включеным, и первый раз переключит рубильник только избранный зек. Значит только избраный зек будет знать изначальное положение рубильника и знать до скольки считать.
Димитрий (23)
28.12.2008 17:12
Такая ситуация. Изначально рубильник выключен. Один из зэков включает его. А потом приходит "избранный" зэк и выключает. Тогда по алгоритму он должен будет ждать, пока выключений станет на 100 больше. Но этого никогда не случится! Проблема в том, что Ваш, ROmka, алгоритм не различает случаи, когда рубильник изначально включен, и когда его вначале включает один из зэков.
R0mka (18)
28.12.2008 03:48
Димитрий, конечно такое может случиться, но ведь нет ограничений на количество прогулок, и шансы остаются. Можно с таким же успехом сказать что одного из зэков так никогда и не выведут.
Димитрий (23)
28.12.2008 00:08
ROmka, может случиться такое, что один из 99-ти зэков будет постоянно натыкаться на включенный рубильник. Тогда он не сможет его никогда включить сам.
R0mka (18)
27.12.2008 08:16
1.2: 99 зэков будут только включать, только 1 раз и только если видели рубильник включеным. 1 зэк будет включать и выключать, и считать сколько раз. Как только количество выключений станет на 99 (или 100 если он первый раз выключал, а не включал) раз больше включений, значит все были.
bot (2)
26.12.2008 18:49
Еще наводящий вопрос,знают ли зеки,когда кого-то выводят,и слышат ли они что происходит в коридоре.
Димитрий (23)
26.12.2008 16:56
В первой задаче их выводят в неопределённое время. ROmka, Ваш алгоритм годится.
Teh Sentinel (0)
26.12.2008 15:01
Т.е., не после каждой прогулки, а после первого посещения корридора.
The Sentinel (0)
26.12.2008 14:55
Первая задача (подходит как для 1.1 так и для 1.2): после каждой прогулки зэк оставляет в корридоре шнурок от ботинка. ;)
R0mka (18)
26.12.2008 07:17
Чтото я еще раз подумал и пришел к другому алгоритму второй задачи, Пусть N количество зеков, (N-1) количество зеков или цифр которые видит каждый зек, S сумма цифр которые видит зек, и остаток от деления S на N запишем как (S mod N), и еще i - порядковый номер зека. Тогда каждый зек говорит число вычисленое по формуле: (N-1)-(S mod N)+i. Вроде вот так.
bot (2)
25.12.2008 23:55
В первой задачке их выводят в определенное время?
Димитрий (23)
25.12.2008 18:10
Да, может. Но когда-то всё равно каждый выйдет.
Piglette (136)
25.12.2008 16:12
а может быть, чтобы одни зеки выходили несколько раз, а другие - ни разу?
R0mka (18)
25.12.2008 10:25
1.2 если изначальное положение рубильника неизвестно то главный зек может с 50% вероятностью сказать переключив рубильник 99 раз.
R0mka (18)
25.12.2008 06:43
Вот что я придумал про зеков из первой задачи: 99 зеков будут только включать рубильник и только один раз, и 1 самый главный зек будет только выключать и считать сколько раз он выключил. Как только он 99 раз выключит то значит все зеки здесь побылали( это если знать что рубильник изначально был выключен, если изначально он был включен то ему надо на 100 раз выключить).
R0mka (18)
25.12.2008 05:23
2.3 Алгоритм вроде такой для N зеков. Каждый зек слаживает все числа что видит и вычисляет остаток от деления на N, затем прибавляет свой порядковый номер(если цифра получилась больше N то опять вычисляет отсток от деления на N).
R0mka (18)
25.12.2008 05:17
Если я правильно понял алгоритм то 2.2: есть зеки (первый, второй, третий). Каждый слаживает цифры которые видит и вычисляет остаток от деления на 3, потом прибавляет свой порядковый номер(первый, второй, третий), если получилось больше трех то опять вычисляет отстаток от делния на 3. Если у всех одинаковые то все выкрикнут разные цифры, если разные то второй отгадает, и в остальных случаях вроде должно сработать.
R0mka (18)
25.12.2008 03:18
Задача 2.1: надо чтобы один из них кричал цифру которую видит на колпаке у другого, а второй противополжную цифру которую видит на колпаке первого( если 2 то 1 , если 1 то 2). Таким образом если у них одинаковые цифры то оба крикнут разные цифры и один из них угадает, если протовоположные, то угадает второй ответивший противоположную цифру
misheln (8)
24.12.2008 23:30
Они договорились так. Если я буду на тебя смотреть говори 1, если нет то говори 2.
Димитрий (23)
24.12.2008 18:50
В первой задаче зэки ходят в коридор только поодиночке, а во второй сказано же, что нельзя обмениваться информацией!
XAVEN (-12)
24.12.2008 15:02
Ну как бы опять условия точно не указаны. Ну вот в первой их выводят по отдельности,или можно выводить когда их много? Во второй как бы можно если глаз один прикрыт -1.если открыты-2.Также для троих.закрыть оба,закрыть один,вообще не закрывать - 1,2,3 соответственно.)