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

Итак, как найти одну фальшивую монету среди нескольких, сравнивая вес различных наборов монет и используя наименьшее возможное количество сравнений?

Для начала проведём анализ проблемы.

У нас есть набор из N монет, и среди них ничем внешне не отличающаяся от подлинных монет фальшивка. Подлинные монеты одинаковы по весу, а фальшивые имеют другой вес. У нас есть весы, позволяющие сравнивать вес двух любых наборов монет из общего количества. Под «любыми двумя наборами» подразумеваем два непересекающихся набора без общих элементов, поскольку монета не может находиться на обеих чашках одновременно. Но помимо того, что невозможно выполнить такое измерение, вклад общих монет в каждый набор аннулируется, поэтому даже в теории нет никакого смысла в рассмотрении пересекающихся наборов.

Далее сосредоточимся на такой версии головоломки, когда точно известно, что во всём наборе есть только одна фальшивая и (N - 1) подлинных монет. Тогда возможны четыре варианта:

1. Известно, что фальшивая монета определённо легче настоящей.

2. Известно, что фальшивая монета определённо тяжелее настоящей.

3. Неизвестно, легче или тяжелее фальшивая монета, но мы знаем, что у неё точно другой вес. То есть нужно найти фальшивую монету, но легче она или тяжелее нам по барабану.

4. Изначально неизвестно, легче или тяжелее фальшивая монета, но, помимо этого в конечном итоге нужно точно знать, легче она или тяжелее.

Первый и второй варианты, по сути, одинаковы. Если решим первый с помощью серии измерений, то второй решается аналогично, только при этом нужно поменять все упоминания «легче» на «тяжелее».

Первый вариант решить довольно легко.

Если N = 1, то эта единственная монета должна быть фальшивой, поэтому мы нашли фальшивку без взвешивания.

Если N = 2, сравниваем две монеты, и более лёгкая монета является фальшивой.

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

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

Как именно нам следует разделить монеты? Если N делится на три, делим монеты на три равные части. Если после деления остаётся одна монета, мы кладём её в третий набор. Если остаётся две, то делим остаток между двух первых наборов. Итак, 9 → (3, 3, 3), 10 → (3, 3, 4), 11 → (4, 4, 3) и т. д.

Каждое сравнение уменьшает размер набора, который должен содержать подделку. Если бы мы начали с N = 3^P монет, каждое сравнение уменьшало бы набор в три раза каждый раз, так что после P сравнений мы бы точно определили её местоположение. В целом, количество сравнений, гарантирующее обнаружение подделки, будет таким наименьшим значением P, что 3^P ≥ N. Так, для десяти монет, которые мы разделили на два набора по три и один набор из четырёх монет, нам может повезти, и подделка окажется в одном из наборов по три монеты. Затем окончательно решим задачу всего одним дополнительным сравнением, но если подделка находится в наборе из четырёх монет, нам может потребоваться ещё два сравнения, что в общей сложности составит три сравнения.

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

А как насчёт третьего варианта, когда у нас нет никаких априорных знаний о том, тяжелее или легче фальшивая монета? Если N = 1, то эта единственная монета и есть фальшивка, но если N = 2, то невозможно сказать, какая из двух монет фальшивая — тяжёлая или лёгкая. В этом случае задача не имеет решения. Поэтому на самом деле о какой-либо стратегии решения задачи имеет смысл говорить только для N ≥ 3.

При N = 3 невозможно быть уверенным в обнаружении подделки всего за одно взвешивание. Мы можем сравнить только две монеты, и если они одинаковы, то это однозначно говорит о том, что третья монета фальшивая. Но если сравниваемые монеты имеют разный вес, нельзя точно узнать, какая из них поддельная. То есть такая ситуация аналогична, что и при N = 2. Единственное решение в этом случае — провести ещё одно сравнение. К счастью, теперь известно, что третья монета подлинная, поэтому мы можем сравнить её с любой из первых двух, и это будет решением задачи. Любая монета, соответствующая третьей монете, будет подлинной, делая другую поддельной, в то время как любая монета, не соответствующая третьей монете, сама будет поддельной.

