Олимпиадная задача: проверки фальшивых монет в коллекции Коли, теория алгоритмов
Задача
В Колиной коллекции есть четыре царские золотые пятирублевые монеты. Коле сказали, что какие-то две из них фальшивые. Коля хочет проверить (доказать или опровергнуть), что среди монет есть ровно две фальшивые. Удастся ли ему это сделать с помощью двух взвешиваний на чашечных весах без гирь? (Фальшивые монеты одинаковы по весу, настоящие тоже одинаковы по весу, но фальшивые легче настоящих.)
Решение
Пусть сначала Коля взвесит по две монеты. Рассмотрим два случая.
1) Весы в равновесии. Коля может сравнить веса двух монет, лежащих (при первом взвешивании) на одной чашке. Если их веса равны, то равны веса всех монет, то есть фальшивых либо 0, либо 4. Если же веса не равны, то ровно одна из них фальшивая. Но тогда и на другой чашке ровно одна фальшивая, то есть фальшивых монет ровно две.
2) Веса чашек не равны. Тогда фальшивых монет либо одна, либо две (в этом случае они лежат на одной чашке), либо три. Коля может взять по монете с каждой чашки и поменять их местами. Если фальшивых монет две, весы уравновесятся, в противном случае – не уравновесятся.
В любом случае проверка Коле удастся.
Ответ
Удастся.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь