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

Непонятно
Что кроется под словом "действовать"?
Они могут меняться местами? Или делать какие-то ещё действия? Откуда поток информации?

Один из узников будет условно считаться "первым" - по договоренности. После того, как узников расставят, следующий после него (по часовой стрелке, к примеру), будет условно считаться вторым и т.д. Если первый узник видит число 1, он подает знак, например, сжимает в кулак правую руку. Второй - если видит число 2... 100-ый - если 100. Если хоть одно чилсо встречается в единственном варианте, то тот из узников, который не видит его, но видит сжатый кулак, назовет свой номер. Если через некоторое время этого не происходит, то все разжимают кулаки и первый сжимает его снова, если число 1 он видит более, чем на одном колпаке... остальные делают то же самое. Если и этот вариант - "мимо", то "видит более, чем на двух колпаках" - и т.д, пока кто-то не сможет назвать свой номер. Запутаться легко, правда, учитывая, что узники все же люди, а не автоматы, но с чисто математической точки зрения вроде правильно. Правда, остается вопрос о допустимых действиях узников.

Вобщем, задачка недоделанная. В текущей формулировке есть решение ещё проще - один узник говорит другому число, которое у того на колпаке написано :)

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

Никаких знаков подавать нельзя.
Переговариваться во время испытания тоже.
Короче говоря, можно только смотреть.

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

Не знаю...
Формулировка встретилась именно такая.
Уточню...

Такой вариант еще есть...
100 узникам на головы надели колпаки с числами из диапазона 1..100. Причем не обязательно, что на всех разные. К примеру, всем могли одеть колпак с числом 7, или половине колпак с числом 20, а второй половине с числом 10. Главное, что не меньше 1 и не больше 100. После этого всех их поставили по кругу. Каждый видит 99 чисел на головах других, но не своё. После этого, каждый пишет на листке бумаги число от 1 до 100 - предпологаемое число на своём колпаке. Общаться и подглядывать нельзя. Их всех отпустят, если хотя бы один угадает своё число.
Какой стратегии они должны придерживаться, если хотят, чтобы их гарантированно отпустили?

Глупое решение...
Например, выбрать 1 узника, который будет в конце концов тем, кто угадает. Когда надевают колпаки - все видят, какой у него номер. Например - 50. Тогда начиная от 1 узника 50 чел. по часовой стрелке сразу пишут ответ (любой). 51-ый не пишет - типа "думает". По этой паузе, у 1 узника есть возможность посчитать сколько людей пишут, а сколько "думают". Потом остальные 49 дописывают любые ответы, а выбранный узник пишет точный номер.

Нормальное решение
Но что если их заставят написать свои числа строго одновременно?

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

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

Дополнение
тогда например, чтоб часть писали левой рукой, часть правой... Все равно 1 узник будет немного отставать...
Или дать всем ста узникам заранее номера по часовой стрелке и только тот, порядковый номер которого будет соответствовать номеру на колпаке 1 узника будет писать левой рукой, а все остальные правой...
У всех этих вариантов одна проблема - если номер 1 узника - 100. так как кроме него остаются только 99

Или
9 узников справа от 1 будут "изображать" десятки, 10 слева - единицы.
Тогда решена проблема с 100, так как дополнительный узник просто может "играть роль" сотни

Сорри :)
под "изображением" я имела ввиду писать левой рукой - то есть отличаться от остальных

eruditor
Почему нет?
Другое дело, что надо придумать какую-то хитрость, чтобы сообщить всем во время испытания, какое число писать...

Никакой информации

2 Zero
"придумать какую-то хитрость, чтобы сообщить " и есть суть задачи.

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

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

Осталось функцию сочинить :)

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

НЕ тот означает, что если видит "1" - пишет "2", видит "2" - пишет "1".
Осталось продолжить функцию на случай произвольного N.

"...понял, что решение реально существует" - уже хорошо! :)
На одном "буржуйском" форуме попалась подсказка - что-то относительно того, что можно каким-то образом использовать сумму всех видимых номеров.

Да, сумма - это правильно. Осталось чуть-чуть. Связать это с решением для N=2.
К сожалению, уезжаю в командировку, додумывать буду в дороге, без интернета.
Всем удачи :-)

Не знаю, как это можно привязать к сумме.... Там же ведь любое число может быть на колпаке. Ну, допусим, вижу я 99 колпаков, сумма чисел - 506. Что это мне дает??? На моем колпаке ведь все равно ЛЮБОЕ число от 1 до 100!!
про: если видит "1" - пишет "2", видит "2" - пишет "1"
ну и что, что видит 1, пишет 2, на колпаке-то может быть и 1 тоже (это если до n=2)

Все равно в любом случае кто-то из 2 угадает свое число. А бОльшего и не надо.

Почему?
Если у обоих написаны "1", то следуя логике eruditor (видит "1" - пишет "2"), оба напишут "2" и никто не угадает

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

"К1 пишет тот номер, который он видит на К2.
К2 пишет НЕ тот номер, который он видит на К1".

Согласен с eruditor
Нумеруем всех от 1 до k (общий случай, на каждом может быть число от 0 до k-1, суть та же). 1-й считает сумму всех чисел других колпаков и берёт остаток от деления на k. Затем от k отнимает полученное число и записывает. 2-й тоже считает сумму всех и добавляет к ней 1, берёт остаток от деления на k и отнимает от k полученое число. 3-й считает сумму всех и +2 и т.д... k-й считает сумму всех + (k-1)..
Проверял для k=3 и 4. Нужно доказать общее

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).

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

Ну, эт понятно :-)
Суть в том, что чисел везде 100 штук, а не 100 и 99.

Всех узников пронумеровать. Первый будет смотреть на того, на ком видит цифру 1. Второй - на того, на ком видит 2 и т.д. Если видит нескольких человек с одинаковыми числами на колпаке, то смотрит на любого, не отрываясь, долго. Не видит ни одного- опускает глаза в пол. Система не сработает лишь в том случае, если каждый получит "свой" номер.. Но тогда правильный вывод можно будет сделать после продолжительного молчания.

Всех узников пронумеровать. Первый будет смотреть на того, на ком видит цифру 1. Второй - на того, на ком видит 2 и т.д. Если видит нескольких человек с одинаковыми числами на колпаке, то смотрит на любого, не отрываясь, долго. Не видит ни одного- опускает глаза в пол. Система не сработает лишь в том случае, если каждый получит "свой" номер.. Но тогда правильный вывод можно будет сделать после продолжительного молчания.

Дополнение к последнему.
Нумерация может быть условной: первый номер присваивается конкретному человеку, второй - стоящему от него слева и т.д.

Fibonacci
Какая "передача информации"? Узники "просто смотрят".

alo чуток неправільно сказал
выберем главаря, пусть он будет 1.
ход рассужденія такой:(от лица главаря)
Узник который будет стоять возле меня( 1) будет первым, итак, если меня на колпаке 1 , то только он на меня смотрит, если 2 то узник, стоящий рядом с ним тоже на меня смотрит итак, сколько людей на меня смотрят( начало от узника , который стоит , допустим слева от главаря) то число у меня на колпаке ,)

Решение(извиняюсь что повторяюсь с эрудитор, оно такое же, но я его искал целый день, выкладываю свои мысли)
Возьмём сумму всех чисел за S, тогда (S mod 100) даёт в остатке K
Если узнику сказать число К, он без проблем узнает своё число, так как К=0,99 то всем узникам даём своё К (тоесть пусть каждый считает своё К)
Найдётся узник, для которого К совпадёт!

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

??????????
Согласен с eruditorom-что значит действовать?
Могут ли они слышать ответы других узников?Если да, то назови одно из чисел которое ты видишь и пусть его кто нибудь повторит(и не надо никаких mod от sum и т.п.-это не задача!).
Если же после того,как им развяжут глаза обмен информацией между любыми двумя узниками невозможен, то и гарантировать угадывание числа хотя бы одним узником невозможно.Можно лишь говорить о вероятности остаться всем живыми.

Интересная задача?!
Она была бы интересной если бы существовало конкретное красивое логическое решение. А так: номер на колпаке абсолютно не зависит от остальных номеров. Следовательно самостоятельно тут сразу ничего не скажешь( а требуют именно сразу, нету динамики какой-то как например в задаче про черные и белые колпаки). Поэтому единственный вариант - придумывать какие-то обманы и т. д.. А это уже не красивое решение...

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

PS: а с этими условиями и без недоговорок задача не имеет решения, так как номер на колпаке каждого узника _никак_ не связан ни с одним из остальных (может быть абсолютно любой из 1..100 (или 0..99))! Или тогда какое-либо уточнение - и это будет уже совсем другая задача!

Решение
Выбираеться узник который будет угадывать. Двое стоящие напротив него в кругу(видят его число) Первый говорит разряд едениц его числа, второй говорит разряд десяток его числа, да нужен 3ий вдруг у выбранного число 100. Потом он называет свое число. Вуаля все спасенны.

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

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

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

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

