Сколькими способами можно разбить число 2017 на почти одинаковые натуральные слагаемые? Под почти одинаковыми подразумеваются слагаемые, попарно различающиеся не более чем на единичку. Порядок слагаемых не имеет значения. задан 28 Июн '17 23:37 Аллочка Шакед |
Случай, когда слагаемое всего одно, также будем включать. Если все слагаемые одинаковые, то случаев всего два в силу простоты числа 2017: это либо само 2017, либо все единицы в таком количестве. Теперь рассмотрим случай, когда у нас есть слагаемые двух типов: $%a$% и $%a+1$%. Здесь надо найти число решений уравнения $%ka+m(a+1)=2017$% в натуральных числах. Уменьшая значения переменных на единицу, приходим к уравнению $%ka+m(a+1)=2016-2a$%, где $%a$% натуральное, и $%k,m\ge0$%. Тем самым, $%1\le a\le1008$%. Для фиксированного $%a$% в указанных пределах обозначим через $%r$% остаток от деления $%2016$% на $%a$%. Тогда $%m=qa+r$% при $%q\ge0$%, и получается $%k+q(a+1)+r=\frac{2016-r}a-2$%. В частности, левая часть должна быть не меньше $%r$%, чтобы решения были, и если $%N=\frac{2016-r}a-2-r\ge0$%, то число решений уравнения в целых неотрицательных числах будет равно $%1+\frac{N}{a+1}$%. Далее применим уже компьютерный подсчёт для каждого $%a$% с последующим суммированием. У меня получился ответ $%2015$%, и вместе с двумя случаями в начале оказывается $%2017$% вариантов. Это наводит на мысль, что есть какое-то более простое решение. Это действительно так, и для любого $%n$% можно показать, что число вариантов равно $%n$%. Количество слагаемых принимает значения от $%1$% до $%n$%, и при фиксированном количестве получается ровно один вариант представления $%n$% в виде суммы $%a+\cdots+(a+1)$%, где слагаемые второго типа могут отсутствовать. Если общее число слагаемых равно $%k$%, а число слагаемых вида $%a+1$% равно $%d$%, то $%n=(k-d)a+d(a+1)=ka+d$%, то есть $%d$% сравнимо с $%n$% по модулю $%k$%. Тогда значение $%d\in\{0,1,...,k-1\}$% определяется однозначно, а с ним и значение $%a$%. отвечен 29 Июн '17 15:01 falcao @falcao, большое спасибо!
(30 Июн '17 10:32)
Аллочка Шакед
1
@Аллочка Шакед: я посмотрел задачу в усложнённом варианте. Там производящая функция в принципе выписывается (по рекуррентным формулам), но вид у неё довольно сложный, и в oeis соответствующей последовательности нет.
(30 Июн '17 12:14)
falcao
|
Есть идея, как это найти при помощи производящих функций, но реализовать её придётся уже завтра.
@falcao, здесь же намного проще всё :) Может, условие слишком отягощённо сформулировано? Попарно различающиеся не более чем на единичку - означает, что никакие два из слагаемых не отличаются более чем на 1. То есть, либо все слагаемые равны одному и тому же числу, либо каждое из слагаемых равно одному из двух чисел, одно из которых на 1 больше другого.
@Аллочка Шакед: ой, а я совсем по-другому воспринял условие, и получилась достаточно сложная задача! Её будет интересно решить в общем виде, потому что там получается очень интересная производящая функция. А если у нас слагаемые одного или двух типов, то это в самом деле очень легко -- я сейчас напишу.
@falcao, а что за сложная задача у Вас получилась? Ой, теперь и мне интересно :)
@Аллочка Шакед: я имел в виду число представлений n в виде суммы типа 4+4+5+6+6+6+7+7, где количество слагаемых каждого вида может быть любым, но значения слагаемых идут "плотно". Это дело надо будет изучить чуть позже.