задачка

[avva]

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

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

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

Comments

[plakhov.livejournal.com]

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

[toyvo.livejournal.com]

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

[french-man.livejournal.com]

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

[faceted-jacinth.livejournal.com]

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

[plakhov.livejournal.com]

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

[french-man.livejournal.com]

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

[toyvo.livejournal.com]

да, да, уже врубился, плохо быть тупицей:)

[faceted-jacinth.livejournal.com]

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

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

[plakhov.livejournal.com]

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

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

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

[toyvo.livejournal.com]

Ага, понял, красиво, спасибо! Я чего-то сразу решил что решение вероятностное и протупил.

[abvgd.livejournal.com]

если у всех написано 1, то по вашей методике каждый называет 2

[faceted-jacinth.livejournal.com]

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

[plakhov.livejournal.com]

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

[french-man.livejournal.com]

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

[abvgd.livejournal.com]

и откуда же следует, что хотя бы у кого-то число совпадет?
если нетрудно, проведите рассуждение для N=4

[toyvo.livejournal.com]

Плахов умный, слушайте Плахова:
http://avva.livejournal.com/1743110.html?replyto=41173510

Сумма любых четырех чисел по модулю 4, это 0 или 1 или 2 или 3.
Раздадим эти 4 числа 4-ем людям. Ясно, что номер на шляпе человека, это сумма всех номеров - сумма всех номеров кроме его номера.
Также ясно, что если мы возьмем по модулю четыре, это правило продолжит работать.
Т.е. если ТОЧНО знать сумму всех чисел (по модулю четыре) и все остальные числа, можно однозначно верно указать своё число. ОК?
Ну, а теперь вспоминаем, что мы раздали все номера от 0 до 3 - т.е. ОДИН человек "знает" правильную сумму - он и угадает число на своей шляпе.

Очень, очень красиво. И совсем нетривиально, ИМХО.

В любом случае, ОДИН из них будет прав (т.е. его сумма окажется верной). ОК?

[109.livejournal.com]

суперское объяснение. плахова прочитал - ничего не понял. тут прочитал - всё понял :)

[dimrub.livejournal.com]

Угу. Я для двух сообразил, а на обобщить уже мозги не хватило.

[french-man.livejournal.com]

Я и для двух не успел сообразить. Так что ты меня умнее!

[dimrub.livejournal.com]

Разве что чуть терпеливее :)

[avva.livejournal.com]

Правильно. Только, кажется, недостаточно ясно объяснено для многих :)

Вот более элементарное объяснение:

Они изначально назначают себе номера, от 1 до 100, когда договариваются. А когда видят шляпы, то каждый называет такое число, чтобы в сумме вместе со всеми остальными числами, которые он видит, последние две цифры совпадали с его "порядковым номером".

Например, у кого-то порядковый номер 34. Он видит, что сумма всех 99 чисел, что он видит у других, равна 4387, например. Сколько нужно еще добавить к этому числу, чтобы получилось что-то, что заканчивается на 34? Нужно добавить 47: 4387+47 = 4434. Поэтому он пишет "47".

Т.к. сумма всех 100 чисел в своих последних двух цифрах обязательно совпадет с одним из "порядковых номеров" (если считать 100 за 00), то именно тот человек, с которым она совпадет, отгадает правильно.

[beth4ever.livejournal.com]

Поверю на слово, что это работает.

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

[burivykh.livejournal.com]

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

[syarzhuk.livejournal.com]

То среднее, а тут гарантированно один угадает

[lavinya.livejournal.com]

Ну и ну. Никогда бы не додумалась. Послала решение маме - мы это вчера обсуждали.