(Задача имеет решение, гарантирующее узникам успех во всех случаях)"

может так?
они договариваются кто будет "началом отсчета". этот узник поворачивается к соседнему и если видит "0" то остается а сосед говорит что на нем цифра "0". если нет то первый отворачивается а эстафету принимает следующий. и так до конца круга пока не найдут "0". если не найдут то ищут "1" и т.д.

=======
Решение уже есть, могу написать док-ва что найдется одно и только одно решение при заданном правиле перебора... бессоная ночка оказалась продуктивной) На самом деле писал писал суда докозательство, перезагружал браузер и сессия не восстановилась ))) поэтому проще я свотаю и вышлю кому надо) http://vkontakte.ru/igor_temerov пишите суда. Здесть смотреть не буду

ыыыы
Выбирается ведущий. Он вытягивает 2 узников с одинаковыми номерами, и ставит их друг перед другом. Думаю дальше все понятно :)

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

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

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

формулировка корявая, первый называет существующее число и все его повторяют

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

Да блин тут же все просто
Узники напишут все числа с 1 до 100. Их 100 и чисел 100. Один да угадает.

Узники хором произносят одно и то же число из чисел,от 1 до 100. Один угадает точно.

Задача и вправду интересная. Только надо в условиях уточнить, что узники смотрят друг на друга например час, потом колпаки снимают и их разводят по камерам. После этого инивидуально каждого спрашивают.
Иначе если спрашивают по порядку, то можно за себя просто сказать номер следующего и всё. Тогда половина ответит правильно (нечётный говорит число следующего чётного, чётный своё).
Или вне зависимости от порядка тот, кого спрашивают первым говорит модуло 100 от суммы чисел на 99 колпаках, что он видит. Исходя из этого каждый оставшийся может подсчитать, какое число у него самого. Т.е будет 99, а если первый случайно попал, то и все 100 правильных ответов.
Разгадка же в том случае, как я описал выше (и как это без сомнения задумано автором) лежит немного в иной плоскости.

Общее красивое и логическое решение выглядит таким образом:
Сумма всех чисел на всех колпаках является вполне конкретным числом. Взятие этого числа по модулю 100 даёт результат от 0 до 99.
Каждый узник может подсчитать сумму 99 чисел, которые он видит. Пронумеруем узников от 1 до 100. Теперь каждый узник должен сказать такое число, чтобы в сумме с остальными 99 числами, которые он видит, получилось число с его порядковым номером по модулю. У узника с номером 100 должен получиться 0.
Таким образом мы проверим общую сумму на все возможные значения по модулю 100 и один (и только один) вариант будет правильным.

Приведу пример:
Узник с порядковым номером 5 видит сумму 5192. Тогда он говорит 13, потому что 5192+13=5205 и 5205%100=5, т.е. его порядковому номеру.
Или узник с номером 37 видит сумму 4914. Тогда он говорит 23, потому что 4914+23=4937%100=37.
Я надеюсь обьяснение понятно.

Без мат-ки. Решение проблемы в одинаковых числах. Те узники, кот. стоят справа от одного из пары узников с одинаковыми числами, причем самыми меньшими из остальных пар, делают одно из не запрещенных действий, например, закрывают один глаз. Можно? Те, кто стоят слева от них, видят друг друга и свой номер. Может оказаться, что один из них как раз и будет составлять одного из пары узников с еще меньшим числом. В таком случае он, во первых, не увидит (один глаз все же открыт) ожидаемого отклика своего визави, во вторых, он обнаружит справа от себя узника с закрытым глазом, и еще одного такого же. Тогда ему останется открыть свой глаз и назвать свой номер, кот. он увидит на голове узника, стоящего слева от второго прикрывшего глаз. Эти действия оговорены заранее.

Мне кажется, что под фразой "никакого обмена информацией" подразумевается, что они должны пытаться логически угадать свой номер, а не пытаться назвать номер своего соседа и ждать когда он его повторит. А то, что достаточно одного правильного ответа даёт нам возможность составить логическую цепочку, в которой последний (при худшем раскладе) будет знать свой номер наверняка. То что попыток у каждого одна и так ясно. Предлагаю свой вариант решения для 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 узников, тоже работает, так что и для любого количества узников сработает. Скажете, что они называя номера, которые не видят, давали инфу остальным. Впринципе давали. Но в моем решение у них все таки была стратегия, в которой они старались прежде всего угадать свои номера, а не своим соседям подсказывали.