Задача 67422
|
|
 |
Условие
Есть $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$ яблок.Замечания
Оказывается, тот же самый набор яблок можно раздать удавам как угодно, лишь с одним условием: не давать одинаковые яблоки одному и тому же удаву. В самом деле, если найдётся удав, съевший яблоко диаметра $N$, то его пасть размера $N$. Иначе такая пасть у удава, не получившего такого яблока. Среди остальных удавов яблоками диаметра $N$ – 1 точно так же находится пасть размера $N$ – 1 и так далее. Оставшийся в конце удав будет иметь пасть размера 1.Среди школьников это заметил, например, Гаджиев Низам (10 кл., Махачкала).
