8 класс комбинаторика

Задача. Есть 10
яблок, каждое весит некоторое натуральное число грамм от 50
до 100
г. Требуется оценить, при каком наименьшем k
можно утверждать, что из этих яблок можно выбрать два непересекающихся непустых подмножества яблок, чьи веса отличаются менее чем на k
.

Решение. Прежде всего заметим, что если выбрать два пересекающихся (но не совпадающих) подмножества яблок с некоторой разностью весов, то убрав общие яблоки, получим непересекающиеся подмножества яблок с такой же разностью. Если при этом одно из подмножеств окажется пустым, то разность весов будет не меньше 50
г, а мы покажем, что можно выбрать два подмножества с меньшей разностью.

Сделаем оценку двумя способами.

Рассмотрим все возможные подмножества из четырёх яблок, для каждого подмножества посчитаем суммарный вес яблок в нём. Отметим на числовой прямой точки, соответствующие полученным числам. Всего подмножеств
?
, поэтому точки разбивают отрезок между самой левой и самой правой точками на
?
меньших отрезков (если две точки совпадают, то будем считать, что между ними отрезок длины 0
). Поскольку каждое яблоко весит от 50
до 100
г, то все точки попадут на отрезок
[?;?]
. Отсюда следует, что найдутся два подмножества, веса которых ?

Рассмотрим все возможные непустые подмножества яблок, для каждого подмножества посчитаем суммарный вес яблок в нём. Отметим на числовой прямой точки, соответствующие полученным числам. Всего непустых подмножеств
?
, поэтому точки разбивают отрезок между самой левой и самой правой точками на
?
меньших отрезков (если две точки совпадают, то будем считать, что между ними отрезок длины 0
). Поскольку каждое яблоко весит от 50
до 100
г, то все точки попадут на отрезок
[?;?]
. Отсюда следует, что найдутся два подмножества, веса которых ?

Нужно вставить пропуски вместо вопросительных знаков
.