Заполните пропуски так, чтобы получилась лучшая оценка, которую можно получить при таком решении.
Задача. Есть 10 яблок, каждое весит некоторое натуральное число грамм от 50 до 100 г. Требуется оценить, при каком наименьшем k можно утверждать, что из этих яблок можно выбрать два непересекающихся непустых подмножества яблок, чьи веса отличаются менее чем на k.
Решение. Прежде всего заметим, что если выбрать два пересекающихся (но не совпадающих) подмножества яблок с некоторой разностью весов, то убрав общие яблоки, получим непересекающиеся подмножества яблок с такой же разностью. Если при этом одно из подмножеств окажется пустым, то разность весов будет не меньше 50 г, а мы покажем, что можно выбрать два подмножества с меньшей разностью.
Сделаем оценку двумя способами.
Рассмотрим все возможные подмножества из четырёх яблок, для каждого подмножества посчитаем суммарный вес яблок в нём. Отметим на числовой прямой точки, соответствующие полученным числам. Всего подмножеств ?(), поэтому точки разбивают отрезок между самой левой и самой правой точками на ?(209, 210, 211) меньших отрезков (если две точки совпадают, то будем считать, что между ними отрезок длины 0). Поскольку каждое яблоко весит от 50 до 100 г, то все точки попадут на отрезок ?([50; 100], [200; 300], [200; 400], [50; 1000]). Отсюда следует, что найдутся два подмножества, веса которых ?(совпадают; отличаются на не более, чем 1г; отличаются на не более, чем 2г; отличаются на не более, чем 3г)
Рассмотрим все возможные непустые подмножества яблок, для каждого подмножества посчитаем суммарный вес яблок в нём. Отметим на числовой прямой точки, соответствующие полученным числам. Всего непустых подмножеств ?(), поэтому точки разбивают отрезок между самой левой и самой правой точками на ?(1022, 1023, 1024) меньших отрезков (если две точки совпадают, то будем считать, что между ними отрезок длины 0). Поскольку каждое яблоко весит от 50 до 100 г, то все точки попадут на отрезок ?([50; 1000], [50; 500], [500; 1000]). Отсюда следует, что найдутся два подмножества, веса которых ?(совпадают; отличаются на не более, чем 1г; отличаются на не более, чем 2г; отличаются на не более, чем 3г).
Нужно выбрать что то одно из скобок где в перед скобкой стоит ?. А там где скобка пустая нужно указать число.