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

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

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

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

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

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

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

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

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

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

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

Задача отыскания одной фальшивой монеты, вес которой может быть больше или меньше веса правильной монеты

Из нетривиальных задач на взвешивание изучена и хорошо известна задача, в которой требуется определить, имеется ли среди 12 монет фальшивая и, если имеется, найти ее и определить ее относительный вес. Эта задача и ее решение впервые были опубликованы в 1945 Р. Л. Гудстейном в «The Mathematical Gazette» (см. статью ). В данной задаче существует статический алгоритм (т. е. алгоритм, в котором взвешивания определены заранее и не зависят от результатов предыдущих взвешиваний), обеспечивающий нахождение фальшивой монеты за 3 взвешивания. Этот алгоритм можно представить следующей таблицей:

0 0 1 0 0 2 2 2 1 1 1 2

0 1 0 2 2 2 1 0 0 1 2 1

1 0 0 2 1 0 0 2 2 2 1 1

В таблице номера столбцов соответствуют номерам монет, а строки определяют взвешивания: 0 – монета не участвует во взвешивании, 1 – кладется на первую чашу, 2 – кладется на вторую чашу. В результате трех взвешиваний определяется так называемый синдром, т. е. тройка чисел, которая однозначно указывают на номер фальшивой монеты. Этот номер равен номеру столбца с соответствующим синдромом. Например, если синдром равен (2,2,0), то фальшивой является монета с номером 6 и она тяжелее эталонных монет.

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

Достаточно общую картину о числе монет n, из которых можно найти одну фальшивую за m взвешиваний, можно составить из . Пусть из данного количества монет можно найти фальшивую за m взвешиваний. Тогда максимально возможное количество монет равно:

• если относительный вес фальшивой монеты известен заранее – $3^{m}$ (независимо от наличия запаса настоящих монет);

• если относительный вес не известен и его требуется узнать:

– при отсутствии запаса настоящих монет – $(3^{m}-3)/2$ ;

– при наличии – $(3^{m}-1)/2$ ,

• если не требуется узнать относительный вес:

– при отсутствии запаса настоящих монет – $(3^{m}-1)/2$;

– при наличии – $(3^{m}+1)/2$.

Обобщения

Обобщенное описание задач такого типа приведено в .

Пусть $\mathbb {R} ^{n}$ -- $n$-мерное евклидово пространство, $[\mathrm {e} ^{1},\mathrm {e} ^{2}]$ -- скалярное произведение векторов $\mathrm {e} ^{1}$ и $\mathrm {e} ^{2}$ из $\mathbb {R} ^{n},$ Для элементов $\mathrm {e} =(e_{1},\dots ,e_{n})\in \mathbb {R} ^{n}$ и подмножеств $E=\{\mathrm {e} ^{j}\}\subseteq \mathbb {R} ^{n},$ используются операции $(\cdot )^{*}$ и $(\cdot )^{+}$ результаты применения которых определяются соотношениями $\mathrm {e} ^{*}=(sign(e_{i}))_{i}$ ; $E^{*}=\{(\mathrm {e} ^{j})^{*}\}$, $\mathrm {e} ^{+}=(|sign(e_{i})|)_{i}$, $E^{+}=\{(\mathrm {e} ^{j})^{+}\}.$ Символом $I^{n}$ будем обозначать дискретный [−1; 1]-cube в $\mathbb {R} ^{n}$; т. е. множество всех последовательностей длины $n$над алфавитом $I=\{-1,0,1\}$. Множество $I_{t}^{n}=\{\mathrm {x} \in I^{n}|w(\mathrm {x} )\leq t\}\subseteq I^{n}$ представляет собой дискретный шар радиуса $t$ (в метрика Хэмминга $w()$ ) с центром в точке $\mathrm {0} .$ Пусть имеются $n$ объектов, относительные веса которых задаются вектором $\mathrm {x} =(x_{1},\dots ,x_{n})\in I^{n},$ определяющим конфигурацию весов множества объектов: $i$-й объект имеет стандартный вес, если $x_{i}=0;$ вес $i$-го объекта больше (меньше) на постоянную (неизвестную) величину, если $x_{i}=1$ (соответственно, $x_{i}=-1$). Вектор $\mathrm {x} ^{+}$ характеризует типы объектов: стандартный, нестандартный (т. е. конфигурацию типов), и не содержит информации об относительных весах нестандартных объектов.

Взвешивание (проверка) задается вектором ${\textbf {h}}\in I^{n},$ при этом результат взвешивания для ситуации ${\textbf {x}}\in I^{n}$ равен $s({\textbf {x}},{\textbf {h}})=sign([{\textbf {x}},{\textbf {h}}]).$ Взвешивание, определенное вектором ${\textbf {h}}=(h_{1},\dots ,h_{n}),$ имеет следующую интерпретацию: при данной проверке $i$ -й объект участвует во взвешивании, если $h_{i}\neq 0;$ он кладется на левую чашку весов, если $h_{i}<0$ и на правую -- если $h_{i}>0.$ При каждом взвешивании ${\textbf {h}}$ на обеих чашках должно быть одинаковое число объектов, недостающее на какой-либо чашке число объектов пополняется эталонными объектами, число которых равно $r({\textbf {h}})=[{\textbf {h}},{\textbf {1}}].$ Результат взвешивания $s({\textbf {x}},{\textbf {h}})$ описывает случаи: при $s({\textbf {x}},{\textbf {h}})=0$ -- равновесие, при $s({\textbf {x}},{\textbf {h}})=-1$ -- левая чашка перевешивает, при $s({\textbf {x}},{\textbf {h}})=1$ -- правая чашка перевешивает. Взвешивание, не использующее дополнительных эталонных объектов ( $r({\textbf {h}})=0$ ), называется центрированным. Неполнота исходной информации относительно распределения весов рассматриваемой группы объектов характеризуется множеством допустимых распределений весов объектов $Z\subseteq I^{n},$ которое также называется множеством допустимых ситуаций, элементы ${\textbf {z}}\in Z$ называются допустимыми ситуациями.

