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

[avva]

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

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

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

Дополнение:

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

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

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

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