Новогодняя

[Руст]

Пусть

$$S_n=\sum_{i=1}^{2009} x_i^n,$$

где $x_i$ все корни уравнения:
$x^{2009}=ax+b$.
1. Вычислить $S_{2008*2009}$, вычислить $S_n$ (в виде суммы $[\frac{n}{2008*2009}]+1$ членов).
2. Пусть a,b - целые и p большой простой делитель n (здесь простой делитель n называем большим, если n<2009p). Доказать, что $S_n$ целое и делится на p. В частности, если n простое, то $n|S_n$.

[juna]

Руст писал(а):

1. Вычислить $S_{2008*2009}$

Если не ошибся, то $2008\cdot a^{2009}+b^{2008}$

[Профессор Снэйп]

Руст писал(а):

Пусть

$$S_n=\sum_{i=1}^{2009} x_i^n,$$

где $x_i$ все корни уравнения:
$x^{2009}=ax+b$.

Сумма берётся по всем $i$ от $1$ до $2009$, то есть суммируются ровно $2009$ чисел. Между тем у уравнения возможны кратные корни, в связи с чем количество корней может быть меньше, чем $2009$. Я понимаю это так, что корни суммируются с учётом их кратности, то есть каждый корень суммируется столько раз, какова его кратность. Если я неправильно понял условие, то пусть автор задачи меня поправит.

Руст писал(а):

Вычислить $S_{2008*2009}$

Вероятно, звёздочка обозначает здесь умножение. То есть надо вычислить $S_{2008 \cdot 2009}$. Если нет, то опять же пусть автор меня поправит.

Итак, пусть $n = 2008 \cdot 2009$ и $e$ --- примитивный корень $n$-ой степени из $1$. Пусть также $f(x) = x^{2009} - ax - b$. Пусть теперь

$$ g(y) = f(e^{-1}y) \cdot f(e^{-2}y) \cdot \ldots \cdot f(e^{-n}y) $$

Видно, что $y$ является корнем $g$ тогда и только тогда, когда для некоторых $i \in [1,2009]$ и $j \in [1,n]$ справедливо $y=x_ie^j$, причём кратность каждого такого корня равна кратности корня $x_i$ при $x_i \neq 0$ и кратности $x_i$, умноженной на $n$, при $x_i = 0$. Это значит, что

$$ g(y) = (y^n-x_1^n) \cdot \ldots \cdot (y^n - x_{2009}^n) \cdot \prod_{j=1}^n e^{-j} $$

Заметим, что $\prod_{j=1}^n e^{-j} = e^{-n(n+1)/2} = -1$. Отметим также, что $\{ e^{-1}, \ldots, e^{-n} \} = \{ e^1, \ldots, e^n \}$ и, как следствие этого,

$$ g(y) = f(ey) \cdot f(e^2y) \cdot \ldots \cdot f(e^ny) = \prod_{j=1}^n (e^{2009j}y^{2009} - ae^jy - b). $$

Пусть теперь $h$ --- такой многочлен, что $g(y) = h(y^n)$, то есть

$$ h(z) = -(z-x_1^n) \cdot \ldots \cdot (z-x_{2009}^n). $$

По теореме Виета число $S_n$ равно коэффициенту многочлена $h(z)$ при $z^{2008}$, то есть коэффициенту многочлена $g(y)$ при $y^{2008n}$. Вычислим этот коэффициент.

Имеем $2008n = 2008^2 \cdot 2009$. Пусть $\mathcal{S}$ --- множество всех таких троек $\langle A, B, C \rangle$, что $A$, $B$ и $C$ --- подмножества множества $\{ 1, \ldots, n \}$, образующие разбиение этого множества (то есть $A$, $B$ и $C$ попарно не пересекаются и в объединении дают всё $\{ 1, \ldots, n \}$) и $2009|A| + |B| = 2008n$. Тогда искомый коэффициент равен

$$ \sum_{\langle A,B,C \rangle \in \mathcal{S}} e^{2009\sum A} \cdot (-a)^{|B|} \cdot e^{\sum B} \cdot (-b)^{|C|} $$

Здесь для произвольного конечного множества чисел $X$ запись $\sum X$ означает сумму всех элементов $X$, $\sum \varnothing = 0$.

