?

Log in

No account? Create an account
задачка (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

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

Links
[Links:| English-language weblog ]

задачка (математическое) [июл. 4, 2012|04:17 pm]
Anatoly Vorobey
Отличная задачка от knop'а (исходная ссылка). Очень понравилась.

"99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее - до надевания колпаков - выработать совместно используемую стратегию.)"

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

Дополнение:

1. Mежду мудрецами не может быть никакого общения после надевания колпаков - никаких подсказок, знаков, итд. Все догадки пишутся всеми мудрецами одновременно.

2. Несколько человек сообщили численный ответ, но не объяснили, каким образом мудрецы договариваются - это не решение. До правильного ответа можно додуматься с неработающей стратегией - со мной это вчера ночью случилось два или три раза, в итоге я лег спать в четыре утра :)

3. За прошедшие несколько часов появилось два правильных решения, их написали vlad_gor и dreamer_other. Кстати, решения у них немного разные, и есть еще как минимум одна совсем другая стратегия поведения, тоже оптимальная.

Дополнение 9 июля: открыл все комментарии. Спасибо всем решившим и пытавшимся!
СсылкаОтветить

Comments:
Страница 1 из 4
<<[1] [2] [3] [4] >>
[User Picture]From: aintlion
2012-07-04 01:35 pm
73
(Ответить) (Thread)
[User Picture]From: avva
2012-07-04 03:52 pm
Нет.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: lobastova
2012-07-04 01:42 pm
Садятся в круг. Каждый пишет на бумажке цвет колпака соседа справа. Потом сдвигают бумажки на один направо.
(Ответить) (Thread)
[User Picture]From: avva
2012-07-04 03:53 pm
:) смешной вариант.
(Ответить) (Parent) (Thread)
[User Picture]From: helendile
2012-07-04 01:54 pm
74
(Ответить) (Thread)
From: lantios
2012-07-04 01:58 pm
49 мудрецов сразу понимают, какого цвета на них колпаки.
Остальных 50 мудрецов надо надежно разделить на две группы по 25 мудрецов, чтобы одна группа назвала один цвет, а другая — другой. Как это сделать — не знаю :)

Правильный ответ, конечно, 49 + 25 = 74.
(Ответить) (Thread)
[User Picture]From: mme_n_b
2012-07-04 02:08 pm
0. Предположим, что 50 мудрецов одеты в колпак цвета А, а 49 - цвета Б.
1. 49 мудрецов пересчитывают всех прочих, находят 50 с колпаком цвета А и 48 с колпаком цвета Б, заключают, что на них цвет Б.
2. 50 мудрецов пересчитывают прочих, находят 49 с колпаком цвета А, и 49 с колпаком цвета Б, понимают, что принадлежат к большинству, но не могут выбрать цвет.
Того 49.
(Ответить) (Thread)
[User Picture]From: mme_n_b
2012-07-04 02:10 pm
Но проще всего каждому мудрецу сразу повернуться к соседу, и сказать: <на тебе колпак такого-то цвета>. Тогда 99.
(Ответить) (Thread)
[User Picture]From: avva
2012-07-04 03:53 pm
Это запрещено - никакого общения после надевания колпаков.
(Ответить) (Parent) (Thread)
[User Picture]From: pargentum
2012-07-04 02:11 pm
Неясно, какие действия мудрецы могут совершать до того, как начнут писать на бумажках.

Например, стратегия может состоять в том, что все мудрецы, которые видят пятьдесят колпаков одного цвета, совершают какое-то не запрещенное правилами действие, например, подмигивают правым глазом или грызут карандаш. Тогда k=99.

Если у мест за столом есть какая-то естественная нумерация, то я придумал стратегию для k=73: те, кто видит 50 колпаков одного цвета, пишут другой цвет - это 49 правильных ответов. А те, кто видит 49 колпаков, выбирают цвет по принципу чет-нечет - это 24.5 правильных ответов или 24 гарантированных.
(Ответить) (Thread)
[User Picture]From: avva
2012-07-04 03:50 pm
Нет, никакого общения между мудрецами после надевания колпаков, никаких знаков итп. не может быть. Ваше второе решение тоже неверно, увы.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2012-07-04 02:21 pm
49 мудрецов заведомо знают свой цвет (они видят 50 колпаков одного цвета, значит, их цвет - противоположный). Если из оставшихся 50 (видящих по 49 колпаков каждого цвета) половина напишет один цвет, а другая половина - противоположный (кто какой, можно договориться заранее), то кто-нибудь точно угадает. Таким образом, можно гарантировать, что k=49+25=74 мудреца напишут свой цвет правильно.
(Ответить) (Thread)
[User Picture]From: avva
2012-07-04 04:20 pm

