Интересные ссылки

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

И вновь интересная алгоритмическая задача. Одна из девяти монет фальшивая!

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

Простак. Для решения головоломки с девятью монетами следует попробовать применить тот же алгоритм, что и в случае с восемью монета­ми. Разбиваем множество всех монет на три количественно равных подмно­жества, т. е. по три монеты в каждом. Далее сравниваем на весах любые два из них. Если вес одинаков, то фальшивая монета в третьем множестве, которое мы не клали на весы. А что с ним делать, мы уже знаем из предыдущей версии головоломки. Чтобы выявить в нем фальшивку, требуется только одно взвешивание. Всего же необходимо два взвешивания.

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

Зануда. Пока Простак решал задачу по моему алгоритму, я уже успел  выяснить,  что в случае  10 монет понадобятся  минимум 3 взвешивания.

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

Зануда. Признаюсь, я применил тот же алго­ритм, что и для задач о 8 и 9 монетах. А о воз­можности существования другого, более эффективного алгоритма я не подумал.

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

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

Впереди - новые алгоритмические задачи! До новых встреч! Эта алгоритмическая задача (продолжение) [...]

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