В условиях ограниченных ресурсов логические задачи перестают быть абстракцией и превращаются в модель реальных процессов принятия решений. Перед нами семь мешков с монетами. Шесть содержат идентичные монеты, один — монеты с отклонением по весу. В распоряжении только балансные весы без гирь. Задача: определить аномальный мешок за минимальное количество взвешиваний.

Структура решения

Оптимальный алгоритм основан на принципе максимального извлечения информации из каждого измерения. Балансные весы дают три возможных исхода: левая чаша тяжелее, правая тяжелее, равновесие. Это позволяет делить пространство поиска не надвое, а натрое.

Семь мешков распределяются на три группы: три мешка, три мешка и один мешок. Первые две группы помещаются на весы.

Первое взвешивание

Три мешка на левой чаше, три на правой, один остаётся вне взвешивания.

Если весы показывают равновесие — аномальный мешок тот, что не участвовал во взвешивании. Задача решена за одно действие.

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

Одно взвешивание сократило область поиска с семи объектов до одного или трёх.

Второе взвешивание

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

Равновесие указывает на мешок, который не взвешивался. Перевес одной из чаш указывает на конкретный мешок на ней — с учётом информации из первого взвешивания.

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

Два взвешивания достаточно в большинстве случаев. Максимум требуется три взвешивания при определённых комбинациях результатов.

Математическая основа

Количество возможных комбинаций при n взвешиваниях равно 3^n. При двух взвешиваниях это 3² = 9 различимых ситуаций. Семь мешков укладываются в эту схему с запасом.

Для восьми или девяти мешков потребуется те же два взвешивания. Десять мешков потребуют третьего обязательного взвешивания, поскольку 3² = 9 < 10.

Это не произвольная конструкция, а следствие информационной ёмкости трёхвариантного измерения. Каждое взвешивание добавляет log₃(количество объектов) единиц информации, необходимой для идентификации.

Алгоритм против перебора

Последовательная проверка каждого мешка потребовала бы до шести взвешиваний. Линейная сложность O(n). Метод группового деления даёт логарифмическую сложность O(log₃ n).

Разница кажется незначительной для семи объектов. Но при масштабировании она становится критичной. Для 27 мешков перебор потребует до 26 взвешиваний, групповое деление — максимум три. Для 81 мешка — до 80 против четырёх.

Это фундаментальное различие между алгоритмами поиска. Одни растут пропорционально размеру задачи, другие — пропорционально логарифму размера.

Практическое применение принципа

Медицинская диагностика использует ту же логику. Врач не назначает все возможные анализы. Он выбирает те, что максимально разделяют множество возможных диагнозов. Положительный результат одного теста может исключить десятки заболеваний и оставить три-четыре для дальнейшей проверки.

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

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

Условие известности направления отклонения

Если заранее известно, что аномальные монеты тяжелее или легче, задача упрощается. Результат взвешивания даёт однозначный ответ: перевес в конкретную сторону указывает на конкретный мешок.

Без этой информации каждый результат допускает двойную интерпретацию. Левая чаша тяжелее может означать либо наличие на ней мешка с тяжёлыми монетами, либо наличие на правой чаше мешка с лёгкими.

Это требует отслеживания промежуточных результатов и построения более сложных логических цепочек. Но количество необходимых взвешиваний остаётся тем же — два-три максимум.

Информационная теория

С точки зрения теории информации, задача сводится к определению одного объекта из семи. Это требует log₂(7) ≈ 2,807 бит информации.

Каждое взвешивание на балансных весах даёт log₂(3) ≈ 1,585 бит информации (три равновероятных исхода).

Два взвешивания дают 2 × 1,585 = 3,17 бит, что превышает необходимые 2,807 бит. Теоретически достаточно для решения задачи.

Три взвешивания дают 4,755 бит, что позволяет различать до 3³ = 27 объектов.

Это объясняет, почему определённые количества объектов идеально укладываются в определённое число взвешиваний, а превышение даже на один объект требует дополнительного измерения.

Оптимизация в условиях ограничений

Ценность задачи не в её практической применимости к поиску фальшивых мешков. Её ценность — в демонстрации принципа оптимального использования ограниченных ресурсов.

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

Минимизация количества таких операций при гарантированном достижении результата — это задача, которая возникает постоянно в различных областях.

Масштабирование алгоритма

Для большего количества мешков схема сохраняется. Главное — поддерживать принцип деления на три примерно равные группы на каждом этапе.

При 12 мешках: 4-4-4. Первое взвешивание — две группы по 4, третья в стороне. Если равны — работаем с четвёркой, что не взвешивалась. Если не равны — с одной из двух групп по 4 на весах.

Второе взвешивание из четырёх мешков: 1-1-2 или 2-2-0 в зависимости от стратегии. И так далее до локализации конкретного мешка.

Количество необходимых взвешиваний для n мешков определяется как минимальное k, при котором 3^k ≥ n.

Дерево решений

Весь процесс можно представить в виде дерева, где каждый узел — это взвешивание, каждая ветвь — один из трёх возможных результатов, каждый лист — конкретный мешок.

Для семи мешков дерево имеет корень (первое взвешивание), три ветви из него (равно, лево тяжелее, право тяжелее), и от каждой ветви дальнейшее разветвление до листьев.

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

Завершение

Задача о семи мешках демонстрирует фундаментальный принцип эффективного поиска: деление пространства возможностей на максимальное количество групп при каждом измерении. Балансные весы позволяют делить натрое. Это даёт логарифмическую сложность алгоритма.

Два взвешивания достаточно для определения аномального мешка в большинстве случаев. Три взвешивания гарантируют решение для любой комбинации.

Принцип применим везде, где требуется локализовать проблему, найти отклонение или идентифицировать объект среди множества при ограниченном количестве проверок.

Об авторе