Метод шаров и перегородок
Ошибка.
Попробуйте повторить позже
У скольких наборов из 
натуральных чисел с суммой 
среди чисел есть равные?
Источники:
Подсказка 1
Пусть (k, k, a, b) — такой набор. Что можно сказать про a и b? Как по ним построить k?
Подсказка 2
a и b разной чётности. А каким методом привыкли искать количество способов разложить что-то в фиксированную сумму?
Подсказка 3
Воспользуемся методом шаров и перегородок! Только вот следить за тем, чтобы какие-то области были равны, сложно. Так что делать с k?
Подсказка 4
Можно разлагать 1002 в три слагаемых — 2k, a, b+1! Но как быть с тем, что нам нужны именно чётные количества?
Подсказка 5
Можно разложить сначала сумму в 501, а затем все количества умножить на 2!
Пусть 
— такой набор. Так как 
нечётно, то числа 
и 
разной чётности и между собой не равны. Пусть 
чётно. Упорядоченной парой 
набор однозначно определяется, поскольку 
вычисляется однозначно, а двух пар равных чисел в
наборе нет ввиду нечётности суммы.
Сопоставим набору строку 
. В ней все слагаемые чётны, а их сумма равна 
. По такой строке набор тоже однозначно
восстанавливается. Число таких строк можно посчитать так: выложим ряд из 
двухрублёвой монет, в который в два разных
промежутка вставлены две перегородки. Числа 
, 
и 
будут равны сумме монет (в рублях) до первой перегородки, между
перегородками и после второй перегородки соответственно. Так как между монетами 
промежутков, есть ровно 
способов выбрать
два из них.
наборов
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
