Головоломки с балансом. Поиск фальшивой монеты (часть 2)

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

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

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

где u равно 0, 1 или 2. В зависимости от значения остатка u, которое мы получим после деления (l + h) на три, у нас будет три возможных тройки значений для размера трёх групп, на которые мы разделим (l + h) монет:

Если u = 0, размеры групп равны (t, t, t).

Если u = 1, размеры групп равны (t, t, t + 1).

Если u = 2, размеры групп составят (t + 1, t + 1, t).

Но пока не будем брать на себя обязательства относительно того, какая из них g₁, g₂, g₃ (размер первой, второй и третьей групп). Первая группа состоит из a монет из множества L и d монет из H. Вторая группа состоит из c монет из L и b монет из H. Наше сравнение будет между a монетами из L вместе с b монетами из H против c монет из L вместе с d монетами из H, с таким количеством эталонных монет, добавленных к одной стороне, которое нам нужно, чтобы гарантировать, что мы сравниваем одинаковое количество монет.

Это приводит к следующим уравнениям и неравенствам:

Итак, для данного выбора g₁ и g₂ мы имеем (a, b), ограниченные прямоугольником в координатной плоскости первым набором неравенств, а затем дополнительно ограниченные полосой, проходящей под углом 45° к осям координат вторым набором неравенств. Затем выберем конкретную точку (a, b), которая определяет другие параметры сравнения, (c, d) и количество эталонных монет, которое нам нужно использовать:

При рассмотрении выборов для g₁ и g₂ (когда есть более одной возможности) нужно проверить, что прямоугольник и полоса 45° имеют непустое пересечение. Затем вместе с нашим выбором (a, b) мы попытаемся сделать ρ как можно меньше, чтобы гарантировать, что у нас будет столько эталонных монет, сколько нам нужно.

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

Во-первых, отметим, что сама полоса 45° не может быть пустой, поскольку число целочисленных значений, которые она допускает для (a — b), равно:

Диапазон значений (a — b), охватываемый верхним левым и нижним правым углами прямоугольника, составляет:

Чтобы пересечение было пустым, один из этих диапазонов должен был бы полностью лежать за пределами другого. Если диапазон прямоугольника находится слева от полосы 45°:

Что, очевидно, невозможно, если только l не является минимумом в min (g₁, l), поэтому потребуется:

что в свою очередь приводит к невыполнимому требованию:

Аналогично, оказывается невозможным, чтобы диапазон прямоугольника лежал справа от полосы 45°. Таким образом, мы свободны выбирать g₁ и g₂ без какого-либо риска сделать множество решений для (a, b) пустым.

Это оставляет нас с проблемой выбора определённых значений для g₁, g₂ и (a, b) с целью минимизации:

В зависимости от ограничений прямоугольника и полосы в 45° сумма (2a + 2b) принимает постоянные значения на каждой линии, пересекающей плоскость под углом -45°. Поэтому для минимизации ρ нужно, чтобы точка (a, b) лежала как можно ближе к конкретной линии, где (2a + 2b) = (g₁ + g₂).

g₁ и g₂ либо равны, либо отличаются на единицу. Единственный вариант, в котором мы в конечном итоге не используем эталонные монеты, подразумевает их равенство. Итак, давайте предварительно предположим, что делаем именно этот выбор (т. е. g₁ = g₂), и посмотрим, столкнёмся ли мы с какими-либо препятствиями.

Какую конкретную точку мы могли бы выбрать для (a, b)?

Точка P₁ = (g₁, 0) будет лежать на линии, которая даёт нам ρ = 0, но она может не соответствовать необходимым ограничениям. Непременно нужно чтобы выполнялось следующее условие:

Очевидно, что P₁ однозначно удовлетворит первому неравенству, но может удовлетворить или не удовлетворить второму. Если 2g₁ > l, рассмотрим альтернативную точку P₂ = (floor(l/2), g₁ — floor(l/2)).

Что даёт нам следующее нестрогое неравенство:

Удовлетворяет ли альтернативная точка первому неравенству? Для его нарушения потребуется, чтобы:

Если l чётное, то правая часть уравнения — (l + h), и невозможно, чтобы сумма двух групп одинакового размера из трёх, на которые делится (l + h), имела больший размер. Если l нечётное, то неравенство становится следующим:

Оно выполняется, только если g₁ = g₂ = 1 и g₃ = 0, при этом (l + h) = 2. Поскольку мы также требуем, чтобы 2g₁ > l, такое возможно только при l = h = 1. Ранее я уже отмечал, что это может быть случай, требующий особого рассмотрения, поэтому пока отложим его в сторону и проверим, выполняются ли другие ограничения для всех остальных случаев.

Если 2g₁ ≤ l, то P₁ = (g₁, 0) лежит в нижнем правом углу прямоугольника, потому что min (g₁, l) = g₁, то есть удовлетворяет всем ограничениям.

Если 2g₁ > l, то P₂ = (floor(l/2), g₁ — floor(l/2)). Обе координаты явно неотрицательны, и a = floor(l/2) меньше или равно как g₁, так и l. Также нужно чтобы выполнялось неравенство:

Теперь можем переписать h и получить:

Отсюда следует, что h ≥ g₁, поэтому становится очевидным, что правая часть ограничения для b равна min (g₁, h) = g₁.

Итак, теперь у нас есть достаточно простой алгоритм для принятия решения о том, какое сравнение следует выполнять, когда мы имеем дело с множествами L и H:

if l = 1 and h = 1 then Set g1 = 1, g2 = 0, g3 = 1 Set a = 1, b = 0, c = 0, d = 0 and ρ = 1 #Сравниваем одну монету в множестве L с одной эталонной монетой else Set g1 = g2 = round((l+h)/3) if 2 g1 ≤ l then Set a = g1, b = 0, c = g1, d = 0 and ρ = 0 #Сравниваем g1 монет из множества L с g1 монет из H else Set a = floor(l/2), b = g1 - floor(l/2), c = floor(l/2), d = g1 - floor(l/2) and ρ = 0 #сравниваем floor(l/2) монет из множества L и g1 - floor(l/2) монет из H со вторым набором, содержащим такое же количество монет из L и H

В первоначальном сравнении можно разделить монеты точно так же, как мы это делали для первого варианта (когда известно, что фальшивая монета определённо легче настоящей, см. первую часть статьи). Но также нельзя забывать про общий случай, когда у нас есть множество F, а не L и H. Если N ≤ (3^C — 1)/2 (где С — наименьшее целое число, для которого это верно). Нужны гарантии, что после K-го сравнения (начиная с K = 1 для первоначального сравнения), у нас не получится, что (l + h) будет больше, чем 3^C-K. Поэтому мы сравниваем это количество монет в F с эталонными монетами или всё множество F, если оно содержит меньше монет.

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

Если для сравнения мы всегда берём 3^C-K монет из множества F (для K = 2, …, C), что в сумме составляет (3^{C — 1} — 1)/2. То есть меньше на одну монету, чем количество монет, которое мы откладываем в первом сравнении, когда N точно равно верхнему пределу (3^C — 1)/2. Если бы количество монет N было на одну меньше, мы бы также откладывали на одну монету меньше. А в конце решения задачи в множестве F у нас бы совсем не осталось монет. Таким образом, для четвёртого варианта максимальное количество монет, с которыми мы можем справиться, используя C сравнений, становится:

На этом, пожалуй, всё. Мы познакомились с одним из типов математических головоломок с балансом и сформулировали алгоритм принятия решения для нахождения одной фальшивой монеты среди совокупности подлинных монет. Конечно, головоломки такого типа можно серьёзно усложнить дополнительными условиями, например, увеличить количество фальшивых монет. В более интересном варианте можно допустить наличие разных подделок — как «тяжёлых», так и «лёгких», что ещё сильнее усложняет решение задачи. Там, конечно, будет совсем другая математика, на порядок сложнее, чем в этой статье, но это как говорится, уже совсем другая история.

P.S. К статье прилагается архив с демкой этого алгоритма (html+js).

---

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