|
|
 |
Условие
Есть 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.
