ERUDITOR.RU

57. 100 узников №2 (нумерация)

Снова в тюрьме оказались 100 узников. На этот раз им предстоит такое испытание. Их расставят по кругу и завяжут глаза. Каждому на голову наденут колпак, на котором будет написано число от 1 до 100. Причем любое из этих чисел может встречаться несколько раз. Затем глаза развяжут. Каждый узник будеть видеть числа остальных 99 узников, но не будет видеть своего. Если хотя бы один верно угадает, какое число написано на его колпаке, то всех отпустят. Если нет — всех казнят.

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

Никакого обмена информацией после написания чисел на колпаках нет.
Примечания
Шикарная сложная логическая задачка.
Продолжение темы про 100 узников/колдунов/мудрецов/визирей.
2007-08-31

Обсуждение


Задачи :: 100 узников №2 (нумерация)
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-09 23:32   »»


Непонятно
Что кроется под словом "действовать"?
Они могут меняться местами? Или делать какие-то ещё действия? Откуда поток информации?
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-10 04:21   «« #2 »»   Ответить


Один из узников будет условно считаться "первым" - по договоренности. После того, как узников расставят, следующий после него (по часовой стрелке, к примеру), будет условно считаться вторым и т.д. Если первый узник видит число 1, он подает знак, например, сжимает в кулак правую руку. Второй - если видит число 2... 100-ый - если 100. Если хоть одно чилсо встречается в единственном варианте, то тот из узников, который не видит его, но видит сжатый кулак, назовет свой номер. Если через некоторое время этого не происходит, то все разжимают кулаки и первый сжимает его снова, если число 1 он видит более, чем на одном колпаке... остальные делают то же самое. Если и этот вариант - "мимо", то "видит более, чем на двух колпаках" - и т.д, пока кто-то не сможет назвать свой номер. Запутаться легко, правда, учитывая, что узники все же люди, а не автоматы, но с чисто математической точки зрения вроде правильно. Правда, остается вопрос о допустимых действиях узников.
↓↓ 0 ↑↑   7777777 (3 / 130)   2007-08-10 10:39   «« #3 »»   Ответить


Вобщем, задачка недоделанная. В текущей формулировке есть решение ещё проще - один узник говорит другому число, которое у того на колпаке написано :)
↓↓ +4 ↑↑   eruditor (143 / 443)   2007-08-10 15:02   «« #4 »»   Ответить


Хорош к формулировкам придираться :)
Как там в оригинале им надо действовать - не знаю...
Но думаю, что ваши варианты не прокатят.

Никаких знаков подавать нельзя.
Переговариваться во время испытания тоже.
Короче говоря, можно только смотреть.
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-10 15:14   «« #5 »»   Ответить


Если никаких действий производить нельзя - то ясно, что решения нет.
Если можно, то без конкретизации того, какие именно действия, задачка бессмысленная.
И слово "придираться" тут как-то не очень подходит.
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-10 15:22   «« #6 »»   Ответить


Не знаю...
Формулировка встретилась именно такая.
Уточню...
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-10 15:24   «« #7 »»   Ответить


Такой вариант еще есть...
100 узникам на головы надели колпаки с числами из диапазона 1..100. Причем не обязательно, что на всех разные. К примеру, всем могли одеть колпак с числом 7, или половине колпак с числом 20, а второй половине с числом 10. Главное, что не меньше 1 и не больше 100. После этого всех их поставили по кругу. Каждый видит 99 чисел на головах других, но не своё. После этого, каждый пишет на листке бумаги число от 1 до 100 - предпологаемое число на своём колпаке. Общаться и подглядывать нельзя. Их всех отпустят, если хотя бы один угадает своё число.
Какой стратегии они должны придерживаться, если хотят, чтобы их гарантированно отпустили?
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-10 15:41   «« #8 »»   Ответить