Эту стратегию можно проиллюстрировать с помощью следующего дерева решений:

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

Назовём совокупность серых множеств F поддельной, совокупность жёлтых множеств — R эталонной (мы знаем, что они подлинные, поэтому можем использовать их в качестве контрольных для проверки других монет). Совокупность бледно-голубых множеств — L с лёгкой фальшивкой, а бледно-розовых множеств — H с тяжёлой. Далее будем использовать f, r, l и h для количества элементов в F, R, L и H,соответственно.

Всякий раз, когда мы проводим измерение, сравнивая два набора A и B (например, наборы монет, отмеченные на дереве зелёными и пурпурными точками), наборы F, R, L и H изменяются следующим образом:

— Если A и B весят одинаково, то все A и B перемещаются в R и удаляются из F, L и H, поскольку единственная фальшивка в A или B склонила бы чашу весов в ту или иную сторону.

— Если A и B имеют разные веса, F становится пустым множеством, в то время как L становится теми элементами более лёгкого из множеств A и B, которые ранее были в L или в F, а H становится теми элементами более тяжёлого из множеств A и B, которые ранее были в H или в F. Всё остальное переходит в R.

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

Стратегию для N = 3 легко расширить до N = 4. Единственное отличие в том, что, когда начальная пара сравниваемых монет оказывается одинаковой по весу, это больше не позволяет сразу определить фальшивую монету, и нужно провести ещё одно сравнение, чтобы получить решение. Поэтому в этом варианте находим фальшивку, выполняя два сравнения в каждом случае.

А как насчет больших значений N? Прежде чем пытаться ответить на вопрос систематически, давайте рассмотрим один конкретный случай. Во второй головоломке с балансом требовалось решение для N = 12 за три сравнения. После определённого количества проб и ошибок получилось такое дерево решений:

Чтобы чрезмерно не загромождать дерево решений, ветвь, где первое сравнение показывает, что зелёный набор легче пурпурного мы опускаем, поскольку все действия для ветви, где верно обратное, можно легко адаптировать для этого результата, просто поменяв местами два набора 1-4 и 5-8.

Вот словесное описание стратегии:

Для первого измерения сравним четыре из двенадцати монет с четырьмя другими.

А. Предположим, что результатом измерения было то, что два набора из четырёх монет весили одинаково. Это означает, что теперь у нас есть восемь монет, которые, как мы знаем, являются подлинными, поэтому мы можем рассматривать их как эталонные монеты, и ещё четыре монеты, включающие поддельную.

Для измерения 2А сравним две из восьми эталонных монет с двумя из четырёх потенциальных подделок.

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

Для измерения 3AA сравним одну из эталонных монет с одной из двух оставшихся потенциальных подделок, что позволит однозначно определить, какая из них фальшивая.

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

Для измерения 3AB сравним одну из эталонных монет с одной из двух оставшихся потенциальных подделок, что позволит определить, какая из них поддельная.

B. Предположим, что результатом первого измерения было то, что два набора из четырёх монет имели разный вес. Это означает, что теперь у нас есть четыре эталонные (те, которые не участвовали в измерении), четыре тяжёлые и четыре лёгкие монеты.

Для измерения 2B мы берём три тяжёлые вместе с двумя лёгкими монетами и сравниваем их с одной тяжёлой монетой и четырьмя эталонными монетами. Это оставляет нам две лёгкие монеты, не принимающие участия в измерении.

Предположим, что результатом измерения 2B было то, что три тяжёлые и две лёгкие монеты были легче, чем одна тяжёлая и четыре эталонных монеты. Это оставляет нам только одну монету, которая может оказаться тяжёлой подделкой, и две монеты, которые также могут содержать лёгкую подделку.

Для измерения 3BA мы сравниваем те две монеты, которые могут включать лёгкую подделку. Если они разные, то более лёгкая из двух монет является подделкой. Если они одинаковы, то одна более тяжёлая монета является подделкой.

Предположим, что результатом измерения 2B было то, что два набора монет, которые мы сравнивали, весили одинаково. Это превращает все десять в эталонные, и означает, что поддельной должна быть одна из двух более лёгких монет, которые мы отложили.

Для измерения 3BB мы сравниваем одну из этих двух более лёгких монет с эталонной монетой, что позволяет определить, какая из них поддельная.

Предположим, что результатом измерения 2B было то, что три тяжёлые монеты и две лёгкие монеты были тяжелее, чем одна тяжёлая монета и четыре эталонных. Это оставляет нам только три тяжёлые монеты в качестве возможных подделок.

Для измерения 3BC сравним две из этих трёх тяжёлых монет. Если они весят одинаково, то третья — фальшивая. Если одна из них тяжелее другой, то более тяжёлая из двух — фальшивая.

Хотя большинство отдельных шагов здесь было довольно легко придумать, одно сравнение, которое выделяется как гораздо менее очевидное, чем другие, — это измерение 2B в письменном описании, которое является верхним сравнением 2-го уровня в древовидной диаграмме. Здесь мы сравниваем два набора монет, каждый из которых взят из двух разных категорий: три монеты из H и две из L сравниваются с одной из H и четырьмя из R.

Мы можем расширить эту стратегию до N = 13 по-прежнему всего с тремя сравнениями. Опять же, сравним четыре монеты с четырьмя другими в качестве первого измерения, и, если у них разный вес, всё работает, по сути, так же, как и для N = 12.

Если у них одинаковый вес, измерение оставляет нам восемь эталонных и пять потенциальных подделок. Теперь сравниваем три потенциальных подделки с тремя эталонными монетами. Если потенциальные подделки весят столько же, сколько эталонные, мы сужаем возможности до двух других потенциальных подделок, и фальшивка легко находится с помощью ещё одного сравнения.

Если три потенциальные подделки тяжелее или легче эталонных монет, сравнение определенно говорит нам, тяжелее или легче подделка, что возвращает нас к N = 3 для первого или второго варианта (из четырёх вариантов в самом начале статьи), который решается путём сравнения одной пары из трёх монет.

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

— f = 2, r ≥ 1. Мы сравниваем одну потенциальную подделку с одной эталонной монетой, что скажет нам, что либо сравниваемая монета является поддельной, либо оставшаяся.

— l + h = 2 или 3, и один из l или h не меньше двух, поэтому (l, h) = (0, 2), (0, 3), (1, 2), (2, 0), (2, 1) или (3, 0). Сравниваем две монеты из одного набора друг с другом; если они одинаковы, то должна быть третья монета, которая является фальшивой, но, если одна тяжелее, а другая легче, так как мы уже знаем, что эти две монеты могут быть подделками только одного конкретного вида, это решает, какая из них является фальшивкой.

— l = 1, h = 1, r ≥ 1. У нас больше нет пары одинаковых монет для сравнения друг с другом, но сравнение любой из потенциальных подделок с эталонной монетой решит вопрос.

Теперь давайте рассмотрим сравнение самого общего вида. Когда у нас есть монеты в сером множестве F:

w монет из F сравниваются с v из F, (w - v) из R, при этом (f - w - v) из F откладываются в сторону.

После измерения мы получаем один из следующих результатов:

— Первый набор был легче второго. Теперь у нас есть w монет в L и v монет в H, все остальные в R.

— Первый набор был таким же, как и второй. Теперь у нас есть монеты (f - w - v) в F, все остальные в R.

— Первый набор был тяжелее второго. Теперь у нас есть w монет в H и v монет в L, все остальные в R.

Когда у нас есть монеты в голубых и розовых наборах L и H, наиболее общее сравнение выглядит так:

монеты a из L, b из H сравниваются с c из L, d из H, (a + b - c - d) из R, при этом откладываются (l - a - c) из L, (h - b - d) из H.

После измерения мы получаем один из следующих результатов:

— Первый набор был легче второго набора. Теперь у нас есть монеты a в L и d в H, все остальные в R.

— Первый набор был таким же, как и второй. Теперь у нас есть монеты (l - a - c) в L и (h - b - d) в H, все остальные в R.

— Первый набор был тяжелее второго. Теперь у нас есть монеты c в L и b в H, все остальные в R.

Теперь способом, похожим на первый вариант, хотя и немного более сложным, разделим монеты в L и H на три группы. Все одинакового размера, если общее число делится на три. С одной дополнительной в одной группе, если в остатке одна монета. И по одной дополнительной в каждой из двух групп, если в остатке две монеты. Такое разделение в любом случае приведёт к тому, что по крайней мере две из групп будут равны по размеру, однако заранее гарантировать одинаковый вес какой-либо конкретной пары групп нельзя.

Эти три группы определят возможные новые наборы элементов L и H после следующего сравнения. Это сравнение будет между (A) всеми текущими элементами L в первой группе и всеми элементами H во второй группе, и (B) всеми элементами L во второй группе и всеми элементами H в первой группе.

Если один из этих наборов меньше другого, нам нужно будет восполнить разницу, дополнив меньший набор эталонными монетами из R. Если сравнение покажет нам, что A весит меньше B, это сожмёт L и H до их пересечения с первой группой.

Если A весит больше B, это сожмёт их до пересечения со второй группой.

Если A и B весят одинаково, это сожмёт их до пересечения с третьей группой.

Максимальное значение (l + h), которое мы можем уменьшить до единицы в С сравнениях таким образом, будет 3^C, но начальное значение (l + h) всегда будет чётным, потому что l и h всегда будут равными в первый раз, когда они не равны нулю (например, они оба равны четырём в нашем дереве решений для N = 12).

Таким образом, (3^C - 1) будет фактическим максимумом. Тогда вопрос в том, сколько монет мы должны сравнить в самом первом сравнении, и сколько мы должны отложить. Число, которое мы сравниваем, определит значение, разделяемое l и h, если сравнение покажет, что наборы имеют разные веса. В то время как число, которое мы откладываем, определит значение f, если наборы окажутся с одинаковым весом.

Предположим, что мы изначально сравниваем два набора монет w = (3^C - 1)/2. Сколько дополнительных монет мы могли бы отложить, не рискуя увеличить количество сравнений C, которое, как мы знаем, будет достаточным для обнаружения фальшивой монеты, если она находится в двух изначально сравниваемых наборах?

Если мы посмотрим на максимум, который мы можем установить для (l + h), после начального значения (3^C - 1) он падает до 3^C-1. Например, для C = 3 у нас есть (3^C - 1) = 26, которые мы затем разделим на наборы по 9, 9 и 8. При каждом последующем сравнении у нас есть максимум для (l + h), равный 3^{C - K}.

Итак, предположим, что у нас есть дополнительные (3^C +1)/2 монеты в начале, так что после первого сравнения мы можем получить f = (3^C +1)/2. Если мы затем возьмем 3^{C - 1} из них и сравним их с контрольными монетами, то, если они окажутся тяжелее или легче, мы получим либо l, либо h, равные 3^{C - 1}, а другие нулю, поэтому (l + h) будет соответствовать максимуму, который мы получаем на том же этапе другим путём. И если они окажутся одинаковы по весу с эталонными монетами, то то, что у нас останется в качестве нового значения f, будет:

Таким образом, мы можем продолжать эту стратегию столько, сколько нам нужно. Когда f равно (3^{C – K} +1)/2, максимум (l + h) на один шаг глубже в дереве решений будет равен 3^{C – K – 1}.

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

Эта формула принимает значения 1, 4, 13, 40, 121, ..., хотя, как я отмечал выше, имеет смысл начинать только с N = 3. Чтобы конкретизировать этот факт, нужно сформулировать алгоритм выбора сравнений в каждой точке дерева решений для любого N ≥ 3. Но об этом я напишу во второй части материала.

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS