Решение задачи 16.
Определим вначале ситуации, когда можно можно определить фальшивую монету за одно взвешивание. Это возможно сделать, если:
есть две неизвестные монеты и одна стандартная (заведомо не
фальшивая);
есть три неизвестные монеты и известен вес фальшивой монеты
(т.е. информация о том, больше или меньше ее вес).
Алгоритм:
Разобьем 13 монет на 3 части: 4,4 и 5 монет.
1. вес монет в первых частях равны. Тогда это стандартные монеты. Будем обозначать их через с а возможные фальшивые монеты через ф.
2-е взвешивание
ссс и ффф (остались неопределенными только фф из третьей части).
Если веса равны, то фальшивая среди оставшихся двух. Если
нет, то среди взвешенных трех, но ее вес известен.
2. Веса монет в первых частях не равны. Тогда монеты из третьей части - стандартные монеты. Определим взвешенные монеты как т (тяжелые) или л (легкие) в зависимости от результатов взвешивания.
2-е взвешивание
ссст и тттл
Если веса равны, то фальшивая среди оставшихся трех легких. Если нет, то возможны следующие ситуации.
2.1. ссст легче тттл. Понятно, что фальшивая монета находится среди трех тяжелых монет.
2.2. ссст тяжелее тттл. Понятно, что фальшивая монета находится среди двух монет: тяжелой монеты слева или легкой справа.
Поэтому фальшивую монету можно определить за одно оставшееся
взвешивание.
|
