Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите пожалуйста решить

Chus Bdjj Ученик (86), на голосовании 5 месяцев назад
Заполните пропуски так, чтобы получилась лучшая оценка, которую можно получить при таком решении.

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

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

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

Рассмотрим все возможные подмножества из четырёх яблок, для каждого подмножества посчитаем суммарный вес яблок в нём. Отметим на числовой прямой точки, соответствующие полученным числам. Всего подмножеств ПРОПУСК, поэтому точки разбивают отрезок между самой левой и самой правой точками на ВЫБРАТЬ ( 209 или 210 или 211 ) меньших отрезков (если две точки совпадают, то будем считать, что между ними отрезок длины 0). Поскольку каждое яблоко весит от 50 до 100г, то все точки попадут на отрезок ВЫБРАТЬ
( [ 50,100] или [ 200, 300] или [200,400] или [50, 400] ). Отсюда следует, что найдутся два подмножества, веса которых
ВЫБРАТЬ ( совпадают или отличаются не более чем на 1г или отличаются не более чем на 2г или отличаются не более чем на 3г ).

Рассмотрим все возможные непустые подмножества яблок, для каждого подмножества посчитаем суммарный вес яблок в нём. Отметим на числовой прямой точки, соответствующие полученным числам. Всего непустых подмножеств ПРОПУСК, поэтому точки разбивают отрезок между самой левой и самой правой точками на ВЫБРАТЬ ( 1022 или 1023 или 1024 ) меньших отрезков (если две точки совпадают, то будем считать, что между ними отрезок длины 0 ). Поскольку каждое яблоко весит от 50 до 100г, то все точки попадут на отрезок ВЫБРАТЬ ( [ 50,1000] или [ 50,500 ] или [ 500,1000 ]. Отсюда следует, что найдутся два подмножества, веса которых ВЫБРАТЬ ( совпадают или отличаются не более чем на 1г или отличаются не более чем на 2г или отличаются не более чем на 3г ).
Голосование за лучший ответ
Samir Mayer Ученик (150) 6 месяцев назад
какой дурак это будет читать
Samir MayerУченик (150) 6 месяцев назад
я
Похожие вопросы