?

Log in

задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [мар. 18, 2007|08:58 pm]
Anatoly Vorobey
Красивая задачка, не очень сложная. Я в отеле в Цюрихе, и комменты с правильными ответами скрывать не буду, так что не заглядывайте, если хотите сами решить.

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: kaktussin
2007-03-18 08:11 pm
всать попорядку. тогда человек увидет какие крайние от него числа и узнает свое.

в правильности сомневаюсь и жду правильный ответ
(Ответить) (Thread)
[User Picture]From: french_man
2007-03-18 08:21 pm
А как встать попурядку, не видя свою попу шляпу?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: plakhov
2007-03-18 08:12 pm
Сумма всех чисел по модулю 100 может иметь 100 различных значений. Поэтому достаточно распределить эти значения по людям (как раз на всех хватит), и пусть дают ответы исходя из значения каждый.
(Ответить) (Thread)
[User Picture]From: toyvo
2007-03-18 08:21 pm
Не совсем догоняю, не могли бы вы подробней?
Сорри, тупля я к ночи, а интересно понять:).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: toyvo
2007-03-18 08:12 pm
(0.99)^100, это примерно 0.36, вероятность что никто не угадает если они будут выбирать случайным образом. Т.е. их шансы выжить и так достаточно высоки.
Теперь можно попробовать следующую стратегию - каждый из них оглядывает всех соседей и выбирает число которого НЕТ на шляпах соседей, таким образом мы получаем вероятность что никто не угадает равной тому, что некое число ни разу не выпало(0.99^100~0.36) в сотой степени ~ 2.2 *10^-44. В такую вероятность я играю:)
Надеюсь что я не напутал и они дейтсвительно не связаны, как на первый взгляд кажется.
(Ответить) (Thread)
[User Picture]From: plakhov
2007-03-18 08:16 pm
пусть злодей раздал всем по шляпе с единицей.
2.2 *10^-44, говорите? ;)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: french_man
2007-03-18 08:15 pm
Имеется в виду дефинитивно избежать или с большой вероятностью?
(Ответить) (Thread)
[User Picture]From: plakhov
2007-03-18 08:17 pm
Можно избежать и заведомо.
(Ответить) (Parent) (Thread)
[User Picture]From: kattrend
2007-03-18 08:23 pm

;)

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

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

(Ответить) (Thread)
[User Picture]From: mama_ari
2007-03-18 08:31 pm

Re: ;)

