Задача
У Чебурашки есть набор из 36 камней массами 1 г, 2 г, ..., 36 г, а у Шапокляк есть суперклей, одной каплей которого можно склеить два камня в один (соответственно, можно склеить три камня двумя каплями и так далее). Шапокляк хочет склеить камни так, чтобы Чебурашка не смог из получившегося набора выбрать один или несколько камней общей массой 37 г. Какого наименьшего количества капель клея ей хватит, чтобы осуществить задуманное?
Решение
Пример. Склеив попарно камни с массами 1 и 18, 2 и 17, ..., 9 и 10, Шапокляк получит набор, в котором каждый камень весит от 19 до 36 г, поэтому одного камня Чебурашке будет мало, а двух – уже много.
Другой способ. Склеив попарно все камни с нечётными массами, Шапокляк получит набор, в котором все камни будут иметь чётные массы, и составить нечётную массу Чебурашка не сможет.
Оценка. Если Шапокляк использует только 8 капель, то в склейках будут участвовать не больше 16 исходных камней. Поэтому хотя бы одна из 18 пар
{1, 36}, {2, 35}, …, {18, 19} окажется "нетронутой", и Чебурашка сможет выбрать её.
Ответ
9 капель.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь