Олимпиада имени Леонарда Эйлера 2016-2017 учебный год, I тур заключительного этапа

У Зевса имеются весы, позволяющие узнавать вес положенного на них груза, и мешок со 100 монетами, среди которых есть 10- и 9-граммовые. Зевсу известно общее число $N$ 10-граммовых монет в мешке, но неизвестно, какие именно сколько весят. Он хотел бы сделать четыре взвешивания на весах и в результате гарантированно найти хотя бы одну 9-граммовую монету. При каком наибольшем $N$ это возможно? ( К. Кноп )

Комментарий/решение

Заметим, что взвесив кучку монет Зевс узнает количество $10$-граммовых монет в кучке, так как знает общий вес монет. Покажем, что максимальное такое $N=15$.

Приведем пример для $N=15$. Первым взвешиванием Зевс взвесит кучку из $50$ монет. После чего он сможет кучку из $50$ монет, где не более $7$ $10$-граммовых монет, взяв для этого либо те монеты которые взвешивал, либо те которые не взвешивал. Следующим ходом разделив эту кучку на две по $25$ монет, Зевс сможет найти кучку из $25$ монет в которой не более $3$ $10$-граммовых. Далее убрав одну монету из кучку и $25$ монет, и поделив ее на две кучки по $12$ монет, Зевс найдет кучку из $12$ монет, где не более одной $10$-граммовой монеты. Повторяя операцию еще раз, Зевс найдет кучку из $6$ монет, где нет ни одной $10$-граммовой.

Покажем, что $N < 16$. Пусть это не так. Заметим, что мы можем сделать монеты $10$-граммовыми так, чтобы после первого взвешивания Зевс не мог найти кучку с менее чем восьмью $10$-граммовыми монетами. Если он взвесил менее восьми монет первым ходом, то пусть они все будут $10$-граммовые. Аналогично поступаем и на следующем взвешивании Зевса, получаем либо во всех кучках не менее четырех $10$-граммовых монет, либо в кучке менее чем из четырех монет все $10$-граммовые. Несложно понять, что повторив это еще два раза, получим что после $4$-ого взвешивания во всех кучках не менее одной $10$-граммовой монеты, и значит не может однозначно определить хотя бы одну $9$-граммовую монету.