Задача о средней монете

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

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

Договоримся поступать с результатами этих четырех взвешиваний так: если одна из монет оказалась тяжелее, то положим ее в «Т-группу», а другую монету в «Л-группу». Если же обе монеты равны, то отложим эту пару отдельно. Монету, которая в этих четырех взвешиваниях не была на весах, будем обозначать буквой X.

Рассмотрите по отдельности несколько случаев, отличающихся числом отложенных пар.

Самый тяжелый случай — когда ни одной отложенной пары нет. При этом мы не можем объявить «ненастоящей» ни одну из девяти монет. Однако мы знаем, что если настоящая монета входит в Т-группу, то она легче всех остальных монет этой группы, а если она из Л-группы, то тяжелее. Таким образом, у нас осталось девять возможностей, и двумя взвешиваниями мы должны их четко разделить. В частности, это значит, что равновесие в пятом взвешивании должно соответствовать трем возможностям. Поскольку равновесие в наших условиях всегда означает, что настоящая монета не взвешивается, то в следующем (пятом по счету) взвешивании должны быть три отложенных монеты, и на каждой из чаш должны быть по три монеты.

Краткое резюме того, что мы уже отметили в подсказках 1–3:

• Буквой Л обозначаются легкие монеты, буквой Т — тяжелые, а буквой Н — настоящая.
• Первые четыре взвешивания — это попарные сравнения восьми монет друг с другом.
• Если одна из двух взвешиваемых монет оказалась тяжелее, то кладем ее в «Т-группу», а вторую — в «Л-группу».
• Если же обе монеты равны, то отложим эту пару отдельно.
• Монету, которая в этих четырех взвешиваниях не была на весах, обозначим буквой X.

Случай 1: Т- и Л-группа состоят из 4 монет каждая, ни одной отложенной пары нет.

Обозначим имеющиеся монеты Т1, Т2, Т3, Т4, Л1, Л2, Л3, Л4 и X. Если монета Н входит в Т-группу, то она легче остальных монет этой группы, а если Н входит в Л-группу, то — тяжелее.

Пятое взвешивание: Т1 + Т2 + Л1 vs Т3 + Т4 + Л2.

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

Неравенство (например, Т1 + Т2 + Л1 легче Т3 + Т4 + Л2) означает, что настоящая монета — это либо Т1, либо Т2, либо Л2. Тогда достаточно сравнить шестым взвешиванием Т1 с Т2.

Случай 2: Т- и Л-группа состоят из 3 монет каждая.

Еще есть одна отложенная пара одинаковых монет (O1 и O2), ни одна из которых не может быть настоящей, поэтому мы их во взвешиваниях больше не используем. Обозначим оставшиеся монеты Т1, Т2, Т3, Л1, Л2, Л3, X. Поскольку здесь нам хочется разделить имеющиеся семь вариантов на 2+3+2, то взвешивать будем по две монеты.

Пятое взвешивание: Т1 + Л1 vs Т2 + Л2.

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

Если же, например, Т1 + Л1 < Т2 + Л2, то настоящая — либо Л2, либо Т1. Тогда дальше можно просто сравнить Л1 с Л2 (либо Т1 с Т2 — это даст то же самое), и по результату этого взвешивания узнать настоящую.

Случай 3: Т- и Л-группы состоят из 2 монет каждая.

Опять отложенные пары монет нас больше не интересуют, настоящая монета — это одна из Т1, Т2, Л1, Л2, X. Здесь можно потратить оставшиеся взвешивания просто на сравнение Т1 с Т2 и Л1 с Л2. Если оба раза будет равенство — настоящей является X.

Случай 4: в Т- и Л-группах всего по 1 монете.

То есть нам надо выбрать настоящую монету из Т1, Л1, X. Сравним Т1 с X (пятое взвешивание) и Л1 с X (шестое). Если мы хотя бы в одном взвешивании получим равенство, то настоящей будет та монета, которая в этом взвешивании не участвовала. А если нет, то настоящая — средняя по весу из трех этих монет.

