ЗДОРОВЬЕ ТЕЛА И ДУШИ
Как сохранить и обрести здоровье
Алгоритмическая задача Одна из девяти монет
И вновь интересная алгоритмическая задача. Одна из девяти монет фальшивая!
Профессор. Теперь я несколько усложню задачу. Пусть количество внешне одинаковых монет равно 9. Может ли в этом случае с помощью двух взвешиваний быть найдена более легкая фальшивая монета?
Простак. Для решения головоломки с девятью монетами следует попробовать применить тот же алгоритм, что и в случае с восемью монетами. Разбиваем множество всех монет на три количественно равных подмножества, т. е. по три монеты в каждом. Далее сравниваем на весах любые два из них. Если вес одинаков, то фальшивая монета в третьем множестве, которое мы не клали на весы. А что с ним делать, мы уже знаем из предыдущей версии головоломки. Чтобы выявить в нем фальшивку, требуется только одно взвешивание. Всего же необходимо два взвешивания.
Если же при первом взвешивании выяснилось, что сравниваемые трехмонетные подмножества имеют разный вес, то переходим к более легкому из них. Как нам уже известно, в этом случае потребуется только одно взвешивание, а в общем итоге — два. Так что алгоритм работает и применительно к задаче о девяти монетах.
Зануда. Пока Простак решал задачу по моему алгоритму, я уже успел выяснить, что в случае 10 монет понадобятся минимум 3 взвешивания.
Профессор. Вы, сдается мне, попробовали применить тот же самый алгоритм? Но, быть может, для 10 монет найдется другой, более эффективный алгоритм, который позволит обойтись не более, чем двумя взвешиваниями?
Зануда. Признаюсь, я применил тот же алгоритм, что и для задач о 8 и 9 монетах. А о возможности существования другого, более эффективного алгоритма я не подумал.
Простак. Ничего не могу сказать о существовании более эффективного алгоритма для случая 10 и более монет, но в случае 9 и менее монет, я убежден, алгоритма лучшего, чем только что рассмотренный, не найти.
Если предложенная вам алгоритмическая задача показалась трудной, вернитесь к более простой задаче [...], так как ее решение поможет вам решить и эту алгоритмическую задачу.
Впереди - новые алгоритмические задачи! До новых встреч! Эта алгоритмическая задача (продолжение) [...]
Статья подготовлена по материалам книги Вадима Дунаева «Занимательная математика. Множества и отношения».
Данная задача в общей постановке имеет общее решение, и тогда она покидает поле головоломок и попадает в область математики. Я это говорю тем, кто считает математику слишком искусственной, сухой или, по меньшей мере, полем игр людей, далеких от реальной жизни. Математика занимается мирами интеллекта, а потому это – концентрированная психология, т.е. наука о самом себе или о нас с вами.
Спасибо, Вадим, за комментарий!
По-моему задача несложная. Берем для взвешивания 3 и 3 монеты. Если весы уравновешены, значит фальшивая среди оставшихся трех, иначе фальшивая среди более легкой группы монет. Таким образом мы уменьшили число подозрительных монет до трех. После этого кладем на весы по одной монете и делаем аналогичные выводы.
В общем случае для задач этого вида (когда известно, что только одна монета фальшивая) n взвешиваниями можно найти фальшивую монету, если общее число монет не более 3 в степени n.
Думаю, что более эффективного алгоритма для таких задач не существует.
Интересно, есть над чем голову полоамть.
Спасибо Вам
Пожалуйста!
Слышал эту задачку на математике, ну там в книге отдельный блок для головоломок был. Долго решали, а учительница где-то за 1 минуту решила. Если смотреть реально, то не всегда фальшивку можно определить взвешиваниями.
действительно головоломка. не профессионал и не решит какая из них фальшивая