полчаса - ДО того, как им наденут шляпы.
(Ответить) (Parent) (Thread)
[User Picture]From: beth4ever
2007-03-18 08:23 pm
Ну, можно договориться так, что если ты открываешь глаза и видишь, что разных цифр больше 50, а повторы редки, то пишешь ту цифру, которая реже встречается.
А если наоборот, много повторов, то ту, которая встречается чаще.
(Ответить) (Thread)
[User Picture]From: nechaman
2007-03-18 08:28 pm
Наверняка избежать?
Прямо даже не знаю для двоих :((
(Ответить) (Thread)
[User Picture]From: azzo27
2007-03-18 08:37 pm
Если видишь закономерность(все числа разные или только четные по 2 раза...) - исходи из нее;
иначе пиши наиболее часто повторяющееся (максимизируя байезианскую вероятность).
(Ответить) (Thread)
[User Picture]From: vorobiev
2007-03-18 08:38 pm

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

Передать информацию таки надо, но чтобы злодей не заметил.
Я бы организовал это так: скажем ктото в круге будет символизировать его начало. Дальше каждый будет иметь номер от 1 до 100. Если человек оглядел всех и увидел у кого либо свой номер, то он закрывает глаза и ждёт когда надо будет писать номера. Как только кто-либо это сделал, то все остальные пишут этот номер. Как то так... возможно стоит подшлифовать, но идея думаю ясна.
(Ответить) (Thread)
[User Picture]From: a_belov
2007-03-18 08:40 pm
Если какое-то число встречается на две шляпы больше, чем остальные, то можно договориться всем писать это число.
(Ответить) (Thread)
[User Picture]From: tienare
2007-03-18 08:50 pm
заранее распределить всем участникам числа от 1 до 100 по порядку и договориться, чтобы каждый подошел к тому, на ком увидит свое число. Хотя бы один точно увидит. Тот, к кому подойдут, пишет то число, которое было распределено тому, кто подошел. Единственная сложность - запомнить, кому какое число было дано, надо это зафиксировать как-то.
(Ответить) (Thread)
[User Picture]From: avva
2007-03-18 10:50 pm
Не, "подходить" это из той же области, что переговариваться. Нет никакой передачи информации после того, как раздали шляпы.
(Ответить) (Parent) (Thread)
From: justsoul
2007-03-18 08:53 pm

Мой вариант

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

Соотв. выбирается двое главных В. и П. . Если В. видит 2 одинаковых номера, то он подходит сперва к 1му, потом ко 2му. Если В. видит все разные, то П. повторяет процедуру. Если одинаковых номеров нет, то все пишут тот, который они не видят.
(Ответить) (Thread)
[User Picture]From: french_man
2007-03-18 09:11 pm

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

Общаться с надетыми шляпами низя. Даже методом подхода. Можно только разглядывать чужие шляпы.
(Ответить) (Parent) (Thread)
[User Picture]From: iratus
2007-03-18 09:15 pm
стратегия элементарная.
Выбирается лидер-сортировщик
он берет людей за руку и строит в колонны, тех у кого одинаковые номера.
расстояние между колоннами меряется шагами( например расстояние между колонной 2 и 4 - будет два шага).
После того, как сортировщик сделает свое дело, кто нибудь берет его за руку и ставит в нужное место.

таким образом в конце все будут знать номера на своих шляпах
(Ответить) (Thread)
[User Picture]From: maccolit
2007-03-18 09:22 pm
я кажется решил
допустив только возможность перестроения в круге
но исключив полностью какие-то разговоры и обмен информацией

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

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

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

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

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

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

(Ответить) (Thread)
[User Picture]From: french_man
2007-03-18 09:29 pm
Скажу, что плохо. Ходить не велено.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vashik
2007-03-18 09:24 pm
Нужно предусмотреть всего 2 варианта: все числа разные или есть повторы. Видя 99 разных чисел - пиcать недостающее 100-е, видя повторы - писать случайно выбранное среди наблюдаемых. Ни один из вариантов не дает 100% спасения.
Странное условие, вы ничего не напутали?
(Ответить) (Thread)
From: vitus_vvagner
2007-03-18 09:32 pm
простенько слишком.
- На первый сотый расчитайсь
- Каждому писать свое число, смотрите не перепутайте.
- Чучмекам выдать бумажки с номерами написанными заранее.
- Рабиновичу дать по голове и сунуть бумажку в карман, а то он до утра будет спорить какой ему полагается номер.
- Орангутяну и Шимпадзе повторяю отдельно - бумажки у соседей из карманов не вытаскивать, это не лоторея, Пи...дец будет всем, и дядя Жора не поможет.
- Госпожа Вайкуле, вы уверены что успеете написать цифру сто?
- Нет, цифры 7 и 77 я раздам сам. И 21 тоже.
- Почему я? Потому что моя фамилия Дирихле, идиот!!!
(Ответить) (Thread)
From: ex_reflexio471
2007-03-18 09:52 pm
Правильно. У меня заняло около минуты додуматься до этого. А всем вышестоящим товарищам не повезло, они уже мертвы ((
(Ответить) (Parent) (Thread)
From: ganim3d
2007-03-18 09:51 pm
Если заточенные слышат ответы друг друга, то тогда так: Они договорятся, мол первый, кто будет произносить свой номер, будет произносить чужой номер, который он увидел у своего собрата, заточенные услышат и все повторят тот или инной номер, следовательно тот, у кого будет номер, который произнесли первым, он тоже повторит и все)
(Ответить) (Thread)
[User Picture]From: larisaka
2007-03-18 10:36 pm
После этого каждый из вас _напишет_ на листке бумаги число.....
(Ответить) (Parent) (Thread)
[User Picture]From: viesel
2007-03-18 10:04 pm
Вот нематематическое решение этой задачи. Сто человек выбирают промеж себя двух самых глазастых. Один зыркает на шляпу второго и размашисто пишет на бумажке ЕГО номер. Другой в это время смотрит на его бумажку и пишет после этого на своей СВОЙ номер. Остальные 98 человек в это время совершают отвлекающие маневры. Для верности можно выбрать не одну пару, а три - народу хвыатает.
Где здесь нарушаются заданные ограничения?
(Ответить) (Thread)
[User Picture]From: muchacho
2007-03-18 10:05 pm
Например, 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
(Ответить) (Thread)
[User Picture]From: tuganbaev
2007-03-18 11:18 pm
+1
(Ответить) (Parent) (Thread)
From: ex_reflexio471
2007-03-18 10:14 pm
Единственное, о чем люди могут договориться, это или распределить числа между собой (от 1 до 100), либо выбрать одно число и всем написать его. Второй вариант мне кажется более статистически оправданным. 100% результативного решения при данных условиях быть не может.
(Ответить) (Thread)
[User Picture]From: french_man
2007-03-18 10:36 pm
Забавно, что правильное решение давно написано, а народ пролжает нести пургу.
(Ответить) (Thread)
[User Picture]From: ipain
2007-03-18 10:49 pm
а есть решение у такой же задачи с цветами вместо цифр?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: felisca
2007-03-18 11:04 pm
если выбрав одного "спасителя",остальные 99 будут иметь номер от 1 до 99 и тот чей номер будет равен числу "спасителя",начнет писать первый (например), будет ли это считаться передачей информации?
(Ответить) (Thread)
[User Picture]From: reut
2007-03-19 12:18 am
похожая задачка есть с мудрецами и разноцветными шляпами. только мне ее гуманно сначала задали для черных и белых. ;)
(Ответить) (Thread)
[User Picture]From: klondayk
2007-03-19 04:41 am
Старая шняга, в "Компьютерре" лет 10 назад была...
По схожему алгоритму действует механизм архивации данных.
(Ответить) (Thread)
[User Picture]From: migmit
2007-03-19 08:29 am
Я не помню, где видел эту задачу, если здесь - звиняйте.
В тюрьме содержатся 100 узников. Однажды их собирают во дворе и объявляют, что проведут с ними испытание. Состоит оно в следующем. В одной из камер расставлены (можно считать, что в ряд) 100 ящиков. В каждый из них положена бумажка с именем одного из узников, причём в разные ящики - разные имена. Узников по одному будут заводить в эту камеру. В камере узник может открыть любые - какие захочет - 50 ящиков из 100. После этого его уведут и сразу отправят в его камеру, так что никакого обмена информацией со следующими не будет. Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл - в частности, запрещено перекладывать бумажки, оставлять ящики открытыми и т.п. Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят. У них есть полчаса перед началом испытания, чтобы договориться. Как им следует действовать, чтобы вероятность выжить составила хотя бы 30%?
(Ответить) (Thread)
Страница 1 из 2
<<[1] [2] >>