задачка (математическое)

[avva]

Отличная задачка от knop'а (исходная ссылка). Очень понравилась.

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

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

Дополнение:

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

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

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

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

Comments

[aintlion.livejournal.com]

73

[lobastova.livejournal.com]

Садятся в круг. Каждый пишет на бумажке цвет колпака соседа справа. Потом сдвигают бумажки на один направо.

[helendile.livejournal.com]

74

[lantios.livejournal.com]

49 мудрецов сразу понимают, какого цвета на них колпаки.
Остальных 50 мудрецов надо надежно разделить на две группы по 25 мудрецов, чтобы одна группа назвала один цвет, а другая — другой. Как это сделать — не знаю :)

Правильный ответ, конечно, 49 + 25 = 74.

[mme-n-b.livejournal.com]

0. Предположим, что 50 мудрецов одеты в колпак цвета А, а 49 - цвета Б.
1. 49 мудрецов пересчитывают всех прочих, находят 50 с колпаком цвета А и 48 с колпаком цвета Б, заключают, что на них цвет Б.
2. 50 мудрецов пересчитывают прочих, находят 49 с колпаком цвета А, и 49 с колпаком цвета Б, понимают, что принадлежат к большинству, но не могут выбрать цвет.
Того 49.

[mme-n-b.livejournal.com]

Но проще всего каждому мудрецу сразу повернуться к соседу, и сказать: <на тебе колпак такого-то цвета>. Тогда 99.

[pargentum.livejournal.com]

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

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

Если у мест за столом есть какая-то естественная нумерация, то я придумал стратегию для k=73: те, кто видит 50 колпаков одного цвета, пишут другой цвет - это 49 правильных ответов. А те, кто видит 49 колпаков, выбирают цвет по принципу чет-нечет - это 24.5 правильных ответов или 24 гарантированных.

[(Anonymous)]

49 мудрецов заведомо знают свой цвет (они видят 50 колпаков одного цвета, значит, их цвет - противоположный). Если из оставшихся 50 (видящих по 49 колпаков каждого цвета) половина напишет один цвет, а другая половина - противоположный (кто какой, можно договориться заранее), то кто-нибудь точно угадает. Таким образом, можно гарантировать, что k=49+25=74 мудреца напишут свой цвет правильно.

[vlad-gor.livejournal.com]

Заранее договариваются, как выбрать первый цвет, как второй. Либо по алфавиту, либо по спектру.
Те, кто видят ситуацию 48+50 могут вычислить свой цвет. Таких 49.
Остальные 50, которые видят 49+49, делают такой трюк. Каждый делит своих соседей на 2 части на соседей слева и соседей справа. И считает сколько первого цвета в каждой части. Т.к. 49 нечетное, то какое то число больше, либо правое, либо левое. После этого, если правого больше, то он пишет первый цвет, если левое, то второй цвет.
Т.е. угадывают 49+25=74

[dreamer-other.livejournal.com]

1) каждый мудрец считает цвета других
2) те что насчитали 50 какого-то цвета, знают свой цвет точно
3) те, что насчитали по 49 обоих, должны разделиться на 2 группы по 25 человек с разными цветами. делают это таким образом: мысленно разбивают круг на 2 части, берут себе тот цвет которого справа больше, если одинакого, берут тот, который ближе к началу радуги(если заранее цветов не знают, если знают, могут договориться о конкретном)

[konaire.livejournal.com]

49 получаем автоматически - это те, кто видят распределение цветов 48 на 50.

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

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

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

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

Ответ: 49+18 = 67 человек. Правильно?

[spamsink.livejournal.com]

Судя по тому, что мой ответ не расскринен, я решил правильно, но таки да, после нескольких мысленных "ой, ни фига не так".

[avva.livejournal.com]

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

[avva.livejournal.com]

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

[avva.livejournal.com]

Нет.

[avva.livejournal.com]

:) смешной вариант.

[spamsink.livejournal.com]

Я имею в виду у Кости в журнале - я ответил через 12 минут после появления поста. :)

[avva.livejournal.com]

Это запрещено - никакого общения после надевания колпаков.

[avva.livejournal.com]

Тогда может быть - этого ответа я не могу видеть ;)

[lord-corwin.livejournal.com]

По-моему, я нашел решение для k=74.

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

Договариваются о том, "больше" или "меньше" и на какой половине считать.

[talash.livejournal.com]

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").

[avva.livejournal.com]

Браво! Ваше решение правильное.

[avva.livejournal.com]

Нет, потому что может так получиться, что на них надели колпаки именно так, что все эти 50 назовут неправильно.

[n-r-dreams.livejournal.com]

Додумался до 51. 49 - очевидно, остальные по ксору соседей. Минимум у двоих результат XOR будет различаться от остальных 48 при любой расстановке шляп.

[dibr.livejournal.com]

Ну, ~половина мудрецов правильный ответ напишут и так: если среди соседей 50 колпаков одного цвета (1), и 48 другого (2) - значит, у меня колпак цвета (2). Это даёт нам 48 угадавших мудрецов.

Остальные видят по 49 колпаков каждого цвета, и при отсутствии возможности общения угадать свой цвет не могут. Но - они могут заранее договориться о том, какой цвет каждый из них называет в этом случае: 25 из них (заранее выбранных) называют цвет (1), а другие 25 называют цвет (2). Какая-то из этих половин, очевидно, свой цвет угадает.

При этом мы получаем, что 48+25=73 мудреца угадают свой цвет гарантированно - а заодно получаем то, что более чем 73 мудреца угадать свой цвет не смогут, угадавших (при таком алгоритме) всегда будет 73 :-)

Итого, ответ - 73.