Взвешивания на двух весах

Аналогичная головоломка для одних двухчашечных весов широко известна — в ней за три минуты удаётся определить фальшивую монету из 12. При этом первым взвешиванием нужно на каждую чашу весов положить по 4 монеты, а еще 4 оставить отложенными. А здесь у нас двое весов, или, если угодно, четырёхчашечные весы. Вместе с отложенными монетами получается пять групп. Что если и здесь поделить монеты по группам поровну?

Каким может быть результат взвешивания? Ясно, что фальшивая монета либо окажется на каких-то весах, либо не окажется.

В первом случае на каких-то весах одна из чаш опустится, а другая поднимется. Во  втором — весы останутся в равновесии.

Второй случай будет означать, что теперь нам нужно искать фальшивую монету только среди 12 отложенных, и на это у нас есть аж две минуты. А как «расшифровать» первый случай?

Итак, мы делаем первое взвешивание, описанное в первой подсказке: на каждую чашу весов кладём по 12 монет.

Группы монет, которые могут содержать фальшивую (после уже проведенных взвешиваний), мы будем называть подозрительными (П-монетами). Например, если после первого взвешивания и первые, и вторые весы оказались в равновесии, то подозрительной оказывается лишь одна группа — те 12 монет, которые не взвешивались. Если же на каких-то весах равновесия не наступило, то подозрительными будут две группы (24 монеты). На первый взгляд, этот случай чуть ли не вдвое хуже, однако на самом деле это не так, и вот почему: если фальшивой будет одна из 12 невзвешенных монет, то она может оказаться как более лёгкой, так и более тяжёлой. Но если фальшивой будет одна из 24 взвешенных, то она может быть только какой-то одной — фальшивая из первых 12 монет может быть только более лёгкой, а из вторых 12 — только более тяжёлой, чем настоящие.

Поэтому мы сразу разделим все П-монеты на три типа: если П-монета может быть и легче, и тяжелее настоящей, то ее отнесём к ЛТ-типу, если только легче, то к Л-типу, а если только тяжелее, то к Т-типу.

Таким образом, исход первого взвешивания мы можем кратко записать так:

либо (A1) осталось 12 ЛТ-монет, либо (Б1) 12 Л-монет и 12 Т-монет.

Остальные монеты (36 или 48) перестали быть подозрительными, то есть каждую из них можно дальше использовать как заведомо настоящую монету.

Второе взвешивание:

(А1) Положим на каждую чашу весов по 3 монеты, причём если на одной из чаш весов это будут 3 ЛТ-монеты, то на другой — 2 ЛТ-монеты и одна настоящая. Такое взвешивание кратко запишем в такой форме:

3 ЛТ | 2 ЛТ + 1 Н || 3 ЛТ | 2 ЛТ + 1 Н || 2 ЛТ + 46 Н

Здесь одинарная вертикальная черта символизирует стрелку весов и отделяет одну чашу весов от другой чаши тех же весов, а двойная вертикальная черта отделяет одни весы от других (и от невзвешиваемых монет).

Итог второго взвешивания после равновесия: (А2) множество подозрительных монет уменьшилось до 2 ЛТ. Итог после неравновесия (Б2): подозрительных монет осталось всего 5; это либо 3Л и 2Т, либо 3Т и 2Л. А поскольку эти случаи совершенно эквивалентны, дальше мы будем рассматривать только первый из них.

(Б1) Здесь нужно разделить по пяти группам 24 монеты. Сделаем это вот так:

3 Л + 2Т | 3 Л + 2 Т || 3 Т + 2Л | 3 Т + 2 Л || 2 Л + 2Т + 36 Н

Итогом после равновесия будет (В2): 2Л + 2Т.

А итог после неравновесия — снова (Б2)! Например, если левая (первая) чаша на первых весах оказалась легче правой (второй), то это означает, что подозрительными остались 3 Л-монеты левой чаши и 2 Т-монеты правой. Более того, поскольку подозрительных монет каждого вида в (В2) меньше, чем в (Б2), то мы всегда можем добавить к (В2) одну заведомо настоящую монету и затем поступать так же, как мы поступим с (Б2).

Третье взвешивание:

