Задачи на взвешивания: как строить дерево решений

В задачах на чашечные весы важно заранее знать, чем отличается искомый предмет. Монета может быть заведомо тяжелее настоящих или просто иметь неизвестное отличие по массе. Это разные задачи. Также нужно понимать, показывают ли весы только сравнение двух чаш или точное значение массы.

Пример с девятью монетами

Среди 9 монет одна заведомо тяжелее остальных, настоящие имеют равную массу. Найдём её за два взвешивания. Разделим монеты на три группы по 3. Сравним первые две группы. Если равны, тяжёлая среди оставшихся 3. Если нет, она находится в более тяжёлой группе.

После первого опыта в любом случае остаются 3 кандидата. Сравним две монеты из выбранной тройки. Если одна тяжелее, она и есть искомая; если равны, подходит третья. Решение охватывает все исходы, а не только удобный случай равновесия.

Почему три группы

Одно сравнение даёт три возможных результата: левая чаша тяжелее, правая тяжелее, равновесие. Два последовательных сравнения образуют не более 3²=9 различимых ветвей. Это объясняет естественность разделения на три части в задаче с известным направлением отличия.

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

Запишите план до опыта

Дерево решений начинается с первого взвешивания. От него отходят три ветви, у каждой нужно указать следующее действие. Нельзя заранее выбирать второе сравнение, которое работает только при одном результате первого. Хорошая стратегия адаптируется к полученной информации.

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

Задания и ответы

1. Одна из 27 монет заведомо тяжелее. Сколько взвешиваний достаточно при таком же подходе?3: группы 9→3→1. 2. Можно ли всегда найти одну тяжёлую среди 10 за два сравнения? Нет: разных кандидатов 10, а ветвей не более 9. 3. Как работать с 8 монетами за два сравнения? Сравнить группы 3 и 3; при равновесии остаются 2, иначе 3, что разрешается одним сравнением.

Проверьте свою стратегию на каждом номере искомой монеты. Это не эксперимент с настоящими деньгами, а логический контроль полноты. Самая частая ошибка — сказать «сравним половины» и не объяснить, что делать при нечётном числе или равновесии.

Почему нужно известное направление отличия

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

Связанные материалы

Основы теории вероятностей, Размещения, перестановки и сочетания.