Минимум яблок для удавов: задача теории алгоритмов (8–11 класс, Казицы

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