Почему деление пополам не всегда лучшее
Обычное сравнение «половина против половины» использует только два результата, если ни одной монеты не остаётся в стороне. Но чашечные весы способны различать три состояния. Разделив девять монет на группы по три, одним взвешиванием можно определить нужную тройку.
Если две тройки равны, фальшивая монета находится в отложенной группе. Если одна легче и заранее известно, что фальшивая монета лёгкая, нужная группа тоже сразу ясна.
Стройте дерево исходов
Перед первым действием нарисуйте три ветки — «лево», «равно», «право». Под каждой напишите, какие кандидаты останутся. Хорошее взвешивание оставляет примерно одинаковое число кандидатов на каждой ветке.
Затем повторите принцип внутри выбранной группы. Три монеты находятся за одно дополнительное сравнение: взвесьте две из них, а третью оставьте. Равновесие укажет на отложенную монету, перевес — на одну из чаш.
Когда условие становится сложнее
Если неизвестно, легче фальшивая монета или тяжелее, каждая монета создаёт две гипотезы. Тогда нужно сохранять эталонные монеты и внимательно учитывать направление прошлых весов. Простого деления на три может быть недостаточно.
Проверяйте стратегию для каждого возможного положения подделки. Слова «найти монету» и «найти монету и определить, легче она или тяжелее» задают разные задачи и разное минимальное число взвешиваний.
Коротко о частом
Вопросы и ответы
Сколько вариантов различают два взвешивания?
В идеальном случае до девяти последовательностей исходов, потому что у каждого взвешивания три результата. Но ограничения конкретной задачи могут уменьшить полезное число веток.
Можно ли пользоваться гирями?
Только если это прямо сказано. Классические задачи предполагают чашечные весы без гирь и сравнение групп монет между собой.