Обозначим для любого конечного непустого множества натуральных чисел $%S$% сумму его элементов через $% \sigma S$%. Пусть $%A= \big\{ a_{1}, a_{2}, ..., a_{11} \big\}$% — множество из таких натуральных чисел, что $% a_{1} < a_{2} < ... < a_{11}$% и для любого натурального числа $%n \leq 1900$% найдется подмножество $%S$% из $%A$%, что $% \sigma S=n$%. Найдите наименьшее возможное значение $% a_{10} $%.

задан 26 Дек '14 15:57

изменен 26 Дек '14 16:05

10|600 символов нужно символов осталось
2

Хорошая задача, но она тут как-то затерялась.

Пусть $%S=a_1+a_2+\cdots+a_{10}$%. Утверждается, что $%S$% должно быть не меньше половины от 1900. Доказательство: предположим, что $%S < 950$%. Тогда в случае $%a_{11}\le950$% общая сумма всех чисел будет строго меньше 1900, и это число мы представить не сможем. Если же $%a_{11} > 950$%, то число 950 окажется не представимо в виде суммы. Если мы не берём $%a_{11}$%, то сумма оказывается меньше нужной, а если берём, то больше.

Теперь мы знаем, что $%a_1+a_2+\cdots+a_{10}\ge950$% в качестве необходимого условия. Поэтому, чтобы $%a_{10}$% было как можно меньше, имеет смысл сделать сумму остальных слагаемых как можно больше. При этом возникают такие ограничения: ясно, что $%a_1=1$% (иначе 1 не представить), $%a_2=2$% (2 как сумма одинаковых слагаемых не представима), и далее $%a_3$% равно 3 или 4. Не может быть $%a_3 > 4$%, так как в этом случае мы не набираем сумму, равную 4. Это значит, что $%a_3\le4$%. При этом $%a_1+a_2+a_3\le7$%, и из этого следует неравенство $%a_4\le8$% (в противном случае 8 не представить как сумму). По индукции получается, что $%a_n\le2^{n-1}$% при всех $%n$%, а также $%a_1+a_2+\cdots+a_n\le2^n-1$%.

Из сказанного ясно, что $%a_1+a_2+\cdots+a_9\le511$%. Следовательно, $%a_{10}\ge950-511=439$%. Осталось показать, что значение $%a_{10}=439$% возможно. Для этого берём все предыдущие числа в виде степеней двойки: 1, 2, 4, ... , 256. Из них составляются все суммы от 0 до 511 включительно (включая случай пустой суммы). Тогда вместе с числом 439 получается диапазон от 439 до 950 включительно. Это значит, что любую сумму от 0 до 950 включительно мы можем получить при помощи первых десяти чисел. Останется положить $%a_{11}=950$%, и тогда все суммы от 1 до 1900 набираются.

ссылка

отвечен 17 Янв '15 17:49

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,770

задан
26 Дек '14 15:57

показан
673 раза

обновлен
17 Янв '15 17:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru