задачка

[avva]

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

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

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

Comments

[kaktussin.livejournal.com]

всать попорядку. тогда человек увидет какие крайние от него числа и узнает свое.

в правильности сомневаюсь и жду правильный ответ

[french-man.livejournal.com]

А как встать попурядку, не видя свою попу шляпу?

[plakhov.livejournal.com]

Сумма всех чисел по модулю 100 может иметь 100 различных значений. Поэтому достаточно распределить эти значения по людям (как раз на всех хватит), и пусть дают ответы исходя из значения каждый.

[toyvo.livejournal.com]

Не совсем догоняю, не могли бы вы подробней?
Сорри, тупля я к ночи, а интересно понять:).

[toyvo.livejournal.com]

(0.99)^100, это примерно 0.36, вероятность что никто не угадает если они будут выбирать случайным образом. Т.е. их шансы выжить и так достаточно высоки.
Теперь можно попробовать следующую стратегию - каждый из них оглядывает всех соседей и выбирает число которого НЕТ на шляпах соседей, таким образом мы получаем вероятность что никто не угадает равной тому, что некое число ни разу не выпало(0.99^100~0.36) в сотой степени ~ 2.2 *10^-44. В такую вероятность я играю:)
Надеюсь что я не напутал и они дейтсвительно не связаны, как на первый взгляд кажется.

[plakhov.livejournal.com]

пусть злодей раздал всем по шляпе с единицей.
2.2 *10^-44, говорите? ;)

[french-man.livejournal.com]

Имеется в виду дефинитивно избежать или с большой вероятностью?

[plakhov.livejournal.com]

Можно избежать и заведомо.

;)

[kattrend.livejournal.com]

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

Помнится, Гед долго стоял перед мастером Привратником, чтобы узнать его имя. И, в конце концов, додумавшись, что от логики и магии нет толку, просто попросил Привратника назвать свое имя. И Привратник его назвал.

Re: ;)

[mama-ari.livejournal.com]

полчаса - ДО того, как им наденут шляпы.

[beth4ever.livejournal.com]

Ну, можно договориться так, что если ты открываешь глаза и видишь, что разных цифр больше 50, а повторы редки, то пишешь ту цифру, которая реже встречается.
А если наоборот, много повторов, то ту, которая встречается чаще.

[nechaman]

