Высшая проба 2023, 9 класс, задача 6

Ответ: да.

Решение. Рассмотрим веса , , , , , , , (здесь и далее веса будут измеряться в граммах). Сделаем две проверки: . Сначала рассмотрим первое взвешивание. Докажем, что если некоторые три монеты уравновесили некоторые две монеты, то это обязательно , , на одной чаше и , на другой. Будем называть монеты , , , , маленькими, а монеты , , — большими. Если среди пяти монет, участвующих в первом взвешивании, есть большие, то на каждой чаше такая монета должна быть ровно одна (иначе чаша, где таких монет больше, перевесит). При этом веса всех маленьких монет делятся на , а веса больших монет дают разные остатки при делении на . Тогда суммарные веса на чашах дают разные остатки при делении на , что невозможно в случае равенства. Значит, все эти пять монет — маленькие. Тогда обе чаши весят по . Легко понять, что сумма весов двух монет может быть равна , только если эти две монеты весят и . Тогда три другие монеты весят , , . Следовательно, если первое взвешивание показало равенство, то , , находятся на чаше с монетами (эту группу назовём ), а , — на чаше с двумя монетами (эту группу назовём ). При этом монеты , , (эту группу назовём ) в первом взвешивании не участвуют.

Рассмотрим второе взвешивание. На одну чашу взяли по одной монете из каждой из трёх групп , , , минимальная сумма весов таких монет . На вторую чашу взяли по одной монете из групп и , максимальная сумма весов таких монет . В силу того, что больше всего на , при взятии любых других монет неравенство во втором взвешивании выполняться не будет. Значит, на одной чаше лежат монеты , , , а на другой — , . Итак, при каждом взвешивании мы однозначно определили набор монет на каждой чаше. При этом для всех монет различны пары групп, куда они попали при первом и втором взвешиваниях (либо на чашу с монетами, либо на чашу с монетами, либо не взвешивалась). Следовательно, вес каждой монеты определяется однозначно.

Замечание. В любом верном алгоритме одно взвешивание должно устанавливать равенство весов двух монет на одной чаше с тремя монетами на другой, а другое взвешивание должно устанавливать, что две монеты на одной чаше тяжелее трёх монет на другой. Это можно понять из следующих соображений. • Монеты, входящие при одном взвешивании в одну из трёх групп (на первой чаше, на второй и не взвешиваемые), обязаны оказаться в разных группах при втором взвешивании. (Действительно, если две монеты оказались в одних и тех же группах при обоих взвешиваниях, лаборант мог их перепутать и мы бы ничего не заметили.) • Из предыдущего пункта следует, что никакое взвешивание не может создавать группу из монет или более. Это означает, что в каждом взвешивании на чашах либо по монеты, либо и . • Также из первого пункта следует, что монеты можно расположить в таблице × , по строкам которой располагаются группы первого взвешивания, а по столбцам — группы второго; ровно одна из клеток останется без монеты.

• Не могут оба взвешивания иметь одинаковый формат и исход. (Например, не может быть, чтобы в обоих взвешиваниях монеты на одной чаше перевешивали монеты на другой.) Действительно, в этом случае если в таблице, привёденной выше, упорядочить строки и столбцы одинаковым образом (например, в порядке лёгкое/тяжёлое/невзвешенное), то пустая клетка расположится на главной диагонали; тогда лаборант мог так перепутать наклейки, чтобы монеты отразились относительно этой диагонали, и заметить этого мы бы не смогли. • Не может быть взвешивания, в котором на обеих чашах по три монеты, и между ними установилось равновесие. Например, пусть первое взвешивание так устроено; его чаши сопоставим первой и второй строкам нашей таблицы. Тогда лаборант мог так перепутать наклейки, что первая и вторая строка поменяются местами. На результатах наших взвешиваний это бы не отразилось, то есть мы бы такую ошибку не заметили. • Не может быть взвешивания, в котором на обеих чашах по три монеты, и одна чаша тяжелее другой. Чтобы это доказать, предположим противное — пусть это было первое взвешивание. Лёгкую его чашу сопоставим первой строке, а тяжёлую — третьей строке; столбцы упорядочим так, чтобы группа из монет от второго взвешивания оказалась в последнем столбце (независимо от самой структуры второго взвешивания).

Если теперь переупорядочить числа в столбцах сверху вниз по возрастанию (оставив пустую клетку пустой), то показания весов не изменятся: состав столбцов не поменяется, а нижняя строка окажется помонетно тяжелее верхней. Но если после этого поменять местами, например, в центральном столбце две нижние монеты, то нижняя строка всё равно будет тяжелее верхней! Получается, что мы не можем однозначно установить расположение монет, то есть у лаборанта опять есть шанс нас обмануть. • Аналогично доказывается, что не может быть взвешивания, в котором чаша с тремя монетами перевешивает чашу с двумя. Также из аналогичных соображений нетрудно понять, что для монет двумя взвешиваниями обойтись уже ни в какой ситуации не получится.