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

$n$ саны — 1-ден үлкен натурал сан болсын. Костяда, егер салмағы жағынан әр түрлі $2n+1$ тиын салсақ, салмағы жағынан қайсысы ортанғы екенін көрсететін құрал бар. Барон Мюнхгаузен Костяға салмағы жағынан әр түрлі $4n+1$ тиын берді және де ішіндігі бір тиынды салмағы жағынан ортаңғысы деп көрсетті. Өзінің құралымен ең көп дегенде $n+2$ өлшеу жүргізу арқылы Барон Мюнхгаузеннің шың немесе өтірік айтқанын Костя қалай тексере алады? ( К. Кноп )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Пусть $M$— монета, которую барон считает средней по весу. Костя может действовать по следующему алгоритму:
0. Счетчик повторов установим равным 0. Положим в прибор монету $M$ и еще какие-то $2n$ монет.
1. Пока значение счетчика не достигло $n$, делаем следующее: если прибор укажет на $M$ как среднюю, то перейдем к шагу 2; если прибор укажет на другую монету, то выкинем ее из прибора, добавим в прибор любую из остальных (не выкинутых ранее) монет, увеличим счетчик повторов на 1 и вернемся к шагу 1; если счетчик повторов равен $n$, то барон не прав. Конец.
2. Оставим в приборе монету $M$ и заменим все остальные $2n$ монет (на все прочие $2n$ монет). Если прибор снова покажет на $M$ как на среднюю, то барон прав, иначе — не прав.
Обоснование вывода, сделанного на шаге 2. Если $M$ — средняя по весу в двух последних тестированиях, то в каждом из них были $n$ монет легче $M$ и $n$ монет тяжелее $M$. Значит, всего есть $2n$ монет легче $M$ и $2n$ монет тяжелее. Следовательно, $M$ — средняя по весу. Если же в предпоследнем тестировании $M$ средняя, а в последнем нет, то $M$ тяжелее, чем ровно $n+x$ монет, где $x$ не равно $n$, — а, значит, точно не средняя по весу из всех монет.
Обоснование вывода, сделанного в конце шага 1. Пусть в $i$-ом тестировании было $x_i$ монет легче монеты $M$. Без ограничения общности можно считать, что при первом тестировании $M$ была тяжелее средней монеты, то есть $x_1 > n$. Далее, если добавленная после $i$-го тестирования монета легче $M$, то $x_{i+1} = x_i$, иначе $x_{i+1} = x_i - 1$. Если счетчик повторов достиг $n$, это значит, что мы выкинули $n$ монет, и при этом $x_i$ никогда не становилось равным $n$. Но тогда все $x_i$ больше $n$, и, в частности, $x_n > n$. Так как уже найдены $x_n$ не выкинутых и $n$ выкинутых монет, которые легче $M$, и $x_n+n > 2n$, то $M $ — точно не средняя.