Определение типов монет с помощью 101 взвешивания

Автор: [Рябичев А.](https://mirolimp.ru/tasks?author%5Bvalue%5D=100808)

  Хватит даже 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.