Леонард Эйлер атындағы олимпиада,2016-2017 оқу жылы, қорытынды кезеңнің 1-ші туры

Зевсте қойылған салмақтың массасын анықтап беретін таразы мен ішінде 100 тиыны бар қап бар. Қаптың ішінде массасы 10 және 9 грамдық тиындар бар. Зевске каптың ішінде қанша 10 грамдық $N$ тиын бар екені белгілі, бірақ қай тиын қандай салмақты екені белгісіз. Ол төрт өлшем жасау арқылы кепілді түрде қандай да бір 9 грамдық тиынды тапқысы келеді. $N$-нің қандай ең үлкен мәнінде ол 9-грамдық тиынды таба алады? ( К. Кноп )

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

Заметим, что взвесив кучку монет Зевс узнает количество $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$-граммовую монету.