Есть классическая задача: Имеется $%N $% монет. Известно, что 1 из них фальшивая (легче настоящей). Также имеются чашечные весы без гирь, которые вмещают любое количество монет на каждой стороне весов. С помощью них можно определить относительный вес монет левой чаши весов, относительно правой(<,>,=). Необходимо определить минимальное количество взвешиваний, с помощью которых можно однозначно определить фальшивую монету. Для любого N ответом на задачу будет $%\left\lceil \log _{ 3 }{ N } \right\rceil$%. Интерес представляет общий случай, когда количество фальшивых монет равно $%M (M<=N) $% Здесь, например, дается верхняя оценка количества взвешиваний для 1, 2, 3, 4 фальшивых монет. Знаком ли кто-нибудь со стратегиями взвешиваний, с помощью которых можно гарантировать минимальное их количество для нескольких фальшивых монет? задан 8 Май '12 16:53 ipolit |