Поиск фальшивой монеты

Задача

Даны 13 монет, из которых одна фальшивая. При этом неизвестно, легче она или тяжелее настоящих. Требуется найти её за 3 взвешивания на чашечных весах без гирь.

Появляясь время от времени на различных форумах, эта задача вызывает длительные бурные дискуссии, иногда даже с переходом на личности. И неудивительно, ведь ещё во время войны немцы, забросив эту задачу британским учёным, парализовали их работу на несколько месяцев.

Интересное решение этой задачи, которое основывается на использовании троичной системы счисления, можно найти на problems.ru. Мы же представим другое красивое решение, предложенное Кузнецовым С.Т., преподавателем Государственной лётной академии Украины.

Решение

Перенумеруем монеты: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.
Первое взвешивание проведём так:
I. 1, 2, 3, 4 ? 5, 6, 7, 8
Для второго взвешивания уберём с первой чаши 3 монеты 1, 2, 3, перенесём туда со второй чаши монеты 5, 6, 7 и поместим на вторую чашу монеты 9, 10, 11.
II. 5, 6, 7, 4 ? 9, 10, 11, 8.
Какими могут быть результаты первых двух взвешиваний? (Будем обозначать равновесие знаком =, а отклонение в ту или иную сторону – знаками < или >)

(=, =)
Если оба раза равновесие не нарушилось, то фальшивых монет на весах не было. Следовательно, это или 12 или 13. в таком случае, третьим взвешиванием может быть
III. 1 ? 12
При равенстве фальшивая монета – 13 (заметьте, что нас не просили указать её вес, а только найти), при неравенстве – 12.

(=, >)
Неравенство во втором взвешивании могли внести только новые введённые монеты: 9, 10 или 11, причём точно известно, что фальшивая монета легче настоящей. Тогда третьим взвешиванием сравниваем
III. 9 ? 10
Фальшивой будет более лёгкая, а при равенстве – монета 11.

Случай (=, <) рассматривается аналогично, с той поправкой, что фальшивая тяжелее настоящей.

(<, =)
Монеты, нарушавшие равновесие в первом взвешивании, были убраны с весов во втором, следовательно, фальшивая среди 1, 2, 3 и она легче настоящей. За одно взвешивание, сравнив
III. 1 ? 2
Фальшивой монетой будет более лёгкая, а при равновесии – монета 3.

(<, <)
После перекладываний монет положение чаш не изменилось. Значит или монета 4 лёгкая, или монета 8 тяжёлая. Сравнением
III. 1 ? 4
фальшивая монета находится. Если левая чаша перетянет, то это 4, при равновесии – это 8.

(<, >)
Так изменить положение чаш весов могло только перекладывание монет 5, 6, 7 с правой чаши на левую. При этом, поскольку в первом взвешивании более тяжёлой была правая чаша, а во втором –левая, то фальшивая монета тяжелее настоящей и её опять-таки можно найти одним взвешиванием.

Случаи (>, <), (>, =), (>, >) рассматриваются аналогично, отличаясь лишь весом фальшивой монеты. Поскольку разобраны все варианты, задача решена.