Глупое решение...
Например, выбрать 1 узника, который будет в конце концов тем, кто угадает. Когда надевают колпаки - все видят, какой у него номер. Например - 50. Тогда начиная от 1 узника 50 чел. по часовой стрелке сразу пишут ответ (любой). 51-ый не пишет - типа "думает". По этой паузе, у 1 узника есть возможность посчитать сколько людей пишут, а сколько "думают". Потом остальные 49 дописывают любые ответы, а выбранный узник пишет точный номер.
↓↓ 0 ↑↑   lemoren (4 / 14)   2007-08-10 20:21   «« #9 »»   Ответить


Нормальное решение
Но что если их заставят написать свои числа строго одновременно?
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-10 22:18   «« #10 »»   Ответить


Не, решение не прокатит. В условии чётко сказано-никакой информации.
Я думаю, что можно (для большей точности формулировки задания) представить дело и так:
каждый испытуемый находится в кабине с односторонним стеклом. Никто не видит — чем там занимается испытуемый и есть ли вообще в ней кто-нибудь). Все могут видеть только табло с числом на кабине.
↓↓ 0 ↑↑   Валерий (10 / 25)   2017-02-16 09:31   «« #59 »»   Ответить


Я думаю, есть смысл всем договориться написать одинаковое число.
Проблема в том, что этого числа может и не быть...
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-10 23:17   «« #11 »»   Ответить


Значит, смысла нет :-)
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-10 23:52   «« #12 »»   Ответить


Дополнение
тогда например, чтоб часть писали левой рукой, часть правой... Все равно 1 узник будет немного отставать...
Или дать всем ста узникам заранее номера по часовой стрелке и только тот, порядковый номер которого будет соответствовать номеру на колпаке 1 узника будет писать левой рукой, а все остальные правой...
У всех этих вариантов одна проблема - если номер 1 узника - 100. так как кроме него остаются только 99
↓↓ 0 ↑↑   lemoren (4 / 14)   2007-08-10 23:56   «« #13 »»   Ответить


Или
9 узников справа от 1 будут "изображать" десятки, 10 слева - единицы.
Тогда решена проблема с 100, так как дополнительный узник просто может "играть роль" сотни
↓↓ +4 ↑↑   lemoren (4 / 14)   2007-08-10 23:58   «« #14 »»   Ответить


Сорри :)
под "изображением" я имела ввиду писать левой рукой - то есть отличаться от остальных
↓↓ 0 ↑↑   lemoren (4 / 14)   2007-08-11 00:00   «« #15 »»   Ответить


eruditor
Почему нет?
Другое дело, что надо придумать какую-то хитрость, чтобы сообщить всем во время испытания, какое число писать...
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-11 13:11   «« #16 »»   Ответить


Никакой информации
↓↓ 0 ↑↑   Валерий (10 / 25)   2017-02-16 09:33   «« #60 »»   Ответить


2 Zero
"придумать какую-то хитрость, чтобы сообщить " и есть суть задачи.
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-11 14:16   «« #17 »»   Ответить


Ага, я кажется придумал... Вернее, понял, что решение реально существует :)

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

Осталось функцию сочинить :)
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-11 14:32   «« #18 »»   Ответить


Пример функции для N=2 колдунов:
К1 пишет тот номер, который он видит на К2.
К2 пишет НЕ тот номер, который он видит на К1.

НЕ тот означает, что если видит "1" - пишет "2", видит "2" - пишет "1".
Осталось продолжить функцию на случай произвольного N.
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-11 18:10   «« #19 »»   Ответить


"...понял, что решение реально существует" - уже хорошо! :)
На одном "буржуйском" форуме попалась подсказка - что-то относительно того, что можно каким-то образом использовать сумму всех видимых номеров.
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-11 23:07   «« #20 »»   Ответить


Да, сумма - это правильно. Осталось чуть-чуть. Связать это с решением для N=2.
К сожалению, уезжаю в командировку, додумывать буду в дороге, без интернета.
Всем удачи :-)
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-12 15:01   «« #21 »»   Ответить


Надолго?
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-12 15:05   «« #22 »»   Ответить


Не знаю, как это можно привязать к сумме.... Там же ведь любое число может быть на колпаке. Ну, допусим, вижу я 99 колпаков, сумма чисел - 506. Что это мне дает??? На моем колпаке ведь все равно ЛЮБОЕ число от 1 до 100!!
про: если видит "1" - пишет "2", видит "2" - пишет "1"
ну и что, что видит 1, пишет 2, на колпаке-то может быть и 1 тоже (это если до n=2)
↓↓ 0 ↑↑   lemoren (4 / 14)   2007-08-13 11:06   «« #23 »»   Ответить


Все равно в любом случае кто-то из 2 угадает свое число. А бОльшего и не надо.
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-13 12:35   «« #24 »»   Ответить


Почему?
Если у обоих написаны "1", то следуя логике eruditor (видит "1" - пишет "2"), оба напишут "2" и никто не угадает
↓↓ 0 ↑↑   lemoren (4 / 14)   2007-08-13 15:15   «« #25 »»   Ответить


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

"К1 пишет тот номер, который он видит на К2.
К2 пишет НЕ тот номер, который он видит на К1".
↓↓ 0 ↑↑   Zero (38 / 335)   2007-08-14 19:49   «« #26 »»   Ответить


Сорри, действительно не заметила :)
↓↓ 0 ↑↑   lemoren (4 / 14)   2007-08-14 20:29   «« #27 »»   Ответить


Согласен с eruditor
Нумеруем всех от 1 до k (общий случай, на каждом может быть число от 0 до k-1, суть та же). 1-й считает сумму всех чисел других колпаков и берёт остаток от деления на k. Затем от k отнимает полученное число и записывает. 2-й тоже считает сумму всех и добавляет к ней 1, берёт остаток от деления на k и отнимает от k полученое число. 3-й считает сумму всех и +2 и т.д... k-й считает сумму всех + (k-1)..
Проверял для k=3 и 4. Нужно доказать общее
↓↓ 0 ↑↑   igar (10 / 119)   2007-08-16 13:56   «« #28 »»   Ответить


igar вроде прав
Решение пришло на вторые сутки. Похоже, что именно такое, как написал igar, но у него не очень понятно.

Итак. Не вполне строгое, но интуитивно просветляющее решение:

Обозначим истинную сумму всех N=100 написанных чисел через S.
А остаток от деления S на N - через q.
Ясно, что q может принимать значения от 0 до N-1.
Пронумеруем узников числами от 0 до N-1. Теперь каждый отвечает за своё значение q. И каждый узник (с номером k), видя сумму всех остальных чисел (s_k), выбирает себе такое число x_k (в диапазоне 1..100), чтобы в результате полная сумма (s_k + x_k) давала при делении на N остаток k (тот, за который его выбрали ответственным).
В результате, в точности у одного узника предполагаемый им остаток (s_k + x_k)//(N) окажется равным истинному значению = q. А это возможно лишь если произнесённое им число (x_k) равно истинному значению, написанному на нём.

P.S. Кстати, мне кажется, что в условии числа, которые на них написаны, могут быть не (1..99), а (1..100).
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-08-31 00:24   «« #29 »»   Ответить


Нашли закономерность там, где её нет. На любое ваше решение можно предложить вариант, при котором никто не отгадает своё число.
Для каждого из узников число на своём колпаке является случайной величиной, никак не зависящей от других.
При невозможности обмена информацией решения просто не существует.
↓↓ 0 ↑↑   Kkk (0 / 1)   2019-08-29 10:26   «« #65 »»   Ответить


Я бы даже сказал не (1..99), а (0..99), т.к. в остатке при делении на 100 мы 100 не получим. )
↓↓ 0 ↑↑   igar (10 / 119)   2007-09-03 10:47   «« #30 »»   Ответить


Ну, эт понятно :-)
Суть в том, что чисел везде 100 штук, а не 100 и 99.
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-09-03 14:34   «« #31 »»   Ответить


