Найди фальшивый камень с помощью весов, сделав как можно меньше взвешиваний.

Если речь про классическую задачу с 12 камнями (один фальшивый, неизвестно — легче он или тяжелее, есть только чашечные весы без гирь), то оптимум — 3 взвешивания. Ниже — полностью рабочее «дерево решений».

Обозначения: камни №1…№12.
Первое взвешивание (В1): 1,2,3,4 ↔ 5,6,7,8.

1) В1 в равновесии

Фальшивый среди 9–12.

В2: 9,10,11 ↔ 1,2,3 (а 1–3 точно настоящие).

• Если равновесие → фальшивый 12.
  В3: 12 ↔ 1 — покажет, легче он или тяжелее.

• Если левая чашка тяжелее → один из 9,10,11 тяжелее.
  В3: 9 ↔ 10.
  — Равны → тяжелый 11.
  — Не равны → тяжелее та сторона, где фальшивый.

• Если левая чашка легче → один из 9,10,11 легче.
  В3: 9 ↔ 10.
  — Равны → лёгкий 11.
  — Не равны → легче та сторона, где фальшивый.

2) В1: левая тяжелее (зеркальный случай «правая тяжелее» разбирается аналогично)

Тогда фальшивый — либо один из 1–4 (и он тяжелее), либо один из 5–8 (и он легче).

В2: 1,2,5 ↔ 3,6,9 (где 9 — заведомо настоящий, его не взвешивали в В1).

• Если В2 в равновесии → фальшивый среди 4 (тяжелее), 7 (легче), 8 (легче).
  В3: 7 ↔ 8.
  — Равны → тяжёлый 4.
  — Не равны → легче та сторона, где фальшивый (7 или 8).

• Если В2: левая тяжелее → кандидаты 1(тяжелее), 2(тяжелее), 6(легче).
  В3: 1 ↔ 2.
  — Равны → лёгкий 6.
  — Не равны → тяжелее та сторона и есть фальшивый (1 или 2).

• Если В2: правая тяжелее → кандидаты 3(тяжелее), 5(легче).
  В3: 3 ↔ 9.
  — Если 3 тяжелее → фальшивый 3 (тяжелее).
  — Иначе → лёгкий 5.

Почему 3 взвешивания — минимум

За одно взвешивание у чашечных весов 3 исхода: «лево тяжелее / право тяжелее / равновесие». За $k$ взвешиваний максимум $3^k$ различимых исходов. В задаче нужно определить не только номер камня (12 вариантов), но и его «знак» (легче/тяжелее), всего 24 возможности, но два состояния «все настоящие» не рассматриваются, поэтому классическая оценка показывает, что 12 камней — ровно предел для 3 взвешиваний. Алгоритм выше этот предел достигает.