Аддитивная комбинаторика
Ошибка.
Попробуйте повторить позже
В Тридесятом царстве в ходу были монеты в несколько копеек, не менее 
разных достоинств (сейчас уже никто не знает, сколько их
точно было и каких достоинств). Какое наименьшее число тридесятских монет должен найти археолог, чтобы быть уверенным, что среди
них заведомо есть ровно 
монет, в сумме дающих целое число рублей?
Подсказка 1
Давайте переформулируем задачу на язык остатков по модулю 100. Для начала попробуйте придумать пример. Попробуйте использовать довольно мало различных номиналов.
Подсказка 2
Можно взять 99 монет номиналом 1 и 99 монет номиналом 0. Тогда, какие бы сто монет мы не взяли, в сумме давать целое число рублей они не будут. Будем доказывать оценку на 199. Теперь давайте обобщим задачу: пусть у нас есть 2n - 1 остаток по модулю n, и мы хотим из них выбрать n, которые в сумме дают 0 по модулю n. Как такое можно доказывать?
Подсказка 3
Правильно! По индукции! Но простая индукция тут может не пройти. Поэтому по чему индукцию тут лучше вести, учитывая, что у нас какие-то остатки по модулю?
Подсказка 4
Ага! Давайте у нас будет индукция по простым делителям числа n. Но для начала надо доказать базу, то есть нашу задачу в случае простого n = p. Для этого давайте посмотрим на наши остатки и отсортируем их a₁ ≤ a₂ ≤ ... ≤ a_{2p-1}. Пойдем от противного. Попробуйте разбить наши остатки на пары(кроме может одного) так, чтобы в каждой паре гарантировано было два различных остатка.
Подсказка 5
Давайте например рассмотрим a_i и a_{i + p - 1} для i от 1 до p - 1. Они не могут быть равны, так как иначе у нас есть p одинаковых остатков. Давайте эти пары обозначим за множества A_i. А множество A_p будет содержать только a_{2p - 1}. Какую теорему осталось применить?
Подсказка 6
Правильно! Теорему Коши-Дэвенпорта, из которой сразу следует, что |A₁ + ... A_p| = p. То есть противоречие. Базу доказали. Давайте докажем переход. Пусть n = pm. Попробуйте набрать каких-то 2m - 1 набора остатков так, чтобы можно превратить их в переменные и применить предположение. Какое еще условие на эти наборы нужно?
Подсказка 7
Точно! Нам нужно, чтобы сумма в каждом наборе делилась еще на p. Какие тогда наборы нужно брать, учитывая базу индукции?
Переформулируем задачу. Будем считать, что у нас номиналы копеек это соответственные остатки по модулю 
и нам нужно выбрать
остатков сумма которых делится на 
Заметим, что 
монет не хватит так, как нам могут выпасть 
монет с остатком 
и 
монет с остатком 
Докажем, что для любого натурального 
нам достаточно вытащить 
монету, чтоб
можно было выбрать 
монет с суммой, которая делится на 
Индукцией по количеству простых множителей числа
База индукции. Пусть 
— простое число. Пронумеруем элементы последовательности в порядке возрастания:
Если 
при каком-нибудь 
то 
(в 
и мы нашли то, что
требуется. В противном случае пусть 
при 
Последовательно применяя теорему Коши —
Дэвенпорта, заключаем, что 
Следовательно, каждый элемент 
в том числе 
представим в виде
суммы из 
слагаемых.
Докажем индукционный переход. Пусть 
где 
— простое, и пусть 
— данная последовательность. По
утверждению задачи для простых 
(база индукции), мы можем последовательно выбирать наборы из 
чисел, сумма которых делится на
Так мы сумеем выбрать 
различных наборов 
Действительно, если 
набора уже выбрано, то количество
оставшихся элементов не меньше 
Для каждого 
положим 
По
предположению индукции эта последовательность содержит подпоследовательность с суммой 
из 
элементов. Это дает нам требуемое
подмножество из 
элементов с суммой, делящейся на 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
