Давайте немного разомнем свой мозг!
Перед нами 12 монет. Среди них есть одна фальшивая, которая то ли легче, то ли тяжелее настоящих. Как за 3 взвешивания на чашечных весах определить, какая из монет поддельная и в какую сторону ее вес отличается от остальных?
(Один из вариантов решения смотрите ниже.)
Подобные задачи отлично развивают навыки, необходимые для участия в олимпиадах по программированию, — логику и умение анализировать. Конечно, кроме них вам понадобится базовое владение каким-либо языком программирования и большая любовь к этому делу. А со всем остальным поможет разобраться онлайн-программа СПбГУ «Основы олимпиадного программирования».
В ней представлен обширный набор алгоритмов и структур данных, которых будет достаточно даже чтобы взять диплом призера на финальном этапе всероссийской олимпиады школьников по информатике! А высокие результаты на соревнованиях такого уровня — это не только возможность поступить в вуз без ЕГЭ, но и важная строчка в резюме при поиске работы. Именно поэтому программа рассчитана как на школьников 5–11 классов, так и на студентов.
Вариант решения:
Первым взвешиванием сравним две группы по четыре монеты.
Случай I: Первое взвешивание показало равенство.
Делаем вывод, что фальшивая монета находится среди четырех оставшихся (назовем их группой Ф). Тогда вторым взвешиванием мы сравним любые три монеты Ф с любыми тремя из первого взвешивания (они точно настоящие).
Далее возможны три варианта:
- Если весы покажут равенство, то фальшивка — оставшаяся монета из группы Ф, и третьим взвешиванием мы сравним ее с настоящей, чтобы узнать, легче она или тяжелее.
- Если три монеты группы Ф оказались легче, то третьим взвешиванием сравним друг с другом две из них. Если они равны, то фальшивая — третья оставшаяся, причем она легче настоящей. Если не равны, то фальшивая та, которая легче другой.
- Аналогичной логики придерживаемся, если монеты группы Ф оказались тяжелее настоящих. Только в этом случае и подделка не легче, а тяжелее остальных.
Случай II: Первое взвешивание показало неравенство.
Назовем 4 монеты на чаше, оказавшейся выше, легкими (Л), 4 монеты на второй чаше — тяжелыми (Т), а 4 монеты, которые не взвешивались — настоящими (Н), потому что среди них точно нет фальшивки.
Взвешиваем две группы: 1) ТННН и 2) ЛТТТ.
Опять возможны три варианта:
- Если группы равны, то фальшивая монета находится среди трех оставшихся легких, а значит, она весит меньше остальных. Сравниваем две из них, если равны, то фальшивая третья, если не равны, то фальшивая та, что легче.
- Если первая группа тяжелее, то фальшивая монета — либо единственная Т из первой группы, либо единственная Л из второй. Сравниваем Т с любой настоящей. Если Т перевесила, то она и есть подделка, если нет, то подделка — Л из второй группы.
- Если первая группа легче, то фальшивка находится среди трех монет Т из второй группы, так как в первой группе три монеты точно настоящие, а четвертая — Т (то есть если бы она была фальшивкой, то должна была бы перевесить чашу весов). Сравниваем две из трех монет Т из второй группы. Та, что окажется тяжелее — фальшивая. Если они равны — фальшивая третья из них.
