Сколькими способами можно разбить число 2017 на почти одинаковые натуральные слагаемые? Под почти одинаковыми подразумеваются слагаемые, попарно различающиеся не более чем на единичку. Порядок слагаемых не имеет значения.

задан 28 Июн '17 23:37

1

Есть идея, как это найти при помощи производящих функций, но реализовать её придётся уже завтра.

(29 Июн '17 2:39) falcao

@falcao, здесь же намного проще всё :) Может, условие слишком отягощённо сформулировано? Попарно различающиеся не более чем на единичку - означает, что никакие два из слагаемых не отличаются более чем на 1. То есть, либо все слагаемые равны одному и тому же числу, либо каждое из слагаемых равно одному из двух чисел, одно из которых на 1 больше другого.

(29 Июн '17 11:10) Аллочка Шакед
1

@Аллочка Шакед: ой, а я совсем по-другому воспринял условие, и получилась достаточно сложная задача! Её будет интересно решить в общем виде, потому что там получается очень интересная производящая функция. А если у нас слагаемые одного или двух типов, то это в самом деле очень легко -- я сейчас напишу.

(29 Июн '17 12:14) falcao

@falcao, а что за сложная задача у Вас получилась? Ой, теперь и мне интересно :)

(29 Июн '17 12:20) Аллочка Шакед
1

@Аллочка Шакед: я имел в виду число представлений n в виде суммы типа 4+4+5+6+6+6+7+7, где количество слагаемых каждого вида может быть любым, но значения слагаемых идут "плотно". Это дело надо будет изучить чуть позже.

(29 Июн '17 15:03) falcao
10|600 символов нужно символов осталось
2

Случай, когда слагаемое всего одно, также будем включать. Если все слагаемые одинаковые, то случаев всего два в силу простоты числа 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, большое спасибо!

(30 Июн '17 10:32) Аллочка Шакед
1

@Аллочка Шакед: я посмотрел задачу в усложнённом варианте. Там производящая функция в принципе выписывается (по рекуррентным формулам), но вид у неё довольно сложный, и в oeis соответствующей последовательности нет.

(30 Июн '17 12:14) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,254
×1,102
×340
×209
×122

задан
28 Июн '17 23:37

показан
437 раз

обновлен
30 Июн '17 12:14

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

по почте:

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

по RSS:

Ответы

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

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