Задачи на взвешивание

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

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

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

При решении задач на взвешивание часто совершается типичная ошибка: требуется определить минимальное количество взвешиваний. При решении строится алгоритм, который, позволяет решить задачу за $N$ шагов. При этом $N$ действительно является верным ответом на вопрос «каково минимальное количество взвешиваний», но этот факт в решении не доказан. Иногда эта ошибка допускается и самими составителями задач.

Анализ с точки зрения теории информации

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

• перевесила левая чашка
• перевесила правая чашка
• чашки находятся в равновесии

Таким образом, единственное взвешивание сообщает нам один разряд в троичной системе счисления, а $N$ взвешиваний позволяют разделить не более чем $3^N$ различных ситуаций. Особенно это соображение полезно при доказательстве минимальности необходимого количества взвешиваний и при доказательстве невозможности определить некий факт за данное количество взвешиваний (в последнем случае обычно требуется комбинаторный анализ пространства возможных ответов).

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

Знания о системах счислений не являются, вообще говоря, необходимыми; достаточно тривиального комбинаторного соображения типа «набор длины $N$, в каждом из которых $m$ вариантов, даёт $N^m$ комбинаций».

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

«Нестандартные» задачи на взвешивание

Иногда встречаются «нестандартные» задачи на взвешивание, например:

• в них фигурируют весы, непосредственно показывающие вес
• в них фигурируют рычажные весы с циферблатом, показывающим разность веса грузов на чашах
• в них фигурирует безмен
• в них фигурируют неравноплечие весы