Два взвешивания

В каждом из 60 мешков лежит по 20 монет: в одном мешке фальшивые, весом по 9 г, а в остальных - настоящие, весом по 10 г. В нашем распоряжении весы, показывающие вес груза в граммах. Класть на весы можно не более 100 монет. Как за два взвешивания на этих весах определить, в каком мешке фальшивые монеты?

Задача была предложена на аргентинском отборе на олимпиаду Cono Sur 2014 года и потом на 45 Уральском турнире юных математиков.

Разделим 60 мешков на четыре группы 14 мешков и оставшуюся группу из четырёх мешков.

Из первой группы из 14 мешков монет для взвешивания брать не будем. Из второй группы возьмём по одной монете. Из третьей группы возьмём по две монеты. Из четвёртой группы возьмём по три монеты. Из маленькой группы возьмём по четыре монеты.

Таким образом, для взвешивания возьмём 14*0+14*1+14*2+14*3+4*4=100 монет. Если общий вес будет ровно 100*10 г, то фальшивые монеты будут в мешке из первой группы. Если до этого веса не будет хватить 1 г, то фальшивые монеты будут в мешке из второй группы и т.д.

Таким образом, обнаружили группу, в которой не более 14 мешков, где есть мешок с фальшивыми монетами.

Если эта группа состояла из 14 мешков, то для второго взвешивания из первого мешка этой группы возьмём 0 монет, из второго мешка - 1 монету, из третьего мешка - 2 монеты, ..., из 14-го мешка возьмём 13 монет.

Всего получится, что мы возьмём 0+1+2+...+13=91 монету.

Опять же, до веса 91*10 г не будет хватать столько, сколько монет из мешка с фальшивыми монетами мы взяли. Это и определит мешок.