|
|
 |
Условие
Дано натуральное $k$. На столе по кругу лежат $n$ внешне одинаковых монет массами $1$, $2$, $\ldots$, $n$ г. Вам известно, что эти массы идут по порядку, но неизвестно, по часовой стрелке или против, и с какого места начинаются. Одним взвешиванием разрешается сравнить любые две монеты и узнать, какая тяжелее. Барон Мюнхгаузен утверждает, что вы можете сделать $k$ взвешиваний так, чтобы по их результатам гарантированно определить массу хотя бы одной монеты. При каком наибольшем $n$ слова барона будут правдой?Решение
Случай $k=1$ очевиден. Далее разберём случай $k > 1$.
Алгоритм. Пусть $n = 2^k - 1$. Пусть уже проведено несколько взвешиваний, нарисуем соответствующие им стрелки (от меньшей монеты к большей). Будем считать, что монеты делят окружность, на которой лежат, на равные промежутки длины 1 (а сами монеты — точки на этой окружности).
Пусть монеты $A,B,C,D$ расположены на окружности именно в таком циклическом порядке (возможно, $A=D$ или $B=C$) и проведены стрелки $\overrightarrow{AC}$ и $\overrightarrow{BD}$. Назовём {\it зазором} между этими стрелками объединение дуг $BC$ и $DA$, а длиной зазора — длину наибольшей из дуг $BC$ и $DA$ (дуги берём «в том же циклическом порядке», то есть, например, дуга $BC$ не содержит внутри точек $A$ и $D$).
Докажем, что «разрыв» между монетами (граница между монетой массы 1 и монетой массы $n$) расположен внутри зазора (то есть, на $BC$ или $DA$).
В самом деле, пусть разрыв расположен, например, на дуге $CD$. Пройдём по окружности от монеты массой 1 до монеты массой $n$ (массы всё время будут возрастать).
В зависимости от направления, в котором идут монеты, мы в одном случае пройдём сначала $D$, а потом $B$, что невозможно (так как $B < D$), а в другом случае пройдём сначала $C$, а потом $A$, что тоже невозможно (так как $A < C$). Противоречие. Аналогично, разрыв не может быть на $AB$.
Докажем, что далее можно делать взвешивания так, чтобы минимальная длина зазора с каждым разом уменьшался хотя бы в два раза. Действительно, пусть длина зазора между $\overrightarrow{AC}$ и $\overrightarrow{BD}$ не превосходит $2^{a}$. Пусть $M$ — середина (или почти середина в случае нечётной длины) дуги $BC$, а $N$ — середина (или почти середина) дуги $DA$. Если $M < N$, то длина зазора между $\overrightarrow{MN}$ и $\overrightarrow{AC}$ не превосходит $2^{a-1}$ (см. рисунок), а если $N < M$, это верно для длины зазора между $\overrightarrow{NM}$ и $\overrightarrow{BD}$.
Оценка. Предположим, что такой алгоритм есть при некотором $n$ и за $k$ взвешиваний можно вычислить какую-то монету. Тогда после всех взвешиваний монеты могут быть расположены не более чем двумя способами, и, произведя ещё одно взвешивание, мы узнаем полностью всю конфигурацию.
Но всего разных конфигураций $2n$, а возможных результатов последовательности из $k+1$ взвешиваний — не более $2^{k+1}$.
Итак, $2n \leqslant 2^{k+1}$, откуда $n \leqslant 2^k$.
Поэтому осталось лишь доказать, что при $n = 2^k$ алгоритма нет.
Предположим противное, и есть какой-то алгоритм.
Всего имеется $2^{k+1}$ возможных конфигураций (того, как в действительности расположены монеты). Эти конфигурации бывают типа $A$ или $B$ (по или против часовой стрелки). Здесь мы используем, что $k > 1$ (в случае двух монет нет разницы между расположениями по и против часовой стрелки).
После выполнения $k$ взвешиваний должны исключаться все конфигурации, кроме может быть двух: одной из $A$, второй из $B$.
Тогда в любой ситуации в конце должно оставаться ровно две конфигурации: одна из $A$, вторая из $B$.
Изначально, до взвешиваний, в $A$ и $B$ по $2^k$ конфигураций. Несложно понять, что после каждого взвешивания, вне зависимости от результата взвешивания, число возможных конфигураций из $A$ должно в точности уполовиниваться — иначе результаты следующих взвешиваний могут оказаться такие, что в конце останется либо 0, либо больше одной конфигурации из $A$. То же верно и для $B$.
Нарисуем правильный $n$-угольник (вершины соответствуют монетам), каждую конфигурацию типа $A$ изобразим как красную сторону многоугольника (соединяющую монеты 1 и $n$). Каждая конфигурация типа $B$ — синяя сторона многоугольника (снова соединяющая монеты 1 и $n$).
Изначально, когда имеется $2^{k+1}$ возможных конфигураций, каждая сторона «двойная» — проведена и синим, и красным.
Далее каждым ходом алгоритма выбираются две вершины, $X$ и $Y$. Заметим, что далее, в зависимости от ответа (кто из $X$, $Y$ тяжелее), происходит одно из двух:
либо выкидываются синие стороны на дуге $XY$ и красные на дуге $YX$,
либо выкидываются синие стороны на дуге $YX$ и красные на дуге $XY$.
И, напомним, нам надо, чтобы каждый раз в любом случае число красных сторон уменьшалось ровно вдвое, и число синих сторон уменьшалось вдвое.
Индукцией по $i$ неcложно показать, что после $i$-го хода синие стороны будут образовывать дугу длины $2^{k-i}$, а красные стороны — симметричную ей дугу. Переход индукции — несложным перебором показываем, что следующее взвешивание должно затрагивать середины этих дуг.
Тогда после $k$ взвешиваний останутся две противоположные стороны, одна красная, а другая синяя. Но такие две конфигурации не имеют общих чисел, поэтому ни одно число восстановить нельзя.
