Задачи на взвешивание монет¶

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

¶Постановка задачи

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

Возможны варианты:

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

¶Теоретический предел

Информационная граница определяется числом возможных исходов. Одно взвешивание даёт три исхода, k взвешиваний — 3^k исходов. Для задачи с N монетами и неизвестным направлением отклонения число возможных ответов равно 2N (каждая монета может быть легче или тяжелее). Следовательно, необходимое условие разрешимости: 2N ≤ 3^k, то есть N ≤ (3^k)/2. Для k=3 максимальное N равно 13 (поскольку 2·13 = 26 ≤ 27). Для задачи с известным направлением отклонения число ответов равно N, и предел составляет N ≤ 3^k (например, за 3 взвешивания можно найти одну лёгкую монету среди 27).

Эти границы являются необходимыми, но не всегда достаточными: для N=13 с неизвестным направлением задача разрешима за 3 взвешивания, однако требует аккуратного построения схемы.

¶Методы решения

¶Метод троичного кодирования

Каждому взвешиванию сопоставляется символ: «<» (левая легче), «>» (левая тяжелее), «=» (равновесие). Последовательность исходов образует троичный код. Если направление отклонения неизвестно, каждой монете сопоставляются два кода (для случая «легче» и «тяжелее»), причём они должны быть взаимно обратными (замена «<» на «>» и наоборот). Схема строится так, чтобы коды всех 2N возможных ответов были различны.

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

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

¶Алгоритм для 12 монет

Классическая задача о 12 монетах (определить фальшивую за 3 взвешивания, направление неизвестно) решается следующим образом. Первое взвешивание: 1,2,3,4 против 5,6,7,8.

Если равновесие: фальшивая среди 9–12. Второе взвешивание: 1,2,3 (настоящие) против 9,10,11. Если равновесие — фальшивая 12, третьим взвешиванием сравниваем её с настоящей. Если перевес — фальшивая среди 9,10,11, причём известно направление; третьим взвешиванием сравниваем две из них.
Если первое взвешивание показало перевес, например, левая чаша тяжелее: фальшивая либо среди 1–4 (тяжелее), либо среди 5–8 (легче). Второе взвешивание: 1,2,5 против 3,6,9 (9 — настоящая). Анализ исходов позволяет сузить круг до двух монет, после чего третье взвешивание даёт однозначный ответ.

¶Обобщение на 13 монет

При N=13 за 3 взвешивания задача также разрешима, но требует более сложной схемы, в которой одно из взвешиваний содержит неравные группы монет. Первое взвешивание: 1,2,3,4 против 5,6,7,8. При равновесии фальшивая среди 9–13, и для оставшихся двух взвешиваний используется более изощрённая комбинация, учитывающая возможность как лёгкой, так и тяжёлой монеты.

¶Применение и значение

Задачи на взвешивание монет широко используются:

в олимпиадной математике и логике как тренировка комбинаторного мышления;
в теории информации для иллюстрации понятия энтропии и информационной ёмкости эксперимента;
в教学中 (педагогике) для развития алгоритмического мышления у школьников;
в теоретической информатике при изучении задач поиска дефектов (fault detection) и построения оптимальных стратегий тестирования.

¶Вариации задач

Помимо классической постановки существуют многочисленные модификации:

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

¶Историческая справка

Задачи о фальшивых монетах известны с античности, однако систематическое исследование началось в XX веке. Значительный вклад в теорию внёс американский математик и информатик Клод Шеннон, чьи работы по теории информации позволили формализовать пределы разрешимости. Классическая задача о 12 монетах стала широко известна благодаря публикациям в сборниках головоломок (например, у Генри Дьюдени и Мартина Гарднера).

¶См. также

¶Источники

Гарднер М. «Математические головоломки и развлечения».
Дьюдени Г. Э. «Кентерберийские головоломки».
Шеннон К. «Работы по теории информации и кибернетике».
Фомин С. В. «Системы счисления» (раздел о троичном кодировании).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →