задачка

[avva]

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

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

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

Comments

[kaktussin.livejournal.com]

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

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

[plakhov.livejournal.com]

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

[toyvo.livejournal.com]

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

[french-man.livejournal.com]

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

[plakhov.livejournal.com]

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

[toyvo.livejournal.com]

короче, это получается похоже на "парадокс дней рождения", только наоборот:) Как-то так:)

[plakhov.livejournal.com]

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

[toyvo.livejournal.com]

Ну так предположение было, что раздают случайным образом.

[french-man.livejournal.com]

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

[toyvo.livejournal.com]

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

[faceted-jacinth.livejournal.com]

+1
То ли с формулировкой что-то не то, то ли красивость задачки проявляется в том, что люди пытаются заюзать лишние данные и несут флеймопотенциальный бред.

[french-man.livejournal.com]

Да, похоже на то.

;)

[kattrend.livejournal.com]

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

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

[beth4ever.livejournal.com]

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

[french-man.livejournal.com]

Сделайте то же для двух человек (и чисел 1,2). Станет понятней.

[faceted-jacinth.livejournal.com]

Ойой! Мы ошиблись! Будем думать дальше.

2plakhov: угадать нужно именно своё число, а не число кого-нибудь другого.

[plakhov.livejournal.com]

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

[nechaman]

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

[faceted-jacinth.livejournal.com]

Человек А называет число 1, человек Б - 2. А на шляпах у них наоборот написано. Оппаньки!

[plakhov.livejournal.com]

Так свое же угадает, свое!

Еще раз. За полчаса каждому раздаем по числу от 0 до 99. Открыв глаза, каждый действует так. Пусть ему при раздаче досталось число N. Он суммирует 99 чисел, которые видит, получает число S, и называет ((N - S) mod 100) + 1.

Поскольку сумма всех ста чисел для кого-то из них окажется равна N по модулю 100, он назовет свое число.

Re: ;)

[mama-ari.livejournal.com]

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

[plakhov.livejournal.com]

я не это имел в виду, см. ниже полное решение

[toyvo.livejournal.com]

Я предположил что злодей - "природа", но это достаточно слабое предположение, согласен:(
Участники выбирают число ни разу не выпавшее на шляпах, их не больше нескольких штук (ну, с реальной вероятностью) на сотню случайных чисел, то что "случайный" выбор из нескольких чисел каждым человеком псевдослучаен, ясно, но приближение неплохое.

[french-man.livejournal.com]

А называет то же число, что написано у Б, а Б называет другое. Один из двух обязательно попадет.

[plakhov.livejournal.com]

плохо сформулировал, каюсь