(А2) 1 ЛТ | 1 Н || 1 ЛТ | 1 Н || 56 Н

Собственно, тут дальше всё очевидно.

(Б2) 1 Л + 1 Т | 2 Н || 1 Л + 1 Т | 2 Н || 1 Л + 51 Н

И здесь тоже очевидно: если весы в равновесии, то фальшивая — единственная невзвешенная Л-монета, а если какие-то весы не в равновесии, то по знаку неравенства мы легко поймём, какая именно из двух подозрительных монет на самом деле оказывается фальшивой.

В 2012 году на заочном матче по решению головоломок между Россией и Украиной эта же задача предлагалась в «обратной» формулировке: для какого наибольшего числа монет удастся определить фальшивую монету за 5 минут? Ответ в матчевой задаче — 1561 — может быть получен по формуле (5⁵ – 3)/2. Аналогично, для N минут максимальное число монет равно (5^N – 3)/2, что при N = 3 даёт 61, а не 60.

Самый интересный (с точки зрения математики) вопрос здесь не в том, КАК, а в том, ПОЧЕМУ именно 61 оказалось максимальным количеством. Вдруг можно как-то иначе провести взвешивания, и в результате определить фальшивую среди большего числа монет? Оказывается, это невозможно. Объяснить это «на пальцах» можно примерно так.

После каждого взвешивания мы можем записать его исход (== — два равенства, остальные варианты: <=, >=, =<, =>) числом от 0 до 4. Затем мы как-то делаем второе взвешивание, его исход записываем вторым числом, затем исход третьего пишем третьим числом. В результате получаем тройку чисел (x₁, x₂, x₃). Всего таких троек может быть не более 125. После трёх взвешиваний мы должны суметь определить фальшивую монету. При этом ровно в одном из исходов (три раза равновесие на всех весах) мы не будем знать, является ли определённая нами монета более легкой или более тяжелой. В остальных 124 случаях мы сможем про каждую фальшивую монету сказать еще и то, легче она или тяжелее. Более того, для каждой из исходных монет мы должны иметь возможность определить те два случая, когда именно она оказалась фальшивой. А так как вариантов у нас только 124 + 1, то фальшивых монет может быть не больше, чем 62 + 1 = 63.

Итак, наше рассуждение показывает, что для более чем 63 монет головоломку решить нельзя. А выше было написано про 61. Как же быть с 63 или 62? Подумайте сами; если вы поняли рассуждение с тройками результатов, то додумать остальное уже совсем несложно.

* * *

А что бы было, если бы фальшивая монета могла бы быть только более лёгкой (ну, или более тяжёлой)? Тогда бы за три взвешивания можно было разобраться со 125 монетами, а за N взвешиваний — с 5^N.

Аналогично, если бы параллельные взвешивания можно было бы делать не на двух, а на K весах, то общее число групп, на которое мы каждый раз могли бы разделить оставшиеся подозрительными монеты, было бы равно не 5, а 2K + 1, поэтому ответ для N минут был бы что-то около (2K + 1)^N/2.

В чем интересность таких задач? Прежде всего, они позволяют самостоятельно разобраться в том, что же собой представляет многозадачность современных компьютерных систем и какие возможности она открывает. Ещё не так давно многозадачный и многопользовательский режимы работы на компьютерах реально были фикцией: один процессор за 1 такт работы справлялся только с одной операцией, а иллюзия многозадачности создавалась за счёт того, что в разные такты процессор мог заниматься разными задачами, время от времени переключаясь между ними и создавая для пользователя иллюзию непрерывной работы над каждой. С тех пор как в каждом ноутбуке стоят двух- и четырехъядерные процессоры, возможность параллельных вычислений стала реальностью. И как ни удивительно, иногда это даёт выигрыш во времени не в два раза, а намного больше. Не верите? Ну так давайте посмотрим ровно на эту самую задачу для одних весов и для двух весов:

Отношение второй колонки к первой примерно равно (5/3)ⁿ, то есть с ростом n растёт экспоненциально. Чем больше количество времени, которое мы готовы потратить на взвешивания, тем больший выигрыш получается при применении двух весов вместо одних.

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