Загадка баланса - Balance puzzle

Для Чемпионат мира по пазлам пазл с цифрами, см. Баланс (головоломка).

Анимация решения проблемы фальшивой монеты с участием десяти монет. В этом примере фальшивая монета легче других.

А головоломка баланса или же пазл для взвешивания это логическая головоломка о балансировке предметов - часто монет - чтобы определить, какие из них имеют другую ценность, с помощью весов баланса ограниченное количество раз. Они отличаются от головоломок, в которых каждому предмету присваивается вес, тем, что имеет значение только относительная масса этих предметов.

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

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

Проблема с девятью монетами

Решение загадки баланса для 9 монет за 2 взвешивания, где нечетная монета легче других - если нечетная монета тяжелее других, две верхние ветви в каждом решении по взвешиванию меняются местами

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

Решение

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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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

Вариации

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

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

2) Тест 1, протестируйте 2 группы по 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 выбраны неправильно.

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

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

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

1. (среди 12 монет A-L) сделайте вывод, все ли они весят одинаково, или найдите нечетную монету и скажите, легче она или тяжелее, или
2. (среди 13 монет A-M) найдите нечетную монету и для 12 из них скажите, легче она или тяжелее.

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

/// // /// /// //- /--/ -//- -/- //-- -//- /-//-- ---/- ----/ -----

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

// A легкий /  A тяжелый // B легкий / B тяжелый // C легкий  / C тяжелый / - D легкий / - D тяжелый- / E легкий - / E тяжелый / - F легкий - / F тяжелый  - G легкий // - G тяжелый-  H легкий - // H тяжелый- I легкий / - / I тяжелый / - J легкий - J тяжелый - / - K легкий - K тяжелый - / L легкий - L тяжелый --- M либо легче, либо тяжелее (футляр на 13 монет), либо все монеты одинаковы (футляр на 12 монет)

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

1-е взвешивание: слева: ADGI, справа: BCFJ 2-е взвешивание: слева: BEGH, справа: ACDK 3-е взвешивание: слева: CFHI, справа: ABEL

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

Обобщения

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

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

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

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

Определение 2. A WA ${displaystyle {mathcal {A}}}$ Говорят, что он: а) определяет ситуации в наборе ${displaystyle Z}$ если условие ${displaystyle |W(s|Z,{mathcal {A}})|=1}$ устраивает для всех ${displaystyle sin S(Z{mathcal {A}});}$б) определить типы объектов в наборе ${displaystyle Z}$ если условие ${displaystyle |W^{+}(s|Z{mathcal {A}})|=1}$ устраивает для всех ${displaystyle sin S(Z{mathcal {A}}).}$

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

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

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

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

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

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

В литературе

• Ниоба, главный герой Пирс Энтони с Роман Со спутанным мотком, должен решить вариант этой головоломки с двенадцатью монетами, чтобы найти своего сына в Ад: Сатана замаскировал сына, чтобы он выглядел идентично одиннадцати другим демонам, и он тяжелее или легче, в зависимости от того, проклят ли он лгать или может говорить правду. Решение в книге следует приведенному примеру 1.c.
• Беремиз, главный герой из Жулио Сезар де Мелло и Соуза книга Человек, который считал, встречает индийского торговца, который бросает ему вызов стандартной головоломкой баланса с восемью жемчужинами одинаковой формы (одна жемчужина немного легче остальных). Беремиз решает это, явно формулируя все переменные задачи, используя только два взвешивания.

На телевидении

• В серии "Свадебный мошенник" Cyberchase, группа главных героев должна найти более легкий ключ из восьми ключей (остальные семь имеют такой же вес), и они решают его субоптимально, с тремя весами, когда достаточно двух.
• В эпизоде ​​«Прощай, дело об убийстве с высоким уровнем интеллекта» Коломбо, Коломбо решает следующую загадку: https://www.mathsisfun.com/puzzles/weighing-10-bags-solution.html
• В эпизоде ​​«Капитан Перальта» Бруклин девять-девять, Холт представляет своей команде версию задачи о двенадцати монетах, в которой участвуют двенадцать человек и качели.

Рекомендации

1. Вайсштейн, Эрик В. «Взвешивание». mathworld.Wolfram.com. Получено 16 августа 2017.
2. Гроссман, Ховард (1945). Scripta Mathematica XI.
3. http://mathforum.org/library/drmath/view/55618.html
4. Чуднов, Александр М. (2015). «Весовые алгоритмы классификации и идентификации ситуаций». Дискретная математика и приложения. 25 (2): 69–81. Дои:10.1515 / dma-2015-0007. S2CID  124796871.
5. Хованова, Таня (2013). «Решение проблемы фальшивых монет и ее обобщение». arXiv:1310.7268 [math.HO ].

внешняя ссылка

• Игровой пример первой головоломки
• Игровой пример второй головоломки
• Весы с двумя чашами и общая проблема поддельных монет
• Программная реализация, которая решает проблему для произвольного количества элементов и измерений, написанных на Python.