Question

У отличника Пети есть набор из 100 гирь массами 1 г, 2 г, …, 100 г, а хулиган Вовочка раздобыл наноклей, одной каплей которого можно склеить две гири в одну (чтобы склеить 3 гири в одну, понадобится 2 капли клея и т.д.), при этом сам клей ничего не весит. Вовочка хочет склеить гири так, чтобы Петя не смог из получившегося набора выбрать одну или несколько гирь общей массой 101 г. Какого наименьшего количества капель клея ему хватит?

Answer 1

Докажем ,что во всех склееных конструкциях должно оказаться в сумме не менее 50 гирь.Ясно что все гири от 1 до 100 г.Можно разбить на пары которые в сумме дают 101.(100+1),(99+2),и тд. То есть в каждой паре одно число менее или равно 50,другое более 50. Разобьем все гири на две группы :с гирями менее или равными 50,и с гирями более 50.Положим что мы убрали из первой группы n гирей.То в ней останеться 50-n гирей.Ясно что к этим 50-n гирей есть пара 50-n гирей ,находящихся в другой группе.Таким образом чтобы не осталось гирей которые в сумме дают 101.Нужно либо убрать оставшиеся 50-n гирей в этой паре.Либо 50-n гирей которые дают им пару во второй группе.То есть как бы мы ни убирали гири,чтобы не осталось гирей не находящихся в склееной конструкции и дающие в сумме 101,что было бы на руку Пете.У Ввочки в сумме в любом случае окажешься в сумме 50 гирей в склеенных конструкциях.Так как же Вовочка сделал так чтобы Петя не смог набрать 101 грамм другими способами.Сообразительный Вовочка склеил друг с другом только гири менее или равно 50,то есть из первой группы. Ясно что минимум клея у Вовочки может уйти чтобы склеить 50 гирь, если он будет клеить гири по две в отдельности,тк если он будет применять по 3 и более конструкции,то при помощи одной капли клея он расправиться только с одной гирей,склеивая рандомную гирю более чем вторая.Поэтому Вовочка склеил гири на 25 пар склеенных гирь,суммарная масса которых 51.В итоге получилось 25 конструкций массой 51.И 50 свободных гирей массой более или равно 51.Тогда минимальный вес, который может получить Петя равен:51+51=102.То есть Пете не удастся набрать 101 г. А значит Вовочка потратил 25 капель клея.