Классический тип олимпиадных задач, это задачи на взвешивания. Зачастую нужно определить фальшивую монету, или взвесить гири какой-то массы. Хотя задачи и кажутся простыми на первый взгляд, их решения часто оказываются совсем не очевидными. Следующая задача, хороший тому пример.
Условие:
В ряд лежат 100 внешне одинаковых монет. Среди них ровно 26 фальшивых, причём они лежат подряд. Настоящие монеты весят одинаково, фальшивые — не обязательно одинаково, но они легче настоящих. Как за одно взвешивание на двухчашечных весах без гирь найти хотя бы одну фальшивую монету?
Идея: Максимально точно за одно взвешивание определить в каком диапазоне находятся фальшивые монеты.
Решение:
Очевидно, что если положить все монеты на весы, то никакого внятного результата мы не получим. Это значит, что нам нужно разбить все монеты на три группы.
Разделим все 100 монет на три группы 26 (первые), 48(с 27), 26 (последние) и положим на весы, на разные чаши, группы по 26 монет. То есть у нас на весах находится 52 монеты и 48 лежат, как лежали.
Возможно три варианта:
1) Первая группа легче. Значит в ней есть фальшивая монета. Так как все 26 фальшивых монеты лежат последовательно, то последняя точно будет фальшивой.
2) Вторая легче. Значит фальшивая монета в ней и так как монеты лежат последовательно, то первая в этой группе точно фальшивая.
3) Чаши равны. Значит все 26 фальшивых монеты в группе из 48 монет. Как бы они небыли расположены, в середине обязательно будет фальшивая, можно взять 50 монету (24-ю в этой группе) и она будет фальшивой.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!
