Дикари поймали сто мудрецов. Им всем на головы надели шапки с числами из диапазона 1..100, причем не обязательно, что на всех разные. К примеру, всем могли надеть колпак с числом 25 или половине — колпак с числом 30, а второй половине — с числом 1. Главное, что не меньше 1 и не больше 100. После этого всех их поставили по кругу. Каждый ммудрец видит 99 чисел на шапках других мудрецов, но не видит что написано на его шапке. После этого каждый пишет на листке бумаги число от 1 до 100 — предполагаемое число на своей шапке. Общаться они не могут. Дикари всех отпустят, если хотя бы один угадает свое число. Какой стратегии они должны придерживаться, чтобы их гарантированно отпустили? (Мудрецы могли заранее договориться об общей стратегии. Мудрецы очень умные.)


+ -

решение

Ваши ответы на задачу

ответов: 17

ИРА 2018-11-09 23:07:59 пишет:

[скрыто]

ИРА 2018-11-09 23:04:00 пишет:

[скрыто]

Алексей Безымённый 2013-01-10 19:26:11 пишет:

[скрыто]

Админ: ставки слишком высоки. Нужен именно 100% результат.

Ptolmees 2013-01-10 12:14:08 пишет:

[скрыто]

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

нет 2012-02-06 15:10:12 пишет:

сложно

Вася Пупкин 2011-12-04 03:42:28 пишет:

[скрыто]

Админ: да-да-да

igv105 2011-12-03 15:45:03 пишет:

Каждому варианту надевания колпаков будет соответствовать упорядоченный набор из 100 чисел от 1 до 100. Чтобы он был упорядоченным необходимо чтобы мудрецы заранее договорились и пронумеровали друг друга от 1 до 100(в моем решении предполагается все видят лица друг друга, хотя для трех мудрецов это не нужно). Необходимо разбить эти наборы на 100 групп и за каждую будет отвечать один мудрец. Мудрец не видит одной позиции в наборе, поэтому не сможет отличить, например набор в котором одна двойка, а остальные единицы от набора в котором одни единицы ( если двойка именно у него на колпаке) такие наборы должны достаться двум разным мудрецам. Всего таких различенных наборов 100 в степени 100. Можно доказать по индукции что возможно разбиение при котором в каждой группе наборы отличаются не менее чем в двух разрядах. При таком разбиении каждый мудрец всегда сможет отличить два различных набора из своей группы друг от друга. Удовлетворяющие группы наборов из двух чисел будут такие ( (1,1) (2,2) ….(100,100)); ((2,3), (3,4),.. (98,99), (100,1)); ….((1,100),(2,1),(3,2), (100,99)) . Теперь если добавить третьим числом 1 ко всем наборам первой группы, 2 ко всем наборам второй группы и тд а потом все получившиеся наборы из трех чисел объединить получится первая группа наборов из трех чисел. Аналогично получается вторая группа. Подробное доказательство слишком большое поэтому пропускаю. В результате все наборы поделятся на сто групп удовлетворяющих условию. Для трех мудрецов получаются следующие три группы (111,122,133,212,223,231,313,321,332) (112,123,131,213,221,232,311,322,333) (113,121,132,211,222,233,312,323,313) Однако практически воспользоваться этим алгоритмом для 100 мудрецов нельзя – никакой мудрец не способен держать в голове такое количество вариантов, интересно найти более простой алгоритм.

344 2011-08-14 04:15:05 пишет:

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

Админ: главные тут - дикари, они не дают проявлять инициативу

Рам 2011-08-13 01:01:38 пишет:

Они просто зарание договарились кто под каким номером ведь они мудрецы

Админ: они не могут знать заранее, какие цифры будут у них на колпаках.

Арс 2011-08-12 19:15:35 пишет:

Каждый напишит разный номер от 1 до 100, о том кто какой номер пишит, обговорят вначале. И тогда хотя бы один из них угадает свой номер.

Админ: ненадежно

Ubori 2011-02-22 19:04:51 пишет:

Естественно в моем ответе имеется ввиду что они пишут одновременно и не видят что пишут другие, разве я где-то написал обратное?

^^ 2011-02-22 14:53:44 пишет:

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

Админ: спасибо за поправку

Ubori 2011-02-21 22:52:48 пишет:

[скрыто]

Админ: близко, но они не видят то, что пишут остальные

Вася 2011-02-20 21:39:13 пишет:

Каждый мудрец пишет число соседа слева (или справа) и передает ему бумажку, и так каждый мудрец по кругу по часовой стрелке (или против). Тогда у все "угдают" свои числа.

Очевидность 2011-02-20 19:55:33 пишет:

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

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

Ubori 2011-02-19 13:26:01 пишет:

Беру свои слова назад. Классная задача!

Админ: так решайте :)

Ubori 2011-02-19 10:53:09 пишет:

Задача не корректна.
Если они НИКАК общаться не могут, и пишут все одновременно, то задача равносильна той, где один мудрец должен угадать число от 1 до 100.

Добавьте комментарий:

© 2009-201x Логические задачи