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

Пусть $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$ — точно не средняя.