|
|
 |
Условие
Дано натуральное $k$. На столе по кругу лежат $n$ внешне одинаковых монет массами $1$, $2$, $\ldots$, $n$ г. Вам известно, что эти массы идут по порядку, но неизвестно, по часовой стрелке или против, и с какого места начинаются. Барон Мюнхгаузен утверждает, что вы можете сделать $k$ взвешиваний на чашечных весах без гирь так, чтобы по их результатам гарантированно определить массу хотя бы одной монеты. При каком наибольшем $n$ слова барона будут правдой? (На каждую чашу помещается сколько угодно монет.)Решение
Оценка. За $k$ взвешиваний результаты разобьют все $2n$ вариантов расположения монет не более чем на $3^k$ частей. При $n> 3^k$ в какую то часть попадут не менее 3 вариантов, среди них будут два одинакового направления (оба по часовой стрелке или оба против часовой). У любой монеты в этих двух вариантах массы различаются, поэтому никакую из масс нельзя определить однозначно. Значит, $n\leqslant 3^k$.
Осталось разобрать ещё случай $k=1$ — проверить, что $n=3$ не подходит. Будем называть монету числом, равным её массе в граммах. Заметим, что одним взвешиванием мы либо сравним друг с другом какие-то две монеты и ни одну из трёх имеющихся не определим (мы могли сравнить монеты 1 и 2, отложив монету 3, или сравнить монеты 2 и 3, отложив монету 1 — ни одна монета «не осталась на месте»), либо сравним одну монету и пару оставшихся монет и в случае неравенства снова ни одну не определим (могли взять монету 1 против монет 2 и 3, а могли взять монету 2 против 1 и 3, причём в паре монеты могут идти по кругу в любом порядке).
Алгоритм. Ясно, что при $k=1$ и $n=2$ достаточно сравнить две имеющиеся монеты друг с другом, и мы узнаем их обе. Далее везде считаем, что $k > 1$.
Пусть $n=3^k$. Пусть монеты выкладываются в вершины правильного $n$-угольника с вертикальной осью симметрии, проходящей через нижнюю вершину. Их массы определяются однозначно, если мы знаем, на какой стороне лежат массы 1 и $n$ (скажем, что это разрыв) и направление (по или против часовой; разрыв по часовой обозначим $n1$, против часовой — $1n$).
Пусть мы положили несколько монет на левую чашу и столько же на правую. Пометим буквой Л вершины, из которой монеты взяты на левую чашу, и буквой П — на правую. Будем класть на каждую чашу монеты парами из симметричных вершин, по 2 или по 4 на каждую чашу. Результат взвешивания определяет набор подозрительных на разрыв сторон (набор зависит от направления).
Будем брать монеты из вершин как на рисунках
Проведём первое взвешивание по 2 монеты $\text{ЛЛ}\ ?\ \text{ПП}$ так, чтобы было $|\text{ЛЛ}|=1$, $|\text{ПП}|=n/3-1$ (тогда $|\text{ЛП}|=|\text{ПЛ}|=n/3$). При равенстве подозрительные стороны на $\text{ЛЛ}+\text{ПП}$, при неравенстве на $\text{ЛП}+\text{ПЛ}$, при $<$ подозрительны $n1$ на ЛП и $1n$ на ПЛ, при $>$ наоборот.
Изначально было по $n$ подозрительных сторон для каждого направления, теперь их осталось по $n/3$. Сохранилась симметрия подозрительных сторон относительно вертикальной оси.
Случай 1: при неравенстве у нас есть два участка, симметричных друг другу, на одном подозрительны только стороны вида $1n$, на другом — только $n1$.
Случай 2: При равенстве у нас есть два участка (один длины 1), каждый участок симметричен и подозрительная сторона может быть как вида $1n$, так и вида $n1$. Будем проводить взвешивания так, чтобы сохранять все перечисленные свойства.
Случай 1. У нас есть два подозрительных участка длин $3m$, где один симметричен другому. В первый раз такие участки возникли при неравенстве $ > $ или $ < $, запомним, при каком именно. Обозначаем их концы $\text{ЛЛ}'$ и $\text{Л}'\text{Л}$ и разбиваем каждый на три равные части монетами П и $\text{П}'$. Монеты лежат по кругу так $\text{ЛПП}'\text{Л}'\text{Л}'\text{П}'\text{ПЛ}$. Сравниваем $\text{ЛЛЛ}'\text{Л}'\ ?\ \text{ППП}'\text{П}'$. При равенстве подозрительны монеты на $\text{П}'\text{П}$ и $\text{ПП}'$, при неравенстве того же знака как запомненное – подозрительны участки $\text{ЛП}+\text{ПЛ}$, при противоположном – участки $\text{П}'\text{Л}'+\text{Л}'\text{П}'$. Во всех случаях остаются по $m$ подозрительных симметричных пар.
Случай 2. Есть два подозрительных участка: $EF$ длины 1 и $AB$ длины $3m-1$, где $m>1$. Пусть $B'A'$ – участок длины $3m-1$ соседний по часовой с $AB$, который не включает $EF$ (при этом $A'$ может совпасть с $E$, см. рисунок).
Осталось заметить, что при неравенстве мы получили ситуацию случая 1, при равенстве — случай 2, все со втрое меньшим $m$.
Случай 2'. Есть два подозрительных участка, $EF$ длины $1$ и $AB$ длины 2. Взвесим $FF'\ ?\ A'B'$, где $F'$, $A'$, $B'$ – соседи монет $F$, $A$, $B$ по часовой. При равенстве подозрительная пара $A'B$, при неравенстве $<$ имеем $EF=1n$ либо $A'B=n1$, при неравенстве $>$ имеем $EF=n1$ либо $AA'=1n$. Во всех случаях после $k$ испытаний остаются подозрительными два расположения противоположного направления, ввиду нечётности общего числа монет у них есть общая монета.
