Задача
Есть $N$ удавов, их пасти имеют размеры 1 см, 2 см, ..., $N$ см. Каждый удав может заглотить яблоко любого диаметра (в см), не превосходящего размер его пасти. Но по внешнему виду нельзя определить, какая у кого пасть. Вечером смотритель может выдать каждому удаву сколько хочет яблок каких хочет размеров, и за ночь удав заглотит все те из них, что влезают ему в пасть. Какое минимальное количество яблок суммарно смотритель должен вечером выдать удавам, чтобы утром по результату он гарантированно определил размер пасти каждого удава?
Решение
Если у какого-то яблока диаметр нецелый, увеличим его до ближайшего целого числа, от этого ничего не изменится: например, все удавы одинаково «реагируют» на яблоки диаметра из промежутка (2, 3]. Так добьёмся того, что диаметры всех яблок будут целыми. Оценка. Рассмотрим яблоки диаметра $d$, где 2 ≤ $d$ ≤ $N$. Пусть таких яблок не дадут каким-то двум удавам. Пасти этих удавов могут оказаться размером $d−1$ и $d$. Оба удава съедят все меньшие яблоки и оставят все бо́льшие, поэтому этих удавов не различить. Значит, для каждого $d$ от 2 до $N$ включительно яблок диаметра $d$ требуется хотя бы $N$ – 1, а всего яблок тогда нужно хотя бы $(N-1)^2$. Пример. Дадим каждому удаву, кроме последнего, яблоки всех диаметров от 2 до $N$ включительно. Получив такой набор, удав выдаст размер своей пасти: он равен максимальному радиусу съеденного яблока или 1, если ни одно яблоко не съедено. Размер пасти у последнего удава определим методом исключения.
Ответ
$(N-1)^2$ яблок.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь