Балансовая головоломка

Головоломка о весах или головоломка о взвешивании — это логическая головоломка о балансировке предметов (часто монет) для определения того, какие из них имеют разное значение, путем использования весов ограниченное количество раз. Они отличаются от головоломок, в которых предметам присваивается вес, тем, что важна только относительная масса этих предметов.

Известный	Цель	Максимальное количество монет для $n$ взвешиваний	Количество взвешиваний для $c$ монет
Является ли целевая монета легче или тяжелее других	Определить монету	$3^{n}$	$\lceil \log _{3}(c)\rceil$
Целевая монета отличается от других	Определить монету	${\frac {3^{n}-1}{2}}$ ^[1]	$\lceil \log _{3}(2c+1)\rceil$
Целевая монета отличается от других, или все монеты одинаковы.	Определите, существует ли уникальная монета и легче она или тяжелее.	${\frac {3^{n}-1}{2}}-1$	$\lceil \log _{3}(2c+3)\rceil$

Например, при обнаружении разнородной монеты за три взвешивания (n = 3) максимальное количество монет, которое можно проанализировать, равно ⁠ 3 ³ − 1/2 = 13. Обратите внимание, что ⁠ при 3 весах и 13 монетах не всегда можно определить принадлежность последней монеты (тяжелее или легче остальных), а лишь то, что монета другая. В общем, по n весов можно определить идентичность монеты, если у вас есть ⁠ 3 ^н − 1/2 ⁠ — 1 или меньше монет. В случае n = 3 вы действительно можете определить идентичность другой монеты из 12 монет.

Задача девяти монет

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

Решение

Чтобы найти решение, сначала рассмотрим максимальное количество предметов, из которых можно найти более легкий всего за одно взвешивание. Максимально возможное количество — три. Чтобы найти более легкую, мы можем сравнить любые две монеты, оставив третью. Если две монеты весят одинаково, то более легкая монета должна быть одной из тех, которых нет на весах. В противном случае это тот, который указан на весах как более легкий.

Теперь представьте себе девять монет в трех стопках по три монеты в каждой. За один ход мы можем определить, какая из трех стопок легче (т.е. та, в которой лежит более светлая монета). Затем требуется всего лишь один ход, чтобы идентифицировать легкую монету из этой более легкой стопки. Итак, за два взвешивания мы сможем найти одну легкую монету из набора $3\times3=9$ .

В более широком смысле, потребуется всего три взвешивания, чтобы найти лишнюю легкую монету среди 27 монет, и четыре взвешивания, чтобы найти ее среди 81 монеты.

Задача двенадцати монет

Более сложная версия имеет двенадцать монет, одиннадцать из двенадцати из которых идентичны. Если один из них отличается, мы не знаем, тяжелее он или легче остальных. На этот раз весы можно использовать три раза, чтобы определить, существует ли уникальная монета, а если есть, то изолировать ее и определить ее вес относительно остальных. (Эта загадка и ее решение впервые появились в статье 1945 года. ^[2]) Задача имеет более простой вариант с тремя монетами за два взвешивания и более сложный вариант с 39 монетами за четыре взвешивания.

Решение

Эта проблема имеет более одного решения. Один из них легко масштабируется до большего количества монет, используя нумерацию по основанию три: маркировка каждой монеты разным количеством трех цифр по основанию три и позиционирование на n -й позиции, взвешивание всех монет, помеченных n- й цифрой. цифра, идентичная метке пластины (с тремя пластинами, по одной с каждой стороны шкалы, обозначенными 0 и 2, и одной за пределами шкалы, обозначенной 1). Другие пошаговые процедуры аналогичны следующим. Решить эту задачу не так просто, и второе и третье взвешивание зависят от того, что произошло ранее, хотя это не обязательно (см. ниже).

С каждой стороны кладут по четыре монеты. Есть две возможности:

1. Одна сторона тяжелее другой. В этом случае уберите три монеты с более тяжелой стороны, перенесите три монеты с более легкой стороны на более тяжелую и положите три монеты, которые не взвешивались в первый раз, на более легкую сторону. (Запомните, какие монеты какие.) Есть три возможности:

1.а) Та сторона, которая была тяжелее в первый раз, остается тяжелее. Это означает, что либо монета, которая осталась там, тяжелее, либо монета, которая осталась на более легкой стороне, легче. Сопоставление одной из них с одной из десяти других монет показывает, какая из них верна, и таким образом решается головоломка.

1.б) Та сторона, которая была тяжелее в первый раз, во второй раз станет легче. Это означает, что одна из трех монет, перешедших от более легкой стороны к более тяжелой, является легкой монетой. Для третьей попытки взвесьте две такие монеты друг против друга: если одна легче, то это уникальная монета; если они уравновесятся, третья монета будет легкой.

1.c) Обе стороны четные. Это означает, что одна из трех монет, удаленных с более тяжелой стороны, является тяжелой монетой. Для третьей попытки взвесьте две такие монеты друг против друга: если одна тяжелее, то это уникальная монета; если они уравновешиваются, третья монета будет тяжелой.

2. Обе стороны четные. В этом случае все восемь монет идентичны и их можно отложить. Возьмите четыре оставшиеся монеты и положите три на одну сторону весов. Поместите 3 из 8 одинаковых монет на другую сторону. Есть три возможности:

2.а) Три оставшиеся монеты светлее. В этом случае вы теперь знаете, что одна из этих трех монет — лишняя и что она легче. Возьмите две из этих трех монет и взвесьте их друг против друга. Если баланс наклоняется, то более легкая монета оказывается лишней. Если две монеты уравновешиваются, то третья монета, отсутствующая на балансе, является лишней и легче.

2.б) Три оставшиеся монеты тяжелее. В этом случае вы теперь знаете, что одна из этих трех монет является лишней и что она тяжелее. Возьмите две из этих трех монет и взвесьте их друг относительно друга. Если баланс наклоняется, то более тяжелая монета оказывается лишней. Если две монеты уравновешиваются, то третья монета, отсутствующая на балансе, является лишней и тяжелее.

2.c) Три оставшиеся монеты уравновешиваются. В этом случае вам просто нужно взвесить оставшуюся монету относительно любой из остальных 11 монет, и это скажет вам, тяжелее она, легче или такая же.

Вариации

Учитывая популяцию из 13 монет, в которой известно, что 1 из 13 отличается (массой) от остальных, легко определить, какая это монета, с помощью весов и 3 тестов следующим образом:

1) Разделите монеты на 2 группы по 4 монеты и третью группу с оставшимися 5 монетами.

2) Тест 1. Проверьте две группы по 4 монеты друг против друга:

а. Если монеты уравновешиваются, нечетная монета входит в группу из 5 и переходите к тесту 2а.

б. Нечетная монета находится среди совокупности из 8 монет. Действуйте так же, как и в задаче о 12 монетах.

3) Тест 2а, Тест 3 монет из группы из 5 монет против любых 3 монет из совокупности 8 монет:

а. Если 3 монеты уравновешиваются, то нечетная монета находится среди оставшейся совокупности из 2 монет. Проверьте одну из двух монет против любой другой монеты; если они сбалансированы, нечетная монета является последней непроверенной монетой, если они не сбалансированы, нечетная монета является текущей тестовой монетой.

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

С эталонной монетой

Если для справки имеется одна подлинная монета, то подозрительных монет может быть тринадцать. Пронумеруйте монеты от 1 до 13 и подлинный номер монеты 0 и выполните эти взвешивания в любом порядке:

0, 1, 4, 5, 6 против 7, 10, 11, 12, 13
0, 2, 4, 10, 11 против 5, 8, 9, 12, 13
0, 3, 8, 10, 12 против 6, 7, 9, 11, 13

Если весы вышли из равновесия только один раз, то это должна быть одна из монет 1, 2, 3, которые появляются только за одно взвешивание. Если баланса нет, то это должна быть одна из монет 10–13, которые появляются при всех взвешиваниях. Выбрать одну фальшивую монету, соответствующую каждому из 27 исходов, всегда возможно (13 монет, одна слишком тяжелая или слишком легкая, составляет 26 возможностей), за исключением случая, когда все взвешивания сбалансированы, и в этом случае фальшивой монеты нет (или ее вес равен правильный). Если из этих взвешиваний исключить монеты 0 и 13, это даст одно общее решение проблемы 12 монет.

Если две монеты являются фальшивыми, эта процедура, как правило, не выбирает ни одну из них, а выбирает подлинную монету. Например, если обе монеты 1 и 2 фальшивые, либо монета 4, либо 5 выбрана неправильно.

Без эталонной монеты

В упрощенном варианте этой головоломки нужно только найти фальшивую монету, но при этом не обязательно уметь определить ее вес относительно остальных. В этом случае очевидно, что любое решение, которое ранее в какой-то момент взвешивало каждую монету, может быть адаптировано для обработки одной дополнительной монеты. Эту монету никогда не кладут на весы, но если все взвешивания уравновешены, ее признают фальшивой. Лучшего сделать невозможно, поскольку любой монете, которую в какой-то момент кладут на весы и считают фальшивой, всегда можно будет присвоить вес относительно других.

Метод, который взвешивает одни и те же наборы монет независимо от результатов, позволяет либо

(среди 12 монет A–L) сделайте вывод, все ли они весят одинаково, или найдите лишнюю монету и скажите, легче она или тяжелее, или
(среди 13 монет A–M) найдите нечетную монету и с вероятностью 12/13 определите, легче она или тяжелее (для оставшейся вероятности 1/13 только то, что она другая).

Три возможных результата каждого взвешивания можно обозначить знаком «\», если левая сторона легче, «/», если правая сторона легче, и «–», если обе стороны имеют одинаковый вес. Символы взвешиваний перечислены последовательно. Например, «//–» означает, что правая сторона легче при первом и втором взвешивании, а при третьем взвешивании обе стороны весят одинаково. Три взвешивания дают следующие 3 ³ = 27 исходов. За исключением «–––», наборы разделены так, что каждый набор справа имеет «/», а набор слева — «\», и наоборот:

/// \\\

\// /\\
/\/ \/\
//\ \\/

\/– /\–
–\/ –/\
/–\ \–/

\\– //–
–\\ –//
\–\ /–/

/–– \––
–/– –\–
––/ ––\

–––

Поскольку каждое взвешивание дает значимый результат только тогда, когда количество монет в левой части равно количеству монет в правой части, мы игнорируем первую строку, чтобы в каждом столбце было одинаковое количество символов «\» и «/». (по четыре каждого). Строки помечены, порядок монет не имеет значения:

\// A light    /\\ A heavy
/\/ B light    \/\ B heavy
//\ C light    \\/ C heavy

\/– D light    /\– D heavy
–\/ E light    –/\ E heavy
/–\ F light    \–/ F heavy

\\– G light    //– G heavy
–\\ H light    –// H heavy
\–\ I light    /–/ I heavy

/–– J light    \–– J heavy
–/– K light    –\– K heavy
––/ L light    ––\ L heavy

––– M either lighter or heavier (13-coin case),
    or all coins weigh the same (12-coin case)

Используя приведенную выше схему результатов, можно определить состав монет для каждого взвешивания; например, набор «\/– D светлый» подразумевает, что монета D должна находиться на левой стороне при первом взвешивании (чтобы эта сторона была легче), на правой стороне при втором и неиспользованной при третьем взвешивании:

1st weighing:  left side: ADGI, right side: BCFJ
2nd weighing:  left side: BEGH, right side: ACDK
3rd weighing:  left side: CFHI, right side: ABEL

Затем результаты считываются с таблицы. Например, если правая сторона легче при первых двух взвешиваниях, а обе стороны весят одинаково при третьем, соответствующий код «//– G тяжелая» означает, что монета G является нечетной и тяжелее остальных. . ^[3]

Обобщения

Обобщение этой задачи описано у Чуднова. ^[4]

Позволять $\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]-куб в $\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} ^{+}$ характеризует типы объектов: стандартный тип, нестандартный тип (т.е. конфигурации типов) и не содержит информации об относительных весах нестандартных объектов.

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

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

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

Позволять $S(Z,{\mathcal {A}})$ быть набором всех $(Z,{\mathcal {A}})$ -синдромы и $W(s|{\mathcal {A}})\subseteq I$ быть набором ситуаций с одним и тем же синдромом $s$ ; то есть $W(s|{\mathcal {A}})=\{\mathrm {z} \in I^{m}|s(z|{\mathcal {A}})=s\}$ ; $W(s|Z;{\mathcal {A}})=W(s|{\mathcal {A}})\cap Z.$

Определение 2 . ПРАВИТЕЛЬСТВО ${\mathcal {A}}$ сказано: а) определить ситуации в наборе $Z$ если условие $|W(s|Z,{\mathcal {A}})|=1$ доволен всем $s\in S(Z{\mathcal {A}});$ б) определить типы предметов в наборе $Z$ если условие $|W^{+}(s|Z{\mathcal {A}})|=1$ доволен всем $s\in S(Z{\mathcal {A}}).$

Это доказано в ^[4] что для так называемых подходящих множеств $Z$ алгоритм идентификации типов идентифицирует также ситуации в $Z.$

В качестве примера идеальные динамические (двухкаскадные) алгоритмы с параметрами $n=11,m=5,t=2$ построены в ^[4] которые соответствуют параметрам идеального троичного кода Голея (кода Виртакаллио-Голея). При этом установлено, что статического ВА (т.е. весового кода) с такими же параметрами не существует.

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

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

Оригинальная головоломка о параллельных взвешиваниях

Элиран Сабаг придумал эту головоломку. Имеется N неразличимых монет, одна из которых фальшивая (неизвестно, тяжелее или легче подлинных монет, которые все весят одинаково). Есть две весы, которые можно использовать параллельно. Каждое взвешивание длится три минуты. Каково наибольшее количество монет N, для которых можно найти фальшивую монету за десять минут? ^[5]

Ссылки

^ Вайсштейн, Эрик В. «Взвешивание» . mathworld.Wolfram.com . Проверено 16 августа 2017 г.
^ Гроссман, Ховард (1945). Скрипта Математика XI .
^ «Математический форум — спросите доктора Математика» . mathforum.org . Архивировано из оригинала 12 июня 2002 г.
^ Jump up to: Перейти обратно: ^а ^б ^с Чуднов, Александр М. (2015). «Весовые алгоритмы классификации и идентификации ситуаций». Дискретная математика и приложения . 25 (2): 69–81. дои : 10.1515/dma-2015-0007 . S2CID 124796871 .
^ Хованова, Таня (2013). «Решение проблемы фальшивых монет и ее обобщение». arXiv : 1310.7268 [ math.HO ].

Внешние ссылки

[1] Вайсштейн, Эрик В. «Взвешивание» . mathworld.Wolfram.com . Проверено 16 августа 2017 г.

[2] Гроссман, Ховард (1945). Скрипта Математика XI .

[3] «Математический форум — спросите доктора Математика» . mathforum.org . Архивировано из оригинала 12 июня 2002 г.

[CH-WA-4] Jump up to: Перейти обратно: ^а ^б ^с Чуднов, Александр М. (2015). «Весовые алгоритмы классификации и идентификации ситуаций». Дискретная математика и приложения . 25 (2): 69–81. дои : 10.1515/dma-2015-0007 . S2CID 124796871 .

[5] Хованова, Таня (2013). «Решение проблемы фальшивых монет и ее обобщение». arXiv : 1310.7268 [ math.HO ].

[1]

[2]

[3]

[4]

[5]