Задача 67422
|
|
 |
Условие
Есть $N$ удавов, их пасти имеют размеры $1$ см, $2$ см, $\dots$, $N$ см. Каждый удав может заглотить яблоко любого диаметра (в см), не превосходящего размер его пасти. Но по внешнему виду нельзя определить, какая у кого пасть. Вечером смотритель может выдать каждому удаву сколько хочет яблок каких хочет размеров, и за ночь удав заглотит все те из них, что влезают ему в пасть. Какое минимальное количество яблок суммарно смотритель должен вечером выдать удавам, чтобы утром по результату он гарантированно определил размер пасти каждого удава?Решение
Если у какого-то яблока диаметр нецелый, увеличим его до ближайшего целого числа, от этого ничего не изменится: например, все удавы одинаково «реагируют» на яблоки диаметра из промежутка $(2, 3]$. Так добьёмся того, что диаметры всех яблок будут целыми.Оценка. Рассмотрим яблоки диаметра $d$, где $2\leqslant d\leqslant 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 кл., Махачкала).