А не проще было бы договориться всем смотреть на выбранное число, а человек, на которого смотрят поймет, что у него именно это число
↓↓ 0 ↑↑   alo (0 / 1)   2008-01-07 14:22   «« #32 »»   Ответить


Всех узников пронумеровать. Первый будет смотреть на того, на ком видит цифру 1. Второй - на того, на ком видит 2 и т.д. Если видит нескольких человек с одинаковыми числами на колпаке, то смотрит на любого, не отрываясь, долго. Не видит ни одного- опускает глаза в пол. Система не сработает лишь в том случае, если каждый получит "свой" номер.. Но тогда правильный вывод можно будет сделать после продолжительного молчания.
↓↓ 0 ↑↑   7777777 (3 / 130)   2008-01-14 15:50   «« #33 »»   Ответить


Всех узников пронумеровать. Первый будет смотреть на того, на ком видит цифру 1. Второй - на того, на ком видит 2 и т.д. Если видит нескольких человек с одинаковыми числами на колпаке, то смотрит на любого, не отрываясь, долго. Не видит ни одного- опускает глаза в пол. Система не сработает лишь в том случае, если каждый получит "свой" номер.. Но тогда правильный вывод можно будет сделать после продолжительного молчания.
↓↓ 0 ↑↑   7777777 (3 / 130)   2008-01-14 15:51   «« #34 »»   Ответить


Дополнение к последнему.
Нумерация может быть условной: первый номер присваивается конкретному человеку, второй - стоящему от него слева и т.д.
↓↓ 0 ↑↑   7777777 (3 / 130)   2008-01-15 14:46   «« #35 »»   Ответить


Fibonacci
Какая "передача информации"? Узники "просто смотрят".
↓↓ 0 ↑↑   7777777 (3 / 130)   2008-01-31 15:51   «« #36 »»   Ответить


alo чуток неправільно сказал
выберем главаря, пусть он будет 1.
ход рассужденія такой:(от лица главаря)
Узник который будет стоять возле меня( 1) будет первым, итак, если меня на колпаке 1 , то только он на меня смотрит, если 2 то узник, стоящий рядом с ним тоже на меня смотрит итак, сколько людей на меня смотрят( начало от узника , который стоит , допустим слева от главаря) то число у меня на колпаке ,)
↓↓ 0 ↑↑   Voland (0 / 4)   2008-04-25 21:18   «« #37 »»   Ответить


А что если они просто пронумеруются от 1 до 100 и каждый назовет свой номер?! =)
↓↓ 0 ↑↑   Bugaboo (0 / 7)   2008-04-27 13:28   «« #38 »»   Ответить


А если на Физтех наконец перестанут брать кретинов?! :(
↓↓ 0 ↑↑   eruditor (143 / 443)   2008-05-01 07:44   «« #39 »»   Ответить


Решение(извиняюсь что повторяюсь с эрудитор, оно такое же, но я его искал целый день, выкладываю свои мысли)
Возьмём сумму всех чисел за S, тогда (S mod 100) даёт в остатке K
Если узнику сказать число К, он без проблем узнает своё число, так как К=0,99 то всем узникам даём своё К (тоесть пусть каждый считает своё К)
Найдётся узник, для которого К совпадёт!
↓↓ 0 ↑↑   Seryoga (0 / 8)   2008-05-23 01:49   «« #40 »»   Ответить


Это интересно
что найдётся ровно один узник, который угадает число;
нельзя договориться, чтобы никто не угадал число;
можно так договориться, чтоб все или угадали свои числа или никто не угадал;
ЗЫ это самая интересная задача из которых я видел за последнее время
↓↓ 0 ↑↑   Seryoga (0 / 8)   2008-05-23 01:53   «« #41 »»   Ответить


??????????
Согласен с eruditorom-что значит действовать?
Могут ли они слышать ответы других узников?Если да, то назови одно из чисел которое ты видишь и пусть его кто нибудь повторит(и не надо никаких mod от sum и т.п.-это не задача!).
Если же после того,как им развяжут глаза обмен информацией между любыми двумя узниками невозможен, то и гарантировать угадывание числа хотя бы одним узником невозможно.Можно лишь говорить о вероятности остаться всем живыми.
↓↓ 0 ↑↑   total (-4 / 9)   2009-02-17 19:48   «« #42 »»   Ответить


Узники по очереди говорят числа (первый говорит 1, второй 2 и тд.) по любому кто-то угадает своё число.
↓↓ 0 ↑↑   Rus_17-91 (0 / 12)   2009-05-03 22:23   «« #43 »»   Ответить


Интересная задача?!
Она была бы интересной если бы существовало конкретное красивое логическое решение. А так: номер на колпаке абсолютно не зависит от остальных номеров. Следовательно самостоятельно тут сразу ничего не скажешь( а требуют именно сразу, нету динамики какой-то как например в задаче про черные и белые колпаки). Поэтому единственный вариант - придумывать какие-то обманы и т. д.. А это уже не красивое решение...
↓↓ 0 ↑↑   Einstein (0 / 4)   2009-11-16 15:43   «« #44 »»   Ответить


проверка
Если узники _никак_ не обмениваются инфой и речь идет о _100%_ достоверности хотя бы одного правильно ответившего узника, то _все_вышеописанные_ алгоритмы не верны. Проверил полным перебором для N=5 узников (3125 вариантов). Дайте URL'ок, где обсуждается именно этот вариант задачи (с английским дружу;)

PS: а с этими условиями и без недоговорок задача не имеет решения, так как номер на колпаке каждого узника _никак_ не связан ни с одним из остальных (может быть абсолютно любой из 1..100 (или 0..99))! Или тогда какое-либо уточнение - и это будет уже совсем другая задача!
↓↓ 0 ↑↑   DRomanov (0 / 4)   2010-03-05 10:47   «« #45 »»   Ответить


Решение
Выбираеться узник который будет угадывать. Двое стоящие напротив него в кругу(видят его число) Первый говорит разряд едениц его числа, второй говорит разряд десяток его числа, да нужен 3ий вдруг у выбранного число 100. Потом он называет свое число. Вуаля все спасенны.
↓↓ 0 ↑↑   logotip-mix (0 / 1)   2010-06-03 15:48   «« #46 »»   Ответить


если хоть один не угадает - всех казнят! пока те будут говорить его десятки всех уже прибьют) если конечно по чистой случайности не угадют свои номера
↓↓ 0 ↑↑   lavsvip (-124 / 40)   2010-10-18 15:18   «« #47 »»   Ответить


Формулировка задачи невнятная.
1) Сколько попыток на угадывание каждому? Нигде не определено.
2) Что значит "сможет сказать"? Он должен быть уверен на 100% заранее, иначе должен молчать? Впечатление именно такое...
3) Зачем эта дописка "Если нет - всех казнят", когда раньше сказано "если _хоть один_ угадает"?? В купе с (2), создаётся впечатление, что иначе (за один неверный ответ) всех казнят. Тогда уж пишите чётче "а если ни один не угадает..."

Не удивительно, что кто-то путается пока не прочитает обсуждение. Но он и не должен его читать, если хочет ответить самостоятельно!

В нормально виде, это надо как-то так:
"Каждому из сотни узников, присвоят совершенно случайное целое число от 1 до 100. Это не номер - число может повторятся, вплоть до того, что у всех узников может выпасть одно и тоже число.
Потом, каждому узнику сообщат числа всех остальных узников, но не его собственное и дадут одну попытку угадать своё число.
Если хоть один из них угадает - всех отпустят. Если все не угадают - всех казнят.

Узники прознали об этом заранее. И когда их разведут по камерам и всё начнётся, никто не сможет общаться ни коим образом до самого конца дела, пока не объявят общий результат (угадал хоть кто-то или нет).
Но пока, у них есть возможность договориться. Как им надо договориться, что бы хоть один них точно угадал бы своё число?

(Задача имеет решение, гарантирующее узникам успех во всех случаях)"
↓↓ 0 ↑↑   SergeyASh (4 / 36)   2010-12-09 22:39   «« #48 »»   Ответить


может так?
они договариваются кто будет "началом отсчета". этот узник поворачивается к соседнему и если видит "0" то остается а сосед говорит что на нем цифра "0". если нет то первый отворачивается а эстафету принимает следующий. и так до конца круга пока не найдут "0". если не найдут то ищут "1" и т.д.
↓↓ 0 ↑↑   vikiller (0 / 1)   2010-12-15 20:07   «« #49 »»   Ответить


=======
Решение уже есть, могу написать док-ва что найдется одно и только одно решение при заданном правиле перебора... бессоная ночка оказалась продуктивной) На самом деле писал писал суда докозательство, перезагружал браузер и сессия не восстановилась ))) поэтому проще я свотаю и вышлю кому надо) http://vkontakte.ru/igor_temerov пишите суда. Здесть смотреть не буду
↓↓ 0 ↑↑   Blabber (0 / 14)   2011-02-01 01:05   «« #50 »»   Ответить


ыыыы
Выбирается ведущий. Он вытягивает 2 узников с одинаковыми номерами, и ставит их друг перед другом. Думаю дальше все понятно :)
↓↓ 0 ↑↑   Dimqe (0 / 19)   2011-05-15 13:03   «« #51 »»   Ответить


вот точно правильное, причем наиболее простое решение
если брать тот вариант задачи где они стоят по кругу, то решение такое: если человек не знает свой номер он говорит номер написанный на колпаке человека стоящего справа от него. даже если их будут спрашивать по-кругу с права на лево не пропуская никого, то хотябы один человек скажет свой номер правильно.
↓↓ 0 ↑↑   suslik (0 / 1)   2011-10-09 12:21   «« #52 »»   Ответить


Пусть говорящий первым называет любой номер, который видит, а остальные все его повторяют...
↓↓ 0 ↑↑   VanDull (4 / 3)   2012-03-24 00:10   «« #53 »»   Ответить


Если каждый имеет список всех номеров, кроме своего, нужно чтобы каждый назвал любой известный ему номер, а все остальные вычеркнули этот номер из своего списка. Тогда предпоследний точно назовет номер последнего.
↓↓ −5 ↑↑   Hag (-5 / 1)   2013-05-06 15:26   «« #54 »»   Ответить


формулировка корявая, первый называет существующее число и все его повторяют
↓↓ 0 ↑↑   Климов (-18 / 16)   2013-08-29 10:37   «« #55 »»   Ответить


Что оказалось непонятным в формулировке
"Никакого обмена информацией после написания чисел на колпаках нет."
?


Да блин тут же все просто
Узники напишут все числа с 1 до 100. Их 100 и чисел 100. Один да угадает.
↓↓ −5 ↑↑   Narek (-5 / 2)   2015-03-20 10:44   «« #57 »»   Ответить


Узники хором произносят одно и то же число из чисел,от 1 до 100. Один угадает точно.
↓↓ −5 ↑↑   Станислав (-10 / 2)   2016-12-31 11:57   «« #58 »»   Ответить


Задача и вправду интересная. Только надо в условиях уточнить, что узники смотрят друг на друга например час, потом колпаки снимают и их разводят по камерам. После этого инивидуально каждого спрашивают.
Иначе если спрашивают по порядку, то можно за себя просто сказать номер следующего и всё. Тогда половина ответит правильно (нечётный говорит число следующего чётного, чётный своё).
Или вне зависимости от порядка тот, кого спрашивают первым говорит модуло 100 от суммы чисел на 99 колпаках, что он видит. Исходя из этого каждый оставшийся может подсчитать, какое число у него самого. Т.е будет 99, а если первый случайно попал, то и все 100 правильных ответов.
Разгадка же в том случае, как я описал выше (и как это без сомнения задумано автором) лежит немного в иной плоскости.
↓↓ 0 ↑↑   Dima (5 / 3)   2017-08-14 18:32   «« #61 »»   Ответить


