ВсОШ 2019, 11 класс, задача 3

Ответ.

За взвешивание.

Решение.

Докажем сначала, что за взвешивание можно найти самую тяжёлую монету. Более точно, мы докажем по индукции по , что самую тяжёлую из данных монет можно определить за взвешивание, имея трое весов, одни из которых, возможно, испорчены.

Если , то взвесим данные две монеты по очереди на трёх разных весах. Если при одном из взвешиваний весы оказались в равновесии, то эти весы испорчены, значит, мы можем определить более тяжёлую монету по показаниям любых из остальных весов. Если равновесия ни разу не было, то какая-то из монет перевесит хотя бы два раза - она и есть более тяжёлая, так как неверный результат могут давать только одни весы. Это даёт базу индукции.

Пусть теперь . Выберем две монеты и двое весов и сравним за первые два взвешивания эти монеты друг с другом на первых и на вторых весах. Возможны два случая:

Случай 1.

Оба раза перевешивала одна и та же из двух монет; назовём её монетой , а вторую из них - монетой . Так как хотя бы одни из двух весов правильные, то монета действительно тяжелее монеты . Значит, не самая тяжёлая. Задача сводится к тому, чтобы определить самую тяжёлую из монеты: монеты и монет, не участвовавших в первых двух взвешиваниях. По предположению индукции мы можем сделать это за взвешивания. Вместе с первыми двумя взвешиваниями получаем взвешивание.

Случай 2.

Либо одно из первых двух взвешиваний дало равновесие, либо результаты первых двух взвешиваний противоречат друг другу: один раз перевесила одна монета, а другой - другая. Значит, одни из двух использованных весов точно испорчены. Возьмём третьи весы. Тогда они обязательно правильные. Используя их, мы легко можем определить самую тяжёлую монету за взвешивание: сравниваем первую монету со второй, более тяжёлую из них с третьей, более тяжёлую из них с четвёртой и т. д. до последней. Вместе с первыми двумя взвешиваниями получаем (так как ) взвешивание.

Покажем теперь, что менее, чем за взвешивание, заведомо определить самую тяжёлую монету нельзя. Достаточно показать, что её нельзя определить ровно за взвешивания, так как можно добавить произвольные взвешивания и игнорировать их результаты. Предположим противное: имеется алгоритм действий, позволяющий определить самую тяжёлую монету за взвешивания.

Пронумеруем монеты числами . Сделаем первые взвешивания согласно алгоритму. Предположим, что в каждом из них перевешивала монета с большим номером. Согласно принципу Дирихле, среди монет с номерами найдётся такая, которая за произведённые взвешиваний «проигрывала» (оказывалась более лёгкой) не более одного раза; обозначим номер этой монеты через . Конечно же, монета с номером ни разу не «проигрывала». Покажем, что такие результаты взвешиваний возможны. Действительно, такое могло произойти по крайней мере в следующих двух ситуациях.

(А) Монеты упорядочены по возрастанию масс и все весы (в том числе, испорченные) показывали правильные результаты во всех взвешиваниях.

(Б) Монеты упорядочены по возрастанию масс, за исключением монеты номер , которая самая тяжёлая. При этом те весы, на которых монета номер «проиграла», испорчены, и в этом взвешивании показали неверный результат, а в остальных взвешиваниях все весы показывали верные результаты.

Рассмотрим два случая.

Случай 1.

В последнем, -м взвешивании, не участвует монета с номером . Предположим, что опять перевесила монета с большим номером. Тогда каждая из ситуаций (А) и (Б) по-прежнему возможна.

Случай 2.

В последнем взвешивании участвует монета с номером . Предположим, что она перевесила. Тогда, с одной стороны, возможно, что имеет место ситуация (А), и последнее взвешивание выполнялось на испорченных весах. С другой стороны, возможно, что имеет место ситуация (Б), и в последнем взвешивании весы показали правильный результат.

Итак, каким бы ни было одно оставшееся взвешивание, его результат может быть таков, что после него каждая из ситуаций (А) и (Б) будет по-прежнему возможной. Тогда каждая из монет и может быть самой тяжёлой, то есть нам не удалось определить самую тяжёлую монету.