Нет, потому что может так получиться, что на них надели колпаки именно так, что все эти 50 назовут неправильно.
(Ответить) (Parent) (Thread) (Развернуть)
Re: - (Анонимно) Развернуть
[User Picture]From: vlad_gor
2012-07-04 02:44 pm
Заранее договариваются, как выбрать первый цвет, как второй. Либо по алфавиту, либо по спектру.
Те, кто видят ситуацию 48+50 могут вычислить свой цвет. Таких 49.
Остальные 50, которые видят 49+49, делают такой трюк. Каждый делит своих соседей на 2 части на соседей слева и соседей справа. И считает сколько первого цвета в каждой части. Т.к. 49 нечетное, то какое то число больше, либо правое, либо левое. После этого, если правого больше, то он пишет первый цвет, если левое, то второй цвет.
Т.е. угадывают 49+25=74
(Ответить) (Thread)
[User Picture]From: dreamer_other
2012-07-04 03:28 pm
1) каждый мудрец считает цвета других
2) те что насчитали 50 какого-то цвета, знают свой цвет точно
3) те, что насчитали по 49 обоих, должны разделиться на 2 группы по 25 человек с разными цветами. делают это таким образом: мысленно разбивают круг на 2 части, берут себе тот цвет которого справа больше, если одинакого, берут тот, который ближе к началу радуги(если заранее цветов не знают, если знают, могут договориться о конкретном)
(Ответить) (Thread)
[User Picture]From: konaire
2012-07-04 03:35 pm
49 получаем автоматически - это те, кто видят распределение цветов 48 на 50.

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

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

Группа:
I   15 18
II   17 16
III 17 16

Такое распределение минимизирует угадывания цветов мудрецами, при этом 18 человек из первой группы назовут верный цвет.

Ответ: 49+18 = 67 человек. Правильно?
(Ответить) (Thread)
[User Picture]From: spamsink
2012-07-04 03:46 pm
Судя по тому, что мой ответ не расскринен, я решил правильно, но таки да, после нескольких мысленных "ой, ни фига не так".
(Ответить) (Thread)
[User Picture]From: avva
2012-07-04 03:51 pm
Я не вижу нигде твоего решения. Не расскринивал ничего потому что несколько часов был без интернета, так бывает :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: lord_corwin
2012-07-04 04:02 pm
По-моему, я нашел решение для k=74.

49 называют свой цвет сразу, а из оставшихся 50 каждый делит стол пополам. Получается две половины по (98/2 = 49). Каждый называет цвет, которого больше (например) на правой (например) от него половине. Тогда 25 из 50 назовут цвет правильно.

Договариваются о том, "больше" или "меньше" и на какой половине считать.
(Ответить) (Thread)
[User Picture]From: avva
2012-07-04 04:16 pm
Браво! Ваше решение правильное.
(Ответить) (Parent) (Thread)
[User Picture]From: talash
2012-07-04 04:03 pm
I think I can guarantee at least 73 sages to be correct using the following algorithm:

- Naturally there's going to be a minority group of 49 sages who will know their own colour, since they'll see 50 hats of one colour

- the other 50 sages will not know their own colour

- what my algorithm says is how to behave if you don't know your own colour

- So, suppose the hat colours are white and black. The first thing is-- we decide that everyone who doesn't know their own colour will get a "default choice" colour-- either white or black, roughly half (49 get one colour and 50 get another).

- This alone, however, does not guarantee anything, since there can be a case of all black hat wearers not knowing their own colour and their default choice being white (or vice versa)

- So before implementing his default choice one has to look around at the wearers of the colour opposite from his default choice and see how many of them will be wrong about guessing their colour if they implement their default choice

- If the number is above half of the wearers of the opposite colour, then one has to change his default choice to the opposite (in our case: if the number of black colour wearers who will guess they wear a white hat by default is >24, then one has to guess "white").
(Ответить) (Thread)
[User Picture]From: n_r_dreams
2012-07-04 04:39 pm
Додумался до 51. 49 - очевидно, остальные по ксору соседей. Минимум у двоих результат XOR будет различаться от остальных 48 при любой расстановке шляп.
(Ответить) (Thread)
Страница 1 из 4
<<[1] [2] [3] [4] >>