Каждое взвешивание ${\textbf {h}}$ определяет разбиение множества $I^{n}$ плоскостью $[{\textbf {x}},{\textbf {h}}]=0$ на три части $W(s|I^{n},{\textbf {h}})=\{{\textbf {x}}\in I^{n}|s({\textbf {x}},{\textbf {h}})=s\},s\in I,$ и соответствующее разбиение множества $Z=W(0|Z,{\textbf {h}})+W(1|Z,{\textbf {h}})+W(-1|Z,{\textbf {h}}),$ где $W(s|Z,{\textbf {h}})=W(s|I^{n},{\textbf {h}})\cap Z.$ С учетом этого будем говорить, что взвешивание ${\textbf {h}}$ классифицирует элементы ${\textbf {z}}\in Z$ по типам, соответствующим подмножествам $W(s|Z,{\textbf {h}});$ при этом величина $d(Z,{\textbf {h}})=\max _{s\in I}|W(s|Z,{\textbf {h}})|$ называется диаметром классификации множества $Z$ взвешиванием ${\textbf {h}}.$

Определение 1. Алгоритм взвешивания ${\mathcal {A}}$ длины $m$ -- это последовательность ${\mathcal {A}}=\langle \mathrm {A} _{1},\dots ,\mathrm {A} _{m}\rangle$ , где $\mathrm {A} _{j}:I^{j-1}\to I^{n}$ -- функция, определяющая проверку ${\textbf {h}}^{j}=\mathrm {A} _{j}({\textbf {s}}^{j-1}),$ ${\textbf {h}}^{j}\in I^{n},$ на каждом $j$ -м $,j=1,2,\dots ,m,$ шаге алгоритма по результатам взвешиваний на предыдущих шагах ${\textbf {s}}^{j-1}=(s_{1},\dots ,s_{j-1})\in I^{j-1}$ $({\textbf {h}}^{1}=\mathrm {A} _{1}()$ -- заданная исходная проверка).

Пусть $S(Z{\mathcal {A}})$ -- множество всех $(Z,{\mathcal {A}})$ -синдромов, $W({\textbf {s}}|{\mathcal {A}})\subseteq I^{n}$ -- множество ситуаций, имеющих одинаковый синдром ${\textbf {s}},$ т. е. $W({\textbf {s}}|{\mathcal {A}})=\{{\textbf {z}}\in I^{n}|{\textbf {s}}({\textbf {z}}|{\mathcal {A}})={\textbf {s}}\};$ $W({\textbf {s}}|Z,{\mathcal {A}})=W({\textbf {s}}|{\mathcal {A}})\cap Z.$

Определение 2. АВ ${\mathcal {A}}$ называется

a) идентифицирующим ситуации в множестве $Z$ , если для всех ${{\textbf {s}}\in S(Z,{\mathcal {A}})}$ выполняется условие $|W({\textbf {s}}|Z,{\mathcal {A}})|=1;$

b) идентифицирующим типы объектов в множестве $Z$ , если для всех ${\textbf {s}}\in S(Z,{\mathcal {A}})$ выполняется условие $|W^{+}({\textbf {s}}|Z,{\mathcal {A}})|=1.$

В доказано, что для установленного класса множеств $Z$ (называемых подходящими) алгоритм, идентифицирующий типы объектов, идентифицирует также ситуации в $Z$.

В качестве примера построены динамические (двухкаскадные) алгоритмы взвешивания с параметрами $n$ = 11, $m$= 5, $t$= 2, которые соответствуют параметрам совершенного код Голея (Virtakallio-Golay code).

Каждый из построенных алгоритмов за 5 взвешиваний находит из 11 тестируемых монет до двух фальшивых, веса которых могут быть больше или меньше веса настоящей монеты на фиксированную величину. В этом случае область неопределенности содержит $1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5}$ ситуаций, т. е. построенный АВ лежит на верхней граница Хэмминга и в этом смысле является совершенным (см. троичный код Голея). В то же время установлено, что статического АВ (кода взвешивания) с параметрами $n$ = 11, $m$= 5, $t$= 2 не существует.

К настоящему времени неизвестно, существуют ли другие совершенные АВ, идентифицирующие ситуации в $I_{t}^{n}$ при каких-либо значениях $t$. Более того, не известно, существуют ли при некотором $t>2$ решения уравнения $\sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m},$ соответствующего граница Хэмминга для троичных кодов, что, очевидно, является необходимым для существования совершенного АВ. Известно лишь, что при $t=1$ совершенных АВ не существует, а при $t=2$ указанное уравнение имеет единственное нетривиальное решение, определяющее параметры $n,m,t$ построенного совершенного АВ.

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

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

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

К. Кноп придумал такую задачу. Мы имеем n монет, одна из которых фальшивая (не известно большего или меньшего веса, чем настоящие монеты, которые имеют одинаковый вес). Имеется 2 рычажных весов, которые могут использоваться параллельно. Каждое взвешивание занимает минуту времени. Каково максимальное число монет n, среди которых можно найти фальшивую монету за 5 минут?