Олимпиада имени Леонарда Эйлера2012-2013 учебный год, II тур заключительного этапа

99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным — другого (но заранее неизвестно, какого именно из двух цветов 50 колпаков, а какого — 49). Каждый из мудрецов видит цвета всех колпаков, кроме своего собственного. Все мудрецы должны одновременно написать (каждый на своей бумажке) цвет своего колпака. Смогут ли мудрецы заранее договориться отвечать так, чтобы не менее 74 из них дали верные ответы? ( U. Feige )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Пусть среди колпаков 50 белых и 49 черных. Понятно, что те 49 мудрецов, которые видят по 50 белых и 48 черных колпаков, знают, что на них черные колпаки. Пусть теперь каждый из тех, кто видит по 49 белых и черных колпаков, назовет тот цвет, который преобладает среди 49 человек, следующих за ним по часовой стрелке. Если А — один из таких мудрецов, а Б — 25-ый от него по часовой стрелке мудрец в белом колпаке. Если между А и Б не больше 48 человек, А скажет, что на нем белый колпак, в противном случае Б скажет, что на нем белый колпак. Поскольку все 50 мудрецов в белых колпаках делятся на 25 таких пар (А, Б), 25 из них верно назовут цвет своего колпака, и в итоге будет дано не менее $49+25 = 74$ верных ответов.