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

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

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

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

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

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

Из нетривиальных задач на взвешивание изучена и хорошо известна задача, в которой требуется определить, имеется ли среди 12 монет фальшивая и, если имеется, найти ее и определить ее относительный вес. Эта задача и ее решение впервые были опубликованы в 1945 Р. Л. Гудстейном в «The Mathematical Gazette» (см. статью [2]). В данной задаче существует статический алгоритм (т. е. алгоритм, в котором взвешивания определены заранее и не зависят от результатов предыдущих взвешиваний), обеспечивающий нахождение фальшивой монеты за 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 взвешиваний, можно составить из [3]. Пусть из данного количества монет можно найти фальшивую за m взвешиваний. Тогда максимально возможное количество монет равно:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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