Как гарантированно найти лёгкую фальшивую монету среди 8 за минимальное число взвешиваний на чашечных весах?

Дано 8 монет. Одна из них фальшивая. Фальшивая монета весит меньше, чем остальные. Также есть весы, которые представлены в виде двух чаш, как такие весы правосудия. Вопрос: за какое минимальное количество взвешиваний можно гарантированно определить, какая монета фальшива?

1 взвешивание — достаточно, так как фальшивая легче

2 взвешивания — достаточно при разбиении 3+3+2

3 взвешивания — минимум, потому что 8 монет «слишком много» для двух

4 взвешивания — минимум, иначе нельзя гарантировать результат

Теория: как определить минимум взвешиваний

Каждое взвешивание на чашечных весах даёт 3 возможных результата, поэтому за n взвешиваний можно различить не более чем 3^n «веток» в дереве решений.

Если заранее известно, что фальшивая монета легче, то максимум монет, среди которых можно найти одну лёгкую за n взвешиваний, равен 3^n, а минимальное число взвешиваний для c монет выражается как ceil(log3(c)).

Для 8 монет: ceil(log3(8)) = 2, поскольку 3^1 = 3 < 8 и 3^2 = 9 ≥ 8, значит 1 взвешивания недостаточно, а 2 теоретически достаточно и (важно) достижимо конкретной стратегией.

Если в условии не сказано, что фальшивая монета легче, и допускается «легче или тяжелее», количество гипотез становится больше (как минимум в 2 раза), и нижняя граница по взвешиваниям меняется.

Пошаговая стратегия 3+3+2 (2 взвешивания)

Обозначения: монеты 1..8, а операция weigh(A, B) означает взвесить набор A против набора B.

Шаг 1 (первое взвешивание): взвесить 1,2,3 против 4,5,6.

Возможны 3 случая:

Равновесие: значит монеты 1..6 настоящие, фальшивая среди 7,8, тогда во 2-м взвешивании необходимо взвесить 7 против 8 и более лёгкая — фальшивая.
Левая чаша легче (то есть 1,2,3 легче 4,5,6): фальшивая среди 1,2,3, во 2-м взвешивании необходимо взвесить 1 против 2; если равны — фальшивая 3, иначе более лёгкая из (1,2) — фальшивая.
Правая чаша легче: аналогично, фальшивая среди 4,5,6, во 2-м взвешивании необходимо взвесить 4 против 5; если равны — фальшивая 6, иначе более лёгкая из (4,5) — фальшивая.

Наглядная схема-дерево:

Взвешивание 1: (1,2,3)  vs  (4,5,6)
  ├─ равно        → Взвешивание 2: 7 vs 8 → легче = фальшивая
  ├─ левое легче  → Взвешивание 2: 1 vs 2
  │     ├─ равно      → 3 фальшивая
  │     └─ не равно   → легче из (1,2) фальшивая
  └─ правое легче → Взвешивание 2: 4 vs 5
        ├─ равно      → 6 фальшивая
        └─ не равно   → легче из (4,5) фальшивая

Взвешивания как дерево решений

Логика решения совпадает с «деревом решений» из разработки: каждый узел (взвешивание) даёт 3 ветви (меньше/больше/равно), а цель — чтобы у каждого листа оставался ровно 1 кандидат.

Разбиение 3+3+2 работает потому, что первое взвешивание либо сразу сужает поиск до 2 монет (случай равновесия), либо до 3 монет (случай перекоса), а 2-е взвешивание умеет однозначно решать и задачу из 2 монет, и задачу из 3 монет.

Псевдокод (как для алгоритмической задачи)

Ниже показан «алгоритм», близкий к тому, как подобное решение оформляется в задачах по программированию.

// weigh(A, B) возвращает:
//  0  если равны
// -1  если A легче (левая чаша легче правой)
//  1  если B легче
function findFakeCoin(coins[1..8]):
  r1 = weigh([1,2,3], [4,5,6])

  if r1 == 0:
    // фальшивая среди 7 и 8
    r2 = weigh([7], [8])
    if r2 == -1: return 7
    else: return 8

  if r1 == -1:
    // фальшивая среди 1,2,3
    r2 = weigh([1], [2])
    if r2 == 0: return 3
    if r2 == -1: return 1
    else: return 2

  // r1 == 1
  // фальшивая среди 4,5,6
  r2 = weigh([4], [5])
  if r2 == 0: return 6
  if r2 == -1: return 4
  else: return 5

Таблица соответствий для 2-го взвешивания в «группе из трёх»:

Результат взвешивания X vs Y	Какая фальшивая (если фальшивая легче)
равно	третья монета Z
X легче	X
Y легче	Y

В итоге: минимально требуется 2 взвешивания; стратегия 3+3+2 гарантированно находит фальшивую лёгкую монету; невозможность решения за 1 взвешивание объясняется тем, что одно взвешивание даёт лишь 3 исхода при 8 возможных кандидатах.