B3 Взвешивания и адаптивные измерения

Идея метода: задачи на взвешивания — это задачи об оптимальном алгоритме поиска «нестандартного» объекта (фальшивой монеты, более тяжёлого шара) с помощью минимального числа сравнений. Метод состоит в том, чтобы строить адаптивные стратегии: каждое следующее взвешивание зависит от результата предыдущего, а не задаётся заранее.

Почему «адаптивный»? Потому что только адаптивная стратегия оптимальна. Если взвешивать по заранее заданной схеме, ты не используешь информацию, полученную из предыдущих взвешиваний. Каждое взвешивание на чашечных весах даёт один из трёх исходов: левое тяжелее, правое тяжелее, равновесие. Это означает, что одним взвешиванием можно различить не более $3$ ситуаций, двумя — $9$, $k$ взвешиваниями — не более $3^k$.

Интуиция: каждый результат взвешивания — это «письмо» от монет. Ты задаёшь «вопрос» (как распределить монеты по чашам), монеты «отвечают» одним из трёх вариантов. Оптимальная стратегия — задавать вопросы так, чтобы каждый ответ максимально сужал пространство возможностей.

Основной принцип: $k$ взвешиваний на чашечных весах позволяют найти одну фальшивую монету (с известным отклонением) среди не более чем $3^k$ монет.

• Информационная нижняя оценка: если возможны $N$ ситуаций и каждое взвешивание имеет 3 исхода, то минимальное число взвешиваний не менее $\lceil \log_3 N \rceil$. Условие: чашечные весы. Когда использовать: для доказательства нижней оценки оптимума.
• Основная теорема взвешиваний: одна фальшивая монета среди $n$, если известно, что она тяжелее (или легче) нормальной, находится за $\lceil \log_3 n \rceil$ взвешиваний. Условие: фальшивая монета отличается в известном направлении. Когда использовать: задачи с известным типом отклонения.
• Нахождение одной фальшивой монеты без знания направления отклонения: среди $n \leq \frac{3^k - 3}{2}$ монет за $k$ взвешиваний, если $n \geq 2$. Для $k=3$: не более $12$ монет. Когда использовать: «классическая» задача с 12 монетами.
• Алгоритм деления на три: при каждом взвешивании разбить подозреваемых поровну на три группы, положить две из них на чаши. Результат указывает на «виновную» группу. Когда использовать: монета тяжелее/легче нормальной, направление известно.

• Делить подозреваемых на три равные части при каждом взвешивании (не на две!).
• Отслеживать «статус» каждой монеты: подозреваемая тяжёлая (Т), подозреваемая лёгкая (Л), заведомо нормальная (Н).
• Использовать нормальные монеты как «контрольные» — класть на чашу заведомо нормальные, чтобы получить дополнительную информацию.
• При задаче «найти и определить тип отклонения» — в первом взвешивании получить информацию о направлении.
• Строить дерево решений: каждый узел — взвешивание, три ветки — три исхода, листья — результат.
• Проверять нижнюю оценку: если нужно различить $N$ ситуаций, минимум $\lceil \log_3 N \rceil$ взвешиваний — и убедиться, что стратегия этого достигает.

Поверхностные признаки (что буквально написано):
- «Чашечные весы», «взвешивание», «найдите фальшивую монету».
- «За минимальное число взвешиваний», «докажите, что $k$ взвешиваний достаточно».
- «Все монеты одинаковы, кроме одной».

Структурные признаки (форма выражения, объекты):
- Небольшое число объектов ($n \leq 100$), один из которых «выделен» (тяжелее, легче, испорчен).
- Измерительный прибор даёт один из трёх ответов (или один из двух для динамометра).
- Задача об оптимальном числе экспериментов.

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

Задача 1. Среди 9 монет одна фальшивая — более тяжёлая. Найдите её за 2 взвешивания.

Источник: тренировочная (классическая задача о взвешиваниях, ВсОШ 7–8 класс).

