|
|
 |
Условие
Есть 100 внешне неразличимых монет трёх типов: золотые, серебряные и медные (каждый тип встречается хотя бы раз). Известно, что золотые весят по 3 г, серебряные – по 2 г, медные – по 1 г.
Как на чашечных весах без гирек определить тип у всех монет не более чем за 101 взвешивание?
Решение
Хватит даже 100 взвешиваний.
Лемма 1. Пусть есть $k$ монет, среди которых все три типа представлены, причём про пару монет $(A, a)$, уже известно, что $A > a$. Тогда можно определить, какая из $k$ монет какого типа, за $k - 1$ взвешивание.
Доказательство. Индукция. База. Если монет три, сравнив оставшуюся монету с $A$ и с $a$, мы упорядочим их по весу.
Шаг индукции. Сравним какие-нибудь две монеты, кроме $A$ и $a$.
Если они равны, то одну можно отбросить (запомнив, с какой она совпадает по весу), и воспользоваться предположением индукции для $k - 1$ монеты.
Если они не равны, скажем, что получилась пара $B > b$. Теперь сравним $A + a$ и $B + b$. Если веса равны, то $A = B$ и $a = b$, так что можно выкинуть $B$ и $b$ (запомнив, что они совпадают по весу с $A$ и $a$), и воспользоваться предположением индукции для $k - 2$ монет.
Пусть веса пар различны, для определённости, $A + a > B + b$. Заметим, что тогда обязательно $A$ = 3 и $b$ = 1. Монеты в паре ($B, a$) имеют либо веса (2, 1), либо (2, 2), либо (3, 2). Итак, сравнив $A + b$ с $B + a$, мы однозначно восстановим веса всех четырёх монет. Среди них есть монета веса 2, будем сравнивать с ней все остальные монеты, на что уйдут оставшиеся $k - 4$ взвешивания.
Лемма 2. Если есть $k$ монет, среди которых все три типа представлены, то можно определить, какая монета какого типа, за k взвешиваний.
Доказательство. Индукция. База. Если монет три, то, сравнив каждую с каждой, мы упорядочим их по весу.
Шаг индукции. Сравним какие-нибудь две монеты. Если они равны, то одну можно отбросить (запомнив, с какой она совпадает по весу) и перейти к случаю $k - 1$ монеты, среди которых все типы представлены.
Если они не равны, скажем, что образовалась пара $A > a$ и воспользуемся леммой 1.
Замечания
1. В решении использовано только то, что сумма весов двух серебряных монет равна сумме весов медной и золотой; тот факт, что серебряная монета вдвое тяжелее медной, не важен.
2. Баллы: 8-9 кл. – 7, 10-11 кл. – 6.