Наверняка избежать?
Прямо даже не знаю для двоих :((

[french-man.livejournal.com]

Для двоих:

http://avva.livejournal.com/1743110.html?thread=41174534#t41174534

[azzo27.livejournal.com]

Если видишь закономерность(все числа разные или только четные по 2 раза...) - исходи из нее;
иначе пиши наиболее часто повторяющееся (максимизируя байезианскую вероятность).

Я бв предложил такой вариант...

[vorobiev.livejournal.com]

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

[a-belov.livejournal.com]

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

[tienare.livejournal.com]

заранее распределить всем участникам числа от 1 до 100 по порядку и договориться, чтобы каждый подошел к тому, на ком увидит свое число. Хотя бы один точно увидит. Тот, к кому подойдут, пишет то число, которое было распределено тому, кто подошел. Единственная сложность - запомнить, кому какое число было дано, надо это зафиксировать как-то.

[avva.livejournal.com]

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

Мой вариант

[justsoul.livejournal.com]

100 человек, значит либо у всех числа разные, либо есть 2 одинаковых.

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

Re: Мой вариант

[french-man.livejournal.com]

Общаться с надетыми шляпами низя. Даже методом подхода. Можно только разглядывать чужие шляпы.

[iratus.livejournal.com]

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

таким образом в конце все будут знать номера на своих шляпах

[maccolit.livejournal.com]

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

1. назначается заранее 1 участник. он и будет в конце знать свой номер

2. он выбирает из всех наименьший номер и пристраивается к нему справа

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

4. далее процедура повторяется, в результате чего промежуток между первым и вторым заполняется.
допустим назначенный имел номер 57, а его сосед слева после всех перестроений имеет номер 51, а следующий - 60. Значит, сам он может иметь номера из этого промежутка, включая концы отрезка.

5. после чего люди вне этого промежутка заполняют пустоту - слева становится 5 любых человек (51+5=56). Первый понимает, что он 57. Если слева не становитсяч никто, он понимает, что его номер совпадает с предыдущим.

юра, что скажешь на это?

[french-man.livejournal.com]

Скажу, что плохо. Ходить не велено.

[vashik.livejournal.com]

Нужно предусмотреть всего 2 варианта: все числа разные или есть повторы. Видя 99 разных чисел - пиcать недостающее 100-е, видя повторы - писать случайно выбранное среди наблюдаемых. Ни один из вариантов не дает 100% спасения.
Странное условие, вы ничего не напутали?

[vitus-vvagner.livejournal.com]

простенько слишком.
- На первый сотый расчитайсь
- Каждому писать свое число, смотрите не перепутайте.
- Чучмекам выдать бумажки с номерами написанными заранее.
- Рабиновичу дать по голове и сунуть бумажку в карман, а то он до утра будет спорить какой ему полагается номер.
- Орангутяну и Шимпадзе повторяю отдельно - бумажки у соседей из карманов не вытаскивать, это не лоторея, Пи...дец будет всем, и дядя Жора не поможет.
- Госпожа Вайкуле, вы уверены что успеете написать цифру сто?
- Нет, цифры 7 и 77 я раздам сам. И 21 тоже.
- Почему я? Потому что моя фамилия Дирихле, идиот!!!

[ex-reflexio471.livejournal.com]

Правильно. У меня заняло около минуты додуматься до этого. А всем вышестоящим товарищам не повезло, они уже мертвы ((

[ganim3d.livejournal.com]

Если заточенные слышат ответы друг друга, то тогда так: Они договорятся, мол первый, кто будет произносить свой номер, будет произносить чужой номер, который он увидел у своего собрата, заточенные услышат и все повторят тот или инной номер, следовательно тот, у кого будет номер, который произнесли первым, он тоже повторит и все)

[larisaka.livejournal.com]

После этого каждый из вас _напишет_ на листке бумаги число.....

[viesel.livejournal.com]

Вот нематематическое решение этой задачи. Сто человек выбирают промеж себя двух самых глазастых. Один зыркает на шляпу второго и размашисто пишет на бумажке ЕГО номер. Другой в это время смотрит на его бумажку и пишет после этого на своей СВОЙ номер. Остальные 98 человек в это время совершают отвлекающие маневры. Для верности можно выбрать не одну пару, а три - народу хвыатает.
Где здесь нарушаются заданные ограничения?

[muchacho.livejournal.com]

Например, Z1 = sum(Xi, i<>1) mod' N (mod, где 0 заменяется на N).
Остальные заполняют в предположении, что первый ошибся на 1, 2 и т.д. (Z1-X1 mod N = 1, 2...)
Zi = X1+(i-1)-sum(Xj, j>1 && j<>i) mod' N

[tuganbaev.livejournal.com]

+1

[ex-reflexio471.livejournal.com]

Единственное, о чем люди могут договориться, это или распределить числа между собой (от 1 до 100), либо выбрать одно число и всем написать его. Второй вариант мне кажется более статистически оправданным. 100% результативного решения при данных условиях быть не может.

[french-man.livejournal.com]

Забавно, что правильное решение давно написано, а народ пролжает нести пургу.

[ipain.livejournal.com]

а есть решение у такой же задачи с цветами вместо цифр?

[felisca.livejournal.com]

если выбрав одного "спасителя",остальные 99 будут иметь номер от 1 до 99 и тот чей номер будет равен числу "спасителя",начнет писать первый (например), будет ли это считаться передачей информации?

[reut.livejournal.com]

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

[klondayk.livejournal.com]

Старая шняга, в "Компьютерре" лет 10 назад была...
По схожему алгоритму действует механизм архивации данных.

[migmit.livejournal.com]

Я не помню, где видел эту задачу, если здесь - звиняйте.
В тюрьме содержатся 100 узников. Однажды их собирают во дворе и объявляют, что проведут с ними испытание. Состоит оно в следующем. В одной из камер расставлены (можно считать, что в ряд) 100 ящиков. В каждый из них положена бумажка с именем одного из узников, причём в разные ящики - разные имена. Узников по одному будут заводить в эту камеру. В камере узник может открыть любые - какие захочет - 50 ящиков из 100. После этого его уведут и сразу отправят в его камеру, так что никакого обмена информацией со следующими не будет. Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл - в частности, запрещено перекладывать бумажки, оставлять ящики открытыми и т.п. Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят. У них есть полчаса перед началом испытания, чтобы договориться. Как им следует действовать, чтобы вероятность выжить составила хотя бы 30%?