Общее красивое и логическое решение выглядит таким образом:
Сумма всех чисел на всех колпаках является вполне конкретным числом. Взятие этого числа по модулю 100 даёт результат от 0 до 99.
Каждый узник может подсчитать сумму 99 чисел, которые он видит. Пронумеруем узников от 1 до 100. Теперь каждый узник должен сказать такое число, чтобы в сумме с остальными 99 числами, которые он видит, получилось число с его порядковым номером по модулю. У узника с номером 100 должен получиться 0.
Таким образом мы проверим общую сумму на все возможные значения по модулю 100 и один (и только один) вариант будет правильным.
↓↓ +5 ↑↑   Dima (5 / 3)   2017-08-14 18:47   «« #62 »»   Ответить


Приведу пример:
Узник с порядковым номером 5 видит сумму 5192. Тогда он говорит 13, потому что 5192+13=5205 и 5205%100=5, т.е. его порядковому номеру.
Или узник с номером 37 видит сумму 4914. Тогда он говорит 23, потому что 4914+23=4937%100=37.
Я надеюсь обьяснение понятно.
↓↓ 0 ↑↑   Dima (5 / 3)   2017-08-14 18:52   «« #63 »»   Ответить


Без мат-ки. Решение проблемы в одинаковых числах. Те узники, кот. стоят справа от одного из пары узников с одинаковыми числами, причем самыми меньшими из остальных пар, делают одно из не запрещенных действий, например, закрывают один глаз. Можно? Те, кто стоят слева от них, видят друг друга и свой номер. Может оказаться, что один из них как раз и будет составлять одного из пары узников с еще меньшим числом. В таком случае он, во первых, не увидит (один глаз все же открыт) ожидаемого отклика своего визави, во вторых, он обнаружит справа от себя узника с закрытым глазом, и еще одного такого же. Тогда ему останется открыть свой глаз и назвать свой номер, кот. он увидит на голове узника, стоящего слева от второго прикрывшего глаз. Эти действия оговорены заранее.
↓↓ 0 ↑↑   Олег (0 / 85)   2018-10-12 14:29   «« #64 »»   Ответить


Мне кажется, что под фразой "никакого обмена информацией" подразумевается, что они должны пытаться логически угадать свой номер, а не пытаться назвать номер своего соседа и ждать когда он его повторит. А то, что достаточно одного правильного ответа даёт нам возможность составить логическую цепочку, в которой последний (при худшем раскладе) будет знать свой номер наверняка. То что попыток у каждого одна и так ясно. Предлагаю свой вариант решения для 3 узников (для 100 он тоже сработает, но рассуждать долго). Итак 3 узника и 3 колпака от 1 до 3. Если на всех разные колпаки, к примеру 1, 2 и 3 соответственно, то любой узник (но для конкретики пусть будет 1ый) пытается угадать свой колпак, называя номер, которого не видит. Первый же ответ будет правильными. Если же не все было так просто, то есть у нас есть два одинаковых колпака, например 1, 1 и 2 соответственно. Тогда первый узник, действуя по тому же принципу, видя 1 и 2, скажет что у него 3 номер и ошибётся. Но 2 и 3 узники поймут, что колпака с номером 3 у них нет. Тогда третий узник, видя колпаки под номерами 1 и зная, что колпака под номером 3 у него нет, назовет свой номер колпака 2. И последний, самый неблагоприятный вариант, у всех трёх колпак под номером 1. Тогда первый и второй узники пытаются угадать свои колпаки, по той же тактике, называют цифры 2 и 3 соответственно. Не угадывают, но третьему зато известен свой номер. Пробовал для 10 узников, тоже работает, так что и для любого количества узников сработает. Скажете, что они называя номера, которые не видят, давали инфу остальным. Впринципе давали. Но в моем решение у них все таки была стратегия, в которой они старались прежде всего угадать свои номера, а не своим соседям подсказывали.
↓↓ 0 ↑↑   Ал (0 / 1)   2021-03-29 17:18   «« #66   Ответить



© 2006-2024   Авторы