|
|
 |
Условие
В наборе из 17 внешне одинаковых монет две фальшивых, отличающихся от остальных по весу. Известно, что суммарный вес двух фальшивых монет вдвое больше веса настоящей. Всегда ли можно ли определить пару фальшивых монет, совершив пять взвешиваний на чашечных весах без гирь? (Определять, какая из фальшивых монет тяжелее, не требуется.)
Решение
Пусть разность весов фальшивых монет меньше чем вес настоящей. Тогда во взвешиваниях имеет смысл сравнивать лишь равные количества монет.
Предположим, что требуемый алгоритм существует. Выпишем для каждой последовательности результатов взвешиваний, которая может получиться в нашем алгоритме, единственную пару фальшивых монет, при которой эта последовательность получается. Заметим, что если в последовательности есть хотя бы одно взвешивание, при котором нет равновесия, то мы можем определить, какая из фальшивых монет тяжелее настоящей. Действительно, если во взвешивании участвует одна фальшивая монета, то это определяется очевидным образом. Если же участвуют обе, то они находятся на разных чашах весов (иначе весы в равновесии), и монета на перевесившей чаше тяжелее.
В таком случае, если в нашей паре монет поменять две фальшивые местами, то получится другая последовательность взвешиваний. Поэтому всем парам, кроме, быть может, одной (при которой весы все время в равновесии) соответствует по две последовательности.
Всего может быть 17·16 : 2 = 136 пар, поэтому число последовательностей не меньше 2·136 – 1 = 271, но их не больше 35 = 243 < 271. Противоречие.
Ответ
Не всегда.
