Задача 4. Две кучки и одно взвешивание

Что показывают весы, если на чашах поровну монет

Мы знаем, из какой кучки каждая монета, но не знаем, где в кучке фальшивая. «Гарантированно найти» значит: после взвешивания указать не меньше $8$ монет и доказать, что они настоящие, — как бы ни лежали фальшивые.

Положим на каждую чашу поровну монет, скажем по $n$. Пусть настоящая монета весит $m$ г, а фальшивая на $d$ г меньше. Если на чаше $k$ фальшивых, то она весит $n\cdot m-k\cdot d$ г. Первое слагаемое у обеих чаш одинаковое, поэтому:

• легче та чаша, на которой больше фальшивых;
• равновесие — ровно тогда, когда фальшивых на чашах поровну (здесь важно, что обе фальшивые весят одинаково).

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

Перевесившая чаша — вся из настоящих монет

Пусть одна чаша перевесила, то есть оказалась тяжелее. По шагу 1 на ней фальшивых меньше, чем на другой. Если бы на ней была хоть одна фальшивая, на другой чаше их было бы не меньше двух — всего не меньше трёх. Но фальшивых только две. Значит, на перевесившей чаше фальшивых нет, и все её монеты настоящие.

Отсюда план: положим на каждую чашу по $8$ монет. Если весы не в равновесии, мы сразу получаем $8$ настоящих монет — все монеты тяжёлой чаши. Осталось позаботиться о равновесии.

Опасный исход — равновесие

Равновесие значит, что фальшивых на чашах поровну: либо $0$ и $0$, либо $1$ и $1$. Весы эти случаи не различают, поэтому нужные монеты должны оказаться настоящими в обоих.

В случае «$0$ и $0$» обе фальшивые могут лежать в стороне, и тогда любая отложенная монета может оказаться фальшивой. А в случае «$1$ и $1$» под подозрением монеты на чашах. Так мы рискуем не найти ни одной точно настоящей монеты.

Как убрать случай «$0$ и $0$»: положим на весы всю кучку Б — все её $11$ монет. Тогда фальшивая кучки Б точно на весах, и при равновесии на каждой чаше лежит ровно по одной фальшивой.

На весах $8+8=16$ монет: $11$ монет кучки Б и ещё $16-11=5$ монет кучки А. Оставшиеся $11-5=6$ монет кучки А лежат в стороне.

Делим монеты между чашами

При равновесии на каждой чаше одна фальшивая. Хорошо бы сразу знать, какая где. Для этого соберём одну чашу из монет одной кучки: на правую чашу положим $8$ монет кучки Б. На левую пойдут оставшиеся $11-8=3$ монеты кучки Б и $5$ монет кучки А — тоже $8$ монет (рисунок ниже).

Разберём равновесие. На правой чаше одна фальшивая, а там только монеты кучки Б — значит, это фальшивая кучки Б. Фальшивая на левой чаше тогда из кучки А: фальшивая кучки Б уже справа. Отсюда:

• $3$ монеты кучки Б на левой чаше настоящие;
• фальшивая кучки А лежит среди её $5$ монет на левой чаше, поэтому $6$ отложенных монет кучки А настоящие.

Всего $3+6=9$ точно настоящих монет.

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

Проверяем все три исхода

Взвешивание: слева $5$ монет кучки А и $3$ монеты кучки Б, справа $8$ монет кучки Б, в стороне $6$ монет кучки А.

• Правая чаша легче (перевесила левая): по шагу 2 все $8$ монет левой чаши настоящие.

• Левая чаша легче (перевесила правая): все $8$ монет правой чаши настоящие.

• Равновесие: по шагу 4 настоящие $3$ монеты кучки Б с левой чаши и $6$ отложенных монет кучки А — $9$ монет.

Каждый исход действительно может случиться. Например: фальшивая кучки А в стороне, а фальшивая кучки Б слева — левая чаша легче; фальшивая А в стороне, фальшивая Б справа — правая чаша легче; фальшивая А слева, фальшивая Б справа — равновесие. Но при любом исходе мы указываем не меньше $8$ монет, которые точно настоящие. Значит, можно.