Pythonist

Прежде всего, мы не можем сравнивать монеты поштучно, ведь взвешивать можно только трижды. Поэтому мы будем сравнивать монеты не по одной.

Разложим монетки в 3 стопки. Кладем на чаши весов две любые стопки.

Дальше возможны разные варианты событий.

Вариант А. Две стопки монет весят одинаково. Следовательно, все монеты в них настоящие, а фальшивая осталась в третьей стопке.

Карандашом помечаем уже взвешенные монеты, например, ноликами.

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

А-1: Если весы в равновесии, оставшаяся одна монета из третьей стопки фальшивая.

А-2: Если монеты из третьей стопки весят больше настоящих, помечаем их плюсами. Если весят меньше — минусами.

Берем две из трех свежепомеченных монет и сравниваем их вес. Если вес равный, третья монета — фальшивка. Но что, если одна чаша перевесила? Мы ведь уже использовали все взвешивания!

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

Мы разобрали Вариант А, когда при первом взвешивании весы были в равновесии. Идем дальше.

Вариант Б. Одна из чаш перевесила. Помечаем монеты с перевесившей чаши плюсами, а с другой — минусами. Оставшиеся невзвешенными монеты помечаем нулями. Фальшивая монета — среди тех, что на чашах весов.

У нас осталось только 2 взвешивания, поэтому мы будем менять монеты местами. Убираем с одной чаши три монеты с плюсами и заменяем их тремя монетами с минусами (итого на чаше 3 «минуса» и 1 «плюс»). На второй чаше остается 1 монета с минусом, а к ней докладываем 3 монеты с нулями.

Теперь есть три варианта.

1. Чаша, что перевешивала раньше, и теперь тоже перевешивает. Это означает, что или оставшаяся на этой чаше монета с плюсом тяжелее остальных, или оставшаяся на другой чаше монета с минусом легче остальных. Мы берем любую из них (с плюсом или с минусом) и сравниваем с монетой с ноликом (наш эталон). Если вес отличается, эта монета фальшивая. Если весят одинаково, фальшивая та, которую не сравнивали с эталоном.

2. Чаша, которая раньше была тяжелее, теперь стала легче второй. Это значит, что три монеты со знаками «минус», которые мы переместили с одной чаши на другую, легче остальных. Мы берем любые две из них и сравниваем их друг с другом. Если весы в равновесии, фальшивка — третья монета. Если одна чаша перевешивает, фальшивка — более легкая монета.

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

Король удовлетворен вашим решением. Фальшивомонетчик занимает ваше место в темнице.