Задача C6 из ЕГЭ
Решал тут намедни в одном сообществе задачку из Второй волны ЕГЭ 10 июля 2012 г.: http://eek.diary.ru/p178532679.htm?from=60
С6.1 Число S таково, что для любого представления S в виде суммы положительных слагаемых, каждое из которых не превосходит 1, эти слагаемые можно разделить на две группы так, что каждое слагаемое попадет только в одну группу и сумма слагаемых в каждой группе не первосходит 20.
а) Может ли число S быть равным 40?
б) Может ли число S быть больше 39 1/21?
в) Найдите максимально возможное значение S.
Попробуйте сначала решить сами, а потом посмотрите мое решение.
Решение
Пусть некоторое число S представлено в виде суммы положительных слагаемых, каждое из которых не превосходит единицы. Эти слагаемые можно разбить на две группы различным образом. Выберем среди них оптимальное, т. е. такое, чтобы бОльшая сумма в группе была минимальна (или, что то же самое, чтобы разница между суммами в группах была минимальна). Если эта сумма не превышает 20, то представление числа S в виде слагаемых будем называть хорошим, в противном случае представление будем называть плохим. По условию задачи число S не имеет плохих представлений.
а), b) Число, большее чем 39 1/21=820/21 имеет плохое представление в виде сорока одного (41) одинакового слагаемого. Минимизируя наибольшую сумму мы вынуждены будем взять 21 слагаемое. Их сумма при этом превысит 820/(21*41) * 21 = 20. Таким образом, число большее чем 39 1/21 не может быть числом S.
в) Пусть S <= 39 1/21 = 820/21. Будем доказывать, что плохих представлений этого числа нет. Предположим противное, т. е. такое представление существует. Возьмем для этого представления оптимальное разбиение и обозначим через M1 и M2 большую и меньшую суммы для данного разбиения. В этих обозначениях мы можем записать:
M1 >= M2, M1 > 20 и M1 + M2 = S.
Далее, поскольку M1 > 20, а каждое слагаемое не превышает единицы, то число слагаемых не меньше 21. В то же время минимальное среди этих слагаемых не может быть меньше разности между M1 и M2, в противном случае минимальное слагаемое можно было бы перенести из большей суммы в меньшую, модуль разности между M1 и M2 уменьшился бы и тем самым рассматриваемое разбиение оказалось бы неоптимальным. Запишем это так:
M1 - M2 <= min или M1 <= M2 + min = S - M1 + min.
Но, поскольку число слагаемых в M1 не меньше 21, то min <= M1/21, и неравенство можно продолжить так:
M1 <= S - M1 + M1/21.
Решая это неравенство, получаем M1 <= 21/41 S <= 21/41 * 820/21 = 20, что противоречит предположению, что M1 > 20.
Таким образом, максимально возможное значение S равно 39 1/21. Мы доказали даже несколько больше: S может принимать любое положительное значение, не превышающее 39 1/21.
С6.1 Число S таково, что для любого представления S в виде суммы положительных слагаемых, каждое из которых не превосходит 1, эти слагаемые можно разделить на две группы так, что каждое слагаемое попадет только в одну группу и сумма слагаемых в каждой группе не первосходит 20.
а) Может ли число S быть равным 40?
б) Может ли число S быть больше 39 1/21?
в) Найдите максимально возможное значение S.
Попробуйте сначала решить сами, а потом посмотрите мое решение.
Решение
Пусть некоторое число S представлено в виде суммы положительных слагаемых, каждое из которых не превосходит единицы. Эти слагаемые можно разбить на две группы различным образом. Выберем среди них оптимальное, т. е. такое, чтобы бОльшая сумма в группе была минимальна (или, что то же самое, чтобы разница между суммами в группах была минимальна). Если эта сумма не превышает 20, то представление числа S в виде слагаемых будем называть хорошим, в противном случае представление будем называть плохим. По условию задачи число S не имеет плохих представлений.
а), b) Число, большее чем 39 1/21=820/21 имеет плохое представление в виде сорока одного (41) одинакового слагаемого. Минимизируя наибольшую сумму мы вынуждены будем взять 21 слагаемое. Их сумма при этом превысит 820/(21*41) * 21 = 20. Таким образом, число большее чем 39 1/21 не может быть числом S.
в) Пусть S <= 39 1/21 = 820/21. Будем доказывать, что плохих представлений этого числа нет. Предположим противное, т. е. такое представление существует. Возьмем для этого представления оптимальное разбиение и обозначим через M1 и M2 большую и меньшую суммы для данного разбиения. В этих обозначениях мы можем записать:
M1 >= M2, M1 > 20 и M1 + M2 = S.
Далее, поскольку M1 > 20, а каждое слагаемое не превышает единицы, то число слагаемых не меньше 21. В то же время минимальное среди этих слагаемых не может быть меньше разности между M1 и M2, в противном случае минимальное слагаемое можно было бы перенести из большей суммы в меньшую, модуль разности между M1 и M2 уменьшился бы и тем самым рассматриваемое разбиение оказалось бы неоптимальным. Запишем это так:
M1 - M2 <= min или M1 <= M2 + min = S - M1 + min.
Но, поскольку число слагаемых в M1 не меньше 21, то min <= M1/21, и неравенство можно продолжить так:
M1 <= S - M1 + M1/21.
Решая это неравенство, получаем M1 <= 21/41 S <= 21/41 * 820/21 = 20, что противоречит предположению, что M1 > 20.
Таким образом, максимально возможное значение S равно 39 1/21. Мы доказали даже несколько больше: S может принимать любое положительное значение, не превышающее 39 1/21.