ЗДОРОВЬЕ ТЕЛА И ДУШИ

Алгоритмическая задача

Продолжим обсуждение  задачи [...].

Профессор. Обратите внимание, что вопрос о самом эффективном алгоритме становится особенно важным, если сформулировать задачу следующим образом: каково наименьшее количество взвешиваний, с по­мощью которых можно выявить фальшивую монету среди N монет? В такой формулировке задачи, даже при конкретном значении N, решение должно быть иным. Заметьте, что, вообще говоря, не требуется разрабатывать алго­ритм группировки монет и их взвешиваний. Но если вы все же пошли по та­кому пути, то необходимо еще доказать, что не существует более эффектив­ного алгоритма.

Зануда. Я, пожалуй берусь доказать, что для достаточно больших  количеств всех монет N не обойтись одним взвешиванием.

П р о с т а к. Но это почти и так очевидно, безо всяких выкладок.

Зануда. Но если я это докажу, то смогу убедить вас, что мой алго­ритм для случая N = 8 или N = 9 самый эффективный.

Профессор. Попробуйте, уважаемый Зануда, это интересно.

Зануда. В самом деле, взвешивание состоит в том, что на чаши весов кладутся два подмножества монет, причем монет должно быть поровну, поскольку в противном случае результат взвешивания ничего не скажет нам о наличии или отсутствии фальшивой монеты. Итак, сравниваемых подмножеств должно быть минимум два. Допустим, эти подмножества содержат по m монет. Разуме­ется. m?0 и 2m < N. Очевидно, возможны два варианта:

1.    2m = N. Нетрудно заметить, что N является четным числом. Если N = 2, то m = 1 и,  следовательно,  достаточно  одного взвешивания. Если N > 2 (например, 4, 6, 8, ...), то m > 1 и результат взве­шивания приведет к необходимости рассматривать подмножество из нескольких монет, следовательно, понадобится, по крайней мере, еще одно взвешивание. Таким образом, для четных N>2 одного взвешивания не­достаточно.

2.    2m < N. Нетрудно заметить, что в данном случае N > 2 (например, 3, 4, 5,
...). Если N = 3 или N = 4, то m=1 и, следовательно, одного взвешивания будет достаточно. Если N > 4, то либо m > 1, либо N – 2m > 1. В первом случае при взвешивании не исключено, что фальшивая монета окажется среди m > 1 монет, и тогда потребуется хотя бы одно дополнительное взвешивание. Во втором случае не исключено, что при первом взвешивании вес подмножеств окажется одинаковым и придется рассматривать подмножество из N-2m> 1 монет, а тогда без дополнительного взвешивания не обойтись. Итак, при N > 4 одного взвешивания недостаточно.

Объединяя результаты рассмотрения двух частных случаев, но исчерпываю­щих все пространство возможностей, заключаем, что при общем количестве монет N?4 требуется не меньше двух взвешиваний. Поскольку ранее я изо­брел алгоритм, обеспечивающий для N = 8 и N = 9 только что полученное минимальное, равное двум, количество взвешиваний, он наилучший.

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

Зануда. Честно говоря, на меня повлияло твое, Простак, упоминание о поиске льва в пустыне методом деления ее участков пополам - Я тогда подумал: а что если делить не пополам, а на три или больше частей? Но теперь я и сам вижу, что мой алгоритм не зависит от этой идеи. Она была моей "музой" — скорее стимулировала мое воображение, чем указывала путь. Алгоритм решения был почти полностью предопределен условием задачи: взвешивайте группы монет на рычажных весах.

Оставалось неоче­видным: что сравнивать с помощью весов — две произвольно выбранные монеты или два произвольных подмножества монет?  То, что количества мо­нет на разных чашах весов должны быть одинаковы, и так понятно,  сколько монет следует выбирать для одного взвешивания, я вычислил, рас­суждая логически.

Простак. Мне кажется, что подобным образом можно доказать, что для одних значений N потребуется не менее трех, а для других — не менее четырех взвешиваний. Хорошо бы найти формулу, определяющую ми­нимальное количество взвешиваний для заданного N.

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

Профессор. Попробуйте это сделать на досуге, сейчас не будем тратить на это время.

Простак. Действительно, мы и так слишком задержались на этой задаче, не имеющей важного практического значения. Но меня сейчас больше волнует вопрос: может быть, это не единственный алгоритм, обеспе­чивающий обнаружение фальшивой монеты с помощью минимального коли­чества взвешиваний?

Профессор. Да, таких алгоритмов может быть несколько. Например, при N = 6 можно разбить множество всех монет на 2 подмно­жества по 3 монеты либо на 3 подмножества по 2 монеты. В любом случае, потребуется 2 взвешивания. А поскольку для N = 6 по "теореме" Зануды это минимальная оценка, то оба алгоритма считаются наилучшими. Замечу, что здесь алгоритмы различаются только способом исходного разбиения множе­ства монет на подмножества.

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

Статья подготовлена по материалам книги Вадима Дунаева «Занимательная математика. Множества и отношения».