Олимпиадная задача о 8 монетах: теория алгоритмов и принцип крайнего, 7–10 класс

Обозначим монеты и их массы буквами A , B , C , D , E , F , G и H . Ясно, что если на чашки весов положены по 4 монеты, то весы не могут оказаться в равновесии. Заметим также, что если монеты разложены по чашкам поровну, то та чашка, где лежит фальшивая монета, всегда либо перевешивает (если фальшивая монета тяжелее настоящих), либо нет (если легче). Поэтому если одна и та же монета при двух взвешиваниях, когда монеты были разложены по чашкам поровну, однажды оказалась внизу, а однажды вверху, то она – настоящая.

Положим при первом взвешивании на левую чашку монеты A , B , C и D , на правую – остальные, при втором взвешивании на левой чашке пусть будут A , B , E и F , а на правой – остальные монеты. Не ограничивая общности рассуждений, можно считать, что

A + B + C + D > E + F + G + H

и

A + B + E + F > C + D + G + H.

В этом случае монеты C , D , E и F – настоящие и, если фальшивая монета тяжелее их, то это A или B , а если легче – то G или H . Третьим взвешиванием сравним массы A + G и B + H . Пусть, скажем, A + G > B + H (другой случай разбирается аналогично). Тогда монеты B и G – настоящие и четвертым взвешиванием следует сравнить A + H с B + G . Если A + H > B + G , то фальшивой и более тяжелой, чем настоящие, является монета A , а если A + H < B + G , то фальшивой и более легкой является монета H .

Ответ задачи отсутствует