Как думать (рассуждение ученика$):
1. $Что я вижу?$ 9$ монет, одна тяжелее. Информационная оценка: $3^2 = 9$ → нижняя граница 2 взвешивания. Значит, 2 взвешивания должны быть достаточны.$2. *$Триггер: одна фальшивая (тяжелее), чашечные весы → делить на 3 группы.$3. *$Первый ход: разбью 9 монет на три тройки: {1,2,3}, {4,5,6}, {7,8,9}. Взвешиваю {1,2,3} против ${4,5,6}.
4. $Три исхода:$ ($а) левая тяжелее → фальшивая в {1,2,3}; (б) правая тяжелее → в {4,5,6}; (в) равновесие → в {7,8,9}.

Решение:$
$Взвешивание $1:$ кладу монеты 1,2,3 на левую чашу и 4,5,6 — на правую.
- Если левая тяжелее: фальшивая в {1,2,3}.
- Если правая тяжелее: фальшивая в {4,5,6}.
- Если равновесие: фальшивая в ${7,8,9}.

$Взвешивание $2:$ из определённой тройки, например {1,2,3}: кладу монету 1 на левую, монету 2 на правую.
- Левая тяжелее → фальшивая монета 1.
- Правая тяжелее → фальшивая монета 2.
- Равновесие → фальшивая монета 3.

Ответ: фальшивая монета найдена за 2 взвешивания.

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

Задача 2. Среди 12 монет одна фальшивая — неизвестно, тяжелее или легче. За 3 взвешивания найдите её и определите, тяжелее она или легче.

Источник: классическая олимпиадная задача (встречается на ВсОШ и Турнире городов).

Как думать (рассуждение ученика$):
1. $Что я вижу?$ 12$ монет, направление неизвестно. Число ситуаций: $12 \times 2 = 24$ (фальшивая монета + тип). Нижняя оценка: $3^3 = 27 > 24$ → 3 взвешивания возможно достаточны.$2. *$Ключевая трудность: теперь каждая монета «подозревается» в двух направлениях.$3. *$Стратегия: взвешивание 1 — 4 против 4, 4 в стороне. Три исхода разделяют 24 ситуации примерно на 8+8+8.

Решение (схема$):
$Взвешивание $1:$ монеты {1,2,3,4} против {5,6,7,8}; монеты {9,10,11,12} в стороне.
- Равновесие → фальшивая в {9,10,11,12}; используем 2 взвешивания для поиска среди 4 с одним известным направлением (нет — снова неизвестно). Далее применяем стандартную схему для 4 монет за 2 взвешивания.
- Левая тяжелее → {1,2,3,4} подозреваются как тяжёлые, {5,6,7,8} — как лёгкие.
Взвешивание $2:* {1,2,5}$ против {3,6,9} (9 — нормальная). Три исхода снова делят подозреваемых на три группы.
Взвешивание $3:*$ окончательно определяем фальшивую.

(Полная схема занимает дерево решений с 27 листьями; здесь показана структура рассуждения.)

Ответ: за 3 взвешивания фальшивая монета находится и её тип определяется.

Что в этой задаче было главным: при неизвестном направлении нужно отслеживать статус каждой монеты (Т/Л/Н) и строить взвешивания, разбивающие множество статусов на три равные части.

• Ошибка: делить монеты на две части, а не на три → Тогда каждое взвешивание даёт только 1 бит информации вместо $\log_2 3 \approx 1{,}58$ бит → стратегия неоптимальна. → Как избежать: всегда делить подозреваемых на три части и класть две из них на чаши.
• Ошибка: не учитывать нормальные монеты → При неизвестном направлении нормальные монеты — ценный ресурс для получения дополнительной информации. → Как избежать: явно отмечай статус Т/Л/Н для каждой монеты.
• Ошибка: путать «за $k$ взвешиваний найти» и «$k$ взвешиваний всегда достаточно» → «Иногда нахожу за 1, иногда за 2» не означает «всегда за 2». → Как избежать: стратегия должна гарантировать нахождение при любом раскладе.
• Ошибка: построить неадаптивный алгоритм → Заранее фиксировать план всех взвешиваний, не учитывая результаты предыдущих. → Как избежать: каждый следующий шаг зависит от результата предыдущего.
• Ошибка: нижняя оценка = ответ → $\lceil \log_3 N \rceil$ — это лишь нижняя граница; нужно ещё предъявить стратегию, которая её достигает. → Как избежать: информационную оценку дополни явным алгоритмом.