Пусть $\langle A,B,C \rangle \in \mathcal{S}$, то есть $2009|A| + |B| = 2008^2 \cdot 2009$. Тогда $|B| = 2009(2008^2 - |A|)$. Так как $0 \leqslant |B| \leqslant n = 2008 \cdot 2009$, то $2008 \cdot 2007 \leqslant |A| \leqslant 2008^2$. Однако $|B| + |C| = n - |A| = 2008 \cdot 2009 - |A|$, так что $2008 \leqslant |B| + |C| \leqslant 2008 \cdot 2$. Отсюда $|B| \leqslant 2008 \cdot 2$. Так как число $B$ кратно $2009$, то получаем две возможности: $|B|=0$ и $|B| = 2009$. При $|B|=0$ имеем $|A| = 2008^2$ и $|C|=2008$, а при $|B|=2009$ выполняется $|A|=2008^2-1$ и $|C|=0$.

Отметим, что в каждом из случаев для любого $A \subseteq \{ 1, \ldots, n \}$, такого что $|A|$ равно $2008^2$ или $2008^2-1$, существуют единственные $B$ и $C$, для которых тройка $\langle A, B, C \rangle \in \mathcal{S}$. Значит, искомую сумму можно расписать в виде

$$ \sum_{|A|=2008^2} e^{2009\sum A} \cdot (-a)^{|B(A)|} \cdot e^{\sum B(A)} \cdot (-b)^{|C(A)|} + $$ $$ + \sum_{|A|=2008^2-1} e^{2009\sum A} \cdot (-a)^{|B(A)|} \cdot e^{\sum B(A)} \cdot (-b)^{|C(A)|} $$

где $B(A)$ и $C(A)$ определяются из условия $\langle A, B(A), C(A) \rangle \in \mathcal{S}$.

Если $|A| = 2008^2$, то $B(A) = \varnothing$ и $|C(A)| = 2008$. Если же $|A| = 2008^2-1$, то $C(A) = \varnothing$, $|B(A)| = 2009$ и $\sum B(A) = \sum \{ 1, \ldots, n \} - \sum A = n(n+1)/2 - \sum A$. Кроме того, легко видеть, что $e^{n(n+1)/2} = -1$. Таким образом, искомая сумма равна

$$ \sum_{|A|=2008^2} e^{2009\sum A} (-b)^{2008} + \sum_{|A|=2008^2-1} e^{2009\sum A} \cdot (-a)^{2009} \cdot (-1) \cdot e^{-\sum A} $$

или, после некоторых сокращений,

$$ b^{2008} \sum_{|A|=2008^2} e^{2009\sum A} + a^{2009} \sum_{|A|=2008^2-1} e^{2008\sum A} $$

Найдём, чему равно

$$ \sum_{|A|=2008^2} e^{2009 \sum A} $$

Из простых комбинаторных рассмотрений ясно, что эта сумма равна коэффициенту при $x^{n-2008^2} = x^{2008}$ многочлена

$$ (x-e^{2009 \cdot 1})(x-e^{2009 \cdot 2}) \cdot \ldots \cdot (x - e^{2009 \cdot n}) $$

Так как $n = 2009 \cdot 2008$ и $e$ --- примитивный корень степени $n$ из $1$, то $e^{2009} = d$, где $d$ --- примитивный корень степени $2008$ из $1$. Значит, этот многочлен равен

$$ (x-d)(x-d^2) \cdot \ldots \cdot (x-d^n) = (x-d)^{2009} \cdot \ldots \cdot (x-d^{2008})^{2009} = (x^{2008}-1)^{2009} $$

Соответствующий коэффициент, как легко видеть из бинома Ньютона, равен $C_{2009}^1 \cdot (-1)^{2009-1} = 2009$. Таким образом,

$$ \sum_{|A|=2008^2} e^{2009 \sum A} = 2009 $$

Найдём, чему равно

$$ \sum_{|A| = 2008^2-1} e^{2008 \sum A} $$

Из тех же соображений, что и при нахождении предыдущей суммы, заключаем, что эта сумма равна минус коэффициенту при $x^{2009}$ многочлена

$$ (x-e^{2008 \cdot 1})(x-e^{2008 \cdot 2}) \cdot \ldots \cdot (x - e^{2008 \cdot n}) $$

Обозначив за $k$ число $e^{2008}$ и заметив, что $k$ есть примитивный корень $2009$-ой степени из $1$, переписываем этот многочлен как

$$ (x-k)(x-k^2) \cdot \ldots \cdot (x-k^n) = (x-k)^{2008} \cdot \ldots \cdot (x-k^{2009})^{2008} = (x^{2009}-1)^{2008} $$

Из бинома Ньютона находим, что коэффициент при $x^{2009}$ у этого многочлена равен $C_{2008}^1 \cdot (-1)^{2007} = -2008$.

Таким образом,

$$ \sum_{|A| = 2008^2-1} e^{2008 \sum A} = 2008 $$

и

$$ S_{2008 \cdot 2009} = 2008a^{2009} + 2009b^{2008} $$

Ответ, однако, отличается от того, который получил juna. Поскольку он не приводит никаких выкладок, желающие могут проверить моё решение и либо убедиться в его правильности, либо найти в нём ошибку.

[juna]

Во наворотили!
Ваш ответ красивее и правильный (я нашел неточность в своих преобразованиях). Но, по-моему, первый пункт простая тренировка на знание формулы Жирара-Ньютона.
Сейчас приведу свое решение.

Добавлено спустя 36 минут 58 секунд:

$S_{2008\cdot 2009}=\sum\limits_{i=1}^{2009}x_i^{2008\cdot 2009}=\sum\limits_{i=1}^{2009} (ax_i+b)^{2008}$
$(ax_i+b)^{2008}=C_{2008}^0\cdot (ax_i)^{2008}+C_{2008}^1\cdot (ax_i)^{2007}\cdot b+...+C_{2008}^{2008}\cdot b^{2008}$
$\sum\limits_{i=1}^{2009} (ax_i+b)^{2008}=C_{2008}^0\cdot a^{2008}\cdot (x_1^{2008}+x_2^{2008}+...+x_{2009}^{2008})+\\C_{2008}^1\cdot a^{2007}\cdot (x_1^{2007}+x_2^{2007}+...+x_{2009}^{2007})+...+2009\cdot C_{2008}^{2008}\cdot b^{2008}$(1)
(в прошлый раз я эту 2009 потерял)
Теперь используем формулу Жирара-Ньютона:
если дано уравнение $x^n+a_1x^{n-1}+...+a_n=0$, то степенные суммы корней $M_i=\sum\limits_{j=1}^{n}x_j^i$ удовлетворяют рекурентному соотношению:
$M_m+a_1M_{m-1}+a_2M_{m-2}+...+a_m\cdot m=0$
Наше уравнение $x^{2009}-ax-b=0$, т.е. $a_ {2009}=-b,a_{2008}=-a$
Отсюда находим, что $M_{2008}-2008a=0$, а все остальные степенные суммы равны нулю.
Подставляя в (1), находим $S_{2008\cdot 2009}=2008\cdot a^{2009}+2009\cdot b^{2008}$

[Профессор Снэйп]

juna писал(а):

Во наворотили!

Не знал я никаких формул Жирара-Ньютона, потому и наворотил! Первый раз о таких слышу

Отсюда мораль:

1) Век живи --- век учись!
2) Против лома нет приёма

[General]

В скором времени следует ожидать (да они уже появляются) задач, затрагивающих номер текущего года. Можно заранее составить список нескольких его свойств. К примеру:

Число 2009 раскладывается на простые множители следующим образом: $2009=7 * 7 * 41$

Следовательно, число 2009 можно представить в виде разности квадратов целых чисел тремя способами:
$2009=1005^2-1004^2=147^2-140^2=45^2-4^2$

А в виде суммы квадратов число представляется единственным образом: $2009=28^2+35^2$

Чтобы получить число 2009 в виде суммы кубов, потребуется минимум 4 слагаемых, и сделать это можно тремя способами:
$2009=1^3+2^3+10^3+10^3=1^3+4^3+6^3+12^3=4^3+6^3+9^3+10^3$

В виде суммы треугольных чисел (имеющих вид $T_n=\frac{n(n+1)}{2}$) число 2009 можно представить 11-ю способами:
$2009=T_1+T_{10}+T_{62}=T_1+T_{35}+T_{52}=T_7+T_7+T_{62}=T_7+T_{31}+T_{54}=T_7+T_{43}+T_{45}=T_8+T_{34}+T_{35}=T_9+T_{22}+T_{58}=T_{13}+T_{27}+T_{55}=T_{22}+T_{25}+T_{53}=T_{22}+T_{27}+T_{52}=T_{27}+T_{28}+T_{49}$

2009-е треугольное число равно 2 019 045

Число 9002, образованное из 2009 обратной записью, также делится на 7: $9002= 2 * 7 * 643$

2009-е простое число равно 17471, это палиндром, оно одинаково читается как справа налево, так и слева направо

Простыми также являются числа $P_{2009}+6$, $P_{2009}+12$, $P_{2009}+18$, $2*2009+1$, $3*2009+2$ и $4*2009+3$

Рассмотрим процесс: берём натуральное число и прибавляем к нему сумму его цифр. Число 2009 в нём можно получить из самопорождённого (по Капрекару) числа 1693 за 19 шагов: 1693 - 1712 = 1693+(1+6+9+3) - 1723 = 1712+(1+7+1+2) - 1736 - 1753 - 1769 - 1792 - 1811 - 1822 - 1835 - 1852 - 1868 - 1891 - 1910 - 1921 - 1934 - 1951 - 1967 - 1990 - 2009.

В другом процессе, рассмотренном индийским математиком Капрекаром, будем из числа, образованного цифрами четырёхзначного числа, записанными в порядке убывания, вычитать число, образованное теми же цифрами, но в порядке возрастания. К числу 6174, постоянной Капрекара, мы придём за 3 шага: К(2009) = 9200-0029=9171; К(9171) = 9711-1179=8532; К(8532) = 8532-2358=6174. К(6174) = 7641-1467=6174.

В числе $2009!=1*2*3*\dots*2009$ 5765 цифр. Оно заканчивается пятьюстами нулями.

И наиболее экзотический факт: оказывается, существует ровно 2009 5-мерных гексамино.

[bot]

General в сообщении #175162 писал(а):

2009! заканчивается пятьюстами нулями.

Эту уже давал на зачёте.
А разрешимость $x^2+y^2=2007$ спрашивал в 2006

[Батороев]

General писал(а):

В виде суммы треугольных чисел (имеющих вид $T_n=\frac{n(n+1)}{2}$) число 2009 можно представить 11-ю способами:
$2009=T_1+T_{10}+T_{62}=T_1+T_{35}+T_{52}=T_7+T_7+T_{62}=T_7+T_{31}+T_{54}=T_7+T_{43}+T_{45}=T_8+T_{34}+T_{35}=T_9+T_{22}+T_{58}=T_{13}+T_{27}+T_{55}=T_{22}+T_{25}+T_{53}=T_{22}+T_{27}+T_{52}=T_{27}+T_{28}+T_{49}$

А сколько существует способов представить число в виде разности двух треугольных чисел?

[ИСН]

Это "те же яйца, вид сбоку", что и разность квадратов. Там сводилось к представлению числа в виде некоторого специального произведения, а тут - к представлению удвоенного числа в виде другого произведения...
шесть вариантов, короче.

[Батороев]

ИСН писал(а):

Это "те же яйца, вид сбоку", что и разность квадратов. Там сводилось к представлению числа в виде некоторого специального произведения, а тут - к представлению удвоенного числа в виде другого произведения...
шесть вариантов, короче.

То есть вариантов больше?

Тогда, если сравнить два способа факторизации:
1. Метод по Ферма;
2. Метод 2:
а) Находим остатки треугольных чисел, превосходящих $N$:
$ T_i\equiv a_i\pmod N $
б) Находим целочисленные значения $ b_i=\sqrt{8a_i+1} $,
в) Раскладываем выражения:
либо $ (i-\dfrac{b_i-1}{2}) $,
либо $ (i+\dfrac{b_i-1}{2}+1) $ на простые множители,

то по-видимому, можно предположить, что при втором способе плотность положительных решений должна быть выше.

[General]

Действительно, способов ровно 6:
$2009=T_{2009}-T_{2008}=T_{1005}-T_{1003}=T_{290}-T_{283}=T_{150}-T_{136}=T_{69}-T_{28}=T_{65}-T_{16}$

В общем же случае, поскольку для разложения числа в виде разности квадратов, требуется решать диофантово уравнение
$n=(a-b)(a+b)$, а для разности треугольных чисел - уравнение $2n=(a-b)(a+b+1)$, то количество решений в первом случа будет равно количеству представления числа n в виде двух множителей одинаковой чётности, а во тором случае - количеству представления числа 2n в виде двух множителей различной чётности.

Пусть число $n=2^k \dot n$, где $\dot n$ - число, получаенное от деления n на максимальную степень двойки, входящую в него. Это число (если оно не полный квадрат), можно разбить на произведение двух множителей $\frac{\tau(\dot n)}{2}$ способами, а чтобы одной формулой учесть ещё и полные квадраты, способов будет $\left \ceil \frac{\tau(\dot n)}{2} \right \ceil$

Далее, при k=0 таким же будет и общее количество способов разбиения числа n на 2 множителя одинаковой чётности. При $k\geq1$ таких способов будет $(k-1)\frac{\tau(\dot n)}{2}$ (из каждого из вариантов разбиения числа $\dot n$ получаем по k-1 вариантов, по-разному распределяя множители-двойки)

Если же $\dot n$ - полный квадрат, то формула модифицируется до $(k-1)\left[\frac{\tau(\dot n)}{2} \righе]+\left[\frac{k}{2}\right]$

Способов разбиения числа 2n на множители разной чётности будет $\tau(\dot n)$ (ведь теперь множитель $2^(k+1)$ должен отходить полностью к какому-либо сомножителю), если $\dot n$ - не полный квадрат, и $2\left \frac{\tau(\dot n)}{2}\right]+1$ в обратном случае.

Так что количество разложений в разность треугольных чисел превышает количество разложений в разность квадратов только у нечётных чисел (вдвое) и у тех, разложение которых двойка входит в первой степени (например, для числа 2010 это соотношение было бы вообще 8 : 0)
//Перечитал ещё раз - ведь действительно, в среднем 3 из 4 чисел можно большим количеством способов представить в иде разности треугольников, чем в виде разности квадратов.

Ещё что интересное нашёл про 2009 - оказывается, ровно столько Гамильтоновых графов с 8-ю вершинами

[Батороев]

General писал(а):

$ T_{45}-T_{3}$

Последняя разность $ T_{65} - T_{16} $.

[General]

Точно, спасибо

[Руст]

Мое решение.
Рассмотрим рекурентную последовательность $x_{n+2009}=ax_{n+1}+bx_n$.
Последовательности $x_i^n$ для любого корня $x^{2009}=ax+b$ удовлетворяют этому соотношению. Поэтому любая линейная комбинация так же удовлетворяет этому соотношению, в частности $S_n=\sum_i x_i^n$. Кратные корни получаются только в случае $a=b=0$ и все формулы работают и в этом случае.
Легко получается, что $S_1=S_2=...=S_{2007}=0,S_0=2009$ (последнее так же можно считать верным для случая a=b=0). Вычислим $S_{2008}=aS_0+bS_{-1}=2009a+b\frac{\sigma_{2008}}{\sigma_{2009}}=2009a+b\frac{-a}{b}=2008a$ и $S_{2009}=aS_1+bS_{2009}=2009b$.
Ненулевые значения $S_n,n>0$ могут появится только в случае, когда $n=2008i+2009j,i,j\ge0.$
Вычислим для такого n количество путей от n до 0 с шагом 2008 или 2009 и их вклад в $S_n$.
Количество путей от n до 2008 с i-1 шагом длиной 2008 и j шагом длиной 2009 равно $C_{i+j-1}^{i-1}$ и они дадут вклад $C_{i+j-1}^{i-1}a^{i-1}b^jS_{2008}=2008C_{i+j-1}a^ib^j$. Аналогично пути до 2009 дают вклад $2009C_{i+j-1}^{j-1}a^ib^j$. В сумме решению $2008i+2009j=n$ соответствует вклад $a^ib^j\frac{(i+j-1)!}{i!j!}(2008i+2009j)=\frac{n}{i+j}C_{i+j}^ia^ib^j$.
Если $i_0,j_0$ решение $2008i_0+2009j_0=n$ с минимальным $j_0$, то все остальные решения будут иметь вид $(i_0-2009k,,j_0+2008k,k=0,...[i_0/2009]<=[n/2008]$. Соответственно
$S_n=na^{i_0}b^{j_0}\sum_k \frac{1}{i_0+j_0-k}C_{i_0+j_0-k}^{j_0+2008k}a^{-2009k}b^{2008k}$.
Отсюда получаются соотношения о делимости (учитывая, что 2009 не простое). Количество слагаемых примерно n/(2008*2009). Примерно в половине случаев надо округлять в верхнюю сторону, в половине в нижнюю сторону для получения точного количества слагаемых.