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

[avva]

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

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

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

Дополнение:

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

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

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

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

Comments

[aintlion.livejournal.com]

73

[avva.livejournal.com]

Нет.

[lobastova.livejournal.com]

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

[avva.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.

[avva.livejournal.com]

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

[pargentum.livejournal.com]

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

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

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

[avva.livejournal.com]

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

[(Anonymous)]

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

[avva.livejournal.com]

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

[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]

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

[lord-corwin.livejournal.com]

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

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

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

[avva.livejournal.com]

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

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

[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.

[(Anonymous)]

Интересно ещё подумать и над вариантом 50+51

[aivean.livejournal.com]

Насколько я понимаю, ответ 74 (49 тех, кто видит 50 колпаков перед собой + 25 тех, кто видит перед собой 49 колпаков одного цвета и 49 другого). Смысл задачи в стратегии разбития этих 50 мудрецов на две равные группы.

Я предлагаю заранее выбрать одного примечательного мудреца и назначить ему цвет, допустим, первый. Далее, за столом, все мудрецы-"неудачники", те, которые не могут однозначно определить свой цвет, считают, что примечательный мудрец выбрал первый цвет (и он действительно должен его выбрать, если он тоже в списке неудачников). Затем все "неудачники" отсчитывают по часовой стрелке расстояние от них до примечательного мудреца. При расчёте считаются только мудрецы первого цвета. (То есть, если между текущим "неудачником" и примечательным мудрецом нет других мудрецов в колпаке первого цвета, то расстояние считается равным 0). "Неудачники" с расстоянием кратным двойке выбирают второй цвет, остальные неудачники -- первый цвет.

[donc.livejournal.com]

Решение тоже на поверхности, но пока придумал только так. Как описывалось выше - те, кто видит распределение колпаков как 48 и 50 имеют цвет 48ми и гарантированно его угадывают. Остальные, кто видит равное кол-во цветов, смотрят на ту правую половину голов от себя (или левую, главное одну и ту же). И выбирают наиболее частый цвет. Половина будет составлять 49, т.е. какой-то цвет всегда больше. Таким образом, должно получится, что половина выберет один цвет и половина другой. Гарантированное кол-во выдивших - 49+25 или 74.

[kashelevich.livejournal.com]

74

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

[pycalka.livejournal.com]

Выбираем человека Ф, с которого будет идти отсчет.
Если м(удрец) видит 50 колпаков одного цвета, то он точно другого.
Иначе, если начиная с Ф по часовой стрелке до м четное количество колпаков цвета 1 то м выбирает для себя цвет 1. Нечетное - цвет 2.

Получаем 49 + 50/2 = 74

[huzhepidarasa.livejournal.com]

74.

Вкратце, 49 (видящие 48+50) знают свой цвет. 50 (видящие 49+49) дают ответ в зависимости от четности перестановки, которую видят перед собой. Половина из них даст правильный ответ.

Похоже на правду?

[http://users.livejournal.com/_iga/]

Мудрец должен сосчитать число шляп разных цветов на всех остальных мудрецах.
Если их поровну, то ответить случайным образом и угадать с вероятностью 0,5.
В противном случае будет 48 шляп ЦветаX и 50 шляп ЦветаY.
Мудрец должен ответить "ЦветX".

Первым вариантом (случайно) ответит один мудрец.
Остальные 98 мудрецов смогут ответить вторым вариантом.

Итого k=98,5

[webface.livejournal.com]

А мудрецы заранее знают, какого цвета колпаков будет 50 штук, а какого 49?

[tasmanj.livejournal.com]

74 = 49+25 (можно ли больше?)

49 мудрецов легко определяют свой цвет, потому что видят 48 мудрецов своего и 50 мудрецов другого цвета.

Остальные 50 видят поровну обоих цветов. Цель - разделить их поровну, что бы половина написала цвет 1 и половина цвет 2. Каждый из них может посчитать сколько из 49 мудрецов сидящих "слева" имеет колпак цвета 1 и сколько из 49 мудрецов сидящих "справа" тоже имеют колпак цвета 1. Если в "левой" части колпаков цвета 1 будет больше то он будет писать на бумажке цвет 1, а в противном случае цвет 2. Таким образом мы можем разделить 50 мудрецов поровну и половина из них угадает свой цвет.