Разделы 
Дополнительно
Задача по математике - 1686
2019-01-20 
В наборе из 17 внешне одинаковых монет две фальшивых, отличающихся от остальных по весу. Известно, что суммарный вес двух фальшивых монет вдвое больше веса настоящей. Всегда ли можно ли определить пару фальшивых монет, совершив 5 взвешиваний на чашечных весах без гирь? (Определить, какая из фальшивых тяжелее, не требуется).
Решение:
Пусть разность весов фальшивых монет меньше, чем вес настоящей. Тогда во взвешиваниях имеет смысл сравнивать лишь равные количества монет. Предположим, что требуемый алгоритм существует.
Выпишем для каждой последовательности результатов взвешиваний, которая может получиться в нашем алгоритме, единственную пару фальшивых монет, при которой эта последовательность получается. Заметим, что если в последовательности есть хотя бы одно взвешивание, при котором нет равновесия, то мы можем определить, какая из фальшивых монет тяжелее настоящей. Действительно, если во взвешивании участвует одна фальшивая монета, то это определяется очевидным образом. Если же участвуют обе, то они находятся на разных чашах весов (иначе весы в равновесии), и монета на перевесившей чаше тяжелее.
В таком случае, если в нашей паре монет поменять две фальшивые местами, то получится другая последовательность взвешиваний. Поэтому всем парам, кроме, быть может, одной (при которой весы все время в равновесии) соответствует по 2 последовательности. Всего может быть $ \frac {17 \cdot 16}{2} = 136$ пар, поэтому число последовательностей не меньше $2 \cdot 136 - 1 = 271$, но их не больше $3^5 - 243 < 271$. Противоречие.
Ответ. Не всегда.
В наборе из 17 внешне одинаковых монет две фальшивых, отличающихся от остальных по весу. Известно, что суммарный вес двух фальшивых монет вдвое больше веса настоящей. Всегда ли можно ли определить пару фальшивых монет, совершив 5 взвешиваний на чашечных весах без гирь? (Определить, какая из фальшивых тяжелее, не требуется).
Решение:
Пусть разность весов фальшивых монет меньше, чем вес настоящей. Тогда во взвешиваниях имеет смысл сравнивать лишь равные количества монет. Предположим, что требуемый алгоритм существует.
Выпишем для каждой последовательности результатов взвешиваний, которая может получиться в нашем алгоритме, единственную пару фальшивых монет, при которой эта последовательность получается. Заметим, что если в последовательности есть хотя бы одно взвешивание, при котором нет равновесия, то мы можем определить, какая из фальшивых монет тяжелее настоящей. Действительно, если во взвешивании участвует одна фальшивая монета, то это определяется очевидным образом. Если же участвуют обе, то они находятся на разных чашах весов (иначе весы в равновесии), и монета на перевесившей чаше тяжелее.
В таком случае, если в нашей паре монет поменять две фальшивые местами, то получится другая последовательность взвешиваний. Поэтому всем парам, кроме, быть может, одной (при которой весы все время в равновесии) соответствует по 2 последовательности. Всего может быть $ \frac {17 \cdot 16}{2} = 136$ пар, поэтому число последовательностей не меньше $2 \cdot 136 - 1 = 271$, но их не больше $3^5 - 243 < 271$. Противоречие.
Ответ. Не всегда.
