Существует большая категория головоломок на взвешивание, целью которых является поиск среди некоторого количества одинаковых предметов более лёгкого или тяжёлого. Классический вариант задачи сводится к поиску фальшивой монеты среди настоящих за ограниченное количество взвешиваний на чашечных или рычажных весах без применения гирь. Познакомимся с одной из наиболее простых задач этого типа.
У вас есть 9 монет одинакового размера и веса, но одна из них фальшивая и тяжелее остальных. У вас есть весы, которые позволяют сравнивать веса двух групп монет, но нет гирь. Как за два взвешивания определить, какая монета фальшивая?
Ответ, как обычно, вы найдёте ниже.
↓
↓
↓
Итак, у нас есть 9 монет, с виду одинаковых, чашечные или рычажные весы без гирь и возможность воспользоваться весами всего два раза. Но, так как мы знаем (откуда - для задачи не имеет значения), что фальшивая монета тяжелее настоящих, то найти её всего за два взвешивания очень просто.
Разделим 9 монет на 3 группы по 3 монеты в каждой. Положим на чаши весов две группы. Если их вес одинаков, то фальшивая монета находится в третьей группе. Взвешиваем две любых монеты из третьей группы, и находим фальшивую: если взятые две монеты равны по весу - значит, фальшивой является третья, а если одна из монет перевесила - значит, она фальшивая.
Если же одна из групп на весах тяжелее другой, то фальшивая монета находится в тяжелой группе. Берем две любых монеты из тяжелой группы и взвешиваем их - здесь порядок действий тот же, что описан выше.
Несколько сложнее найти фальшивую монету, если мы не знаем её относительный вес, то есть - тяжелее она или легче настоящих. Здесь потребуется как минимум на одно взвешивание больше, но об этом мы поговорим в другой раз.