Леонард Эйлер атындағы олимпиада,2012-2013 оқу жылы, қорытынды кезеңнің 2-ші туры

99 дана дөңгелек үстел бойына отыр. Даналарға олардың 50-і екі түсті қалпақтардың біреуін, ал қалған 49-ы қалған екінші түсті қалпақты киіп алғаны белгілі (бірақ алдын-ала 50 дана да, 49 дана да қандай түсті қалпақ кигені белгісіз). Әр дана басқа даналардың қалпағының түсін көріп, ал өзінің қалпағының түсін көре алмайды. Әр дана бір уақытта (әрқайсысы өз қағазына) өзінің қалпағының түсін жазу керек. Даналар бір-бірімен берген жауаптың ішінде кем дегенде 74 дұрыс жауап болатындай алдын-ала кім қандай жауап жазатыны жайлы келісіп ала алады ма? ( U. Feige )

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

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