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