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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Вадим Дунаев говорит:

    Данная задача в общей постановке имеет общее решение, и тогда она покидает поле головоломок и попадает в область математики. Я это говорю тем, кто считает математику слишком искусственной, сухой или, по меньшей мере, полем игр людей, далеких от реальной жизни. Математика занимается мирами интеллекта, а потому это – концентрированная психология, т.е. наука о самом себе или о нас с вами.

  • По-моему задача несложная. Берем для взвешивания 3 и 3 монеты. Если весы уравновешены, значит фальшивая среди оставшихся трех, иначе фальшивая среди более легкой группы монет. Таким образом мы уменьшили число подозрительных монет до трех. После этого кладем на весы по одной монете и делаем аналогичные выводы.
    В общем случае для задач этого вида (когда известно, что только одна монета фальшивая) n взвешиваниями можно найти фальшивую монету, если общее число монет не более 3 в степени n.
    Думаю, что более эффективного алгоритма для таких задач не существует.

  • Владимир говорит:

    Интересно, есть над чем голову полоамть.
    Спасибо Вам

  • Павел говорит:

    Слышал эту задачку на математике, ну там в книге отдельный блок для головоломок был. Долго решали, а учительница где-то за 1 минуту решила. Если смотреть реально, то не всегда фальшивку можно определить взвешиваниями.

  • Назгуль говорит:

    действительно головоломка. не профессионал и не решит какая из них фальшивая

Ответить на Владимир Отмена ответа

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>