Случай 5: Т- и Л-группы пусты.

Тогда настоящая монета — это X, никаких взвешиваний больше не нужно.

Все случаи разобраны, во всех случаях мы определили настоящую монету.

Разобранная нами головоломка впервые появилась в 2013 году на командном конкурсе MIT Mistery Hunt, который проводится ежегодно с 1981 года. Она находится в прямой связи с такими классическими задачами информатики (computer science) как задача сортировки и задача выбора i-го по величине элемента в массиве.

Полная «историография» и библиография по этим задачам выходит очень далеко за рамки комментария к этой задаче, поэтому я ограничусь всего двумя замечаниями:
1) некоторые методы сортировки, применяемые сейчас на компьютерах, по-видимому, изобретены еще до появления компьютеров и поначалу применялись для обработки перфокарт с результатами переписей населения;
2) в монографии «Искусство программирования» Д. Э. Кнута сортировке и поиску посвящен целый том.

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

Более-менее очевидно, что для выбора любой из «крайних» статистик достаточно проделать n − 1 сравнение (если угодно, это можно переформулировать в терминах взвешиваний: для поиска самой легкой из n монеток достаточно проделать n − 1 взвешивание на чашечных весах). Действительно, чтобы найти минимум, достаточно вначале сравнить два элемента, а затем последовательно сравнивать наименьший из уже просмотренных с любым из еще не просмотренных. Можно очень просто доказать и необходимость такого числа сравнений, то есть невозможность гарантированно определить наименьший элемент за меньшее количество попарных сравнений. Действительно, рассмотрим своеобразный «турнир» среди n чисел, а каждое сравнение — как «партию», в которой меньшее число побеждает. Чтобы определить победителя турнира, каждое из остальных чисел должно проиграть по крайней мере одну партию, так что меньше n − 1 партий быть не может.

Однако для «средних» статистик такие очевидные способы, увы, не срабатывают. Специалисты в течение достаточно долгого времени были уверены (а многие программисты сохранили эту уверенность и до сих пор), что для выбора какого-нибудь среднего числа (например, 44-го из 100) нет лучшего способа, чем выполнить полную сортировку 100 чисел и взять 44-й из отсортированных элементов. Однако, к счастью, это не так. Еще в 1973 году Блюм, Флойд, Пратт, Райвест и Тарьян опубликовали алгоритм нахождения медианы за «линейное в худшем случае время». Если перевести эту терминологическую абракадабру на доступный язык, то она означает, что нахождение среднего элемента среди N всегда требует не более kN сравнений, где k — какое-то определенное число, не зависящее от N.

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

Вот так и вышло, что первыми о самом простом частном случае задумались не профессиональные алгоритмисты и математики, а любители головоломок. Что, если нам нужно найти медиану (элемент множества, равный M) при условии, что все элементы либо равны M, либо равны L, где L < M, либо равны H, и H > M? Эту задачу мы здесь не обсуждали, но поскольку она не очень сложна и очень интересна, я готов оставить ее читателю в качестве самостоятельного «домашнего задания». Понятно, что она тоже может быть решена за «линейное в худшем случае» число сравнений, и не очень удивительно, что коэффициент пропорциональности здесь будет меньше, чем лучший из известных для общего случая.

А если еще дополнительно известно, что медиана единственна? Оказывается, что при этом задача решается еще быстрее. А именно, не более чем за n сравнений в худшем случае. Эту задачу (для произвольного n) мы тоже не обсуждали, но после решения основной задачи она уже не должна вызывать трудности.

Ну и, наконец, если вместо произвольного n взять определенное значение (9) и разрешить использовать не только попарные сравнения, но и более общие «взвешивания», то получается ровно та задачка, которой мы и занимались. Она решается еще быстрее (в нашем частном случае — за 6 взвешиваний вместо 9), но это решение, увы, не переносится на более общие случаи.