2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Новогодняя
Сообщение28.12.2008, 16:10 
Заслуженный участник


09/02/06
4382
Москва
Пусть $$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$.

 Профиль  
                  
 
 Re: Новогодняя
Сообщение02.01.2009, 15:15 
Заслуженный участник
Аватара пользователя


07/03/06
1892
Москва
Руст писал(а):
1. Вычислить $S_{2008*2009}$

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

 Профиль  
                  
 
 Re: Новогодняя
Сообщение03.01.2009, 04:48 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Руст писал(а):
Пусть $$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. Поскольку он не приводит никаких выкладок, желающие могут проверить моё решение и либо убедиться в его правильности, либо найти в нём ошибку.

 Профиль  
                  
 
 
Сообщение03.01.2009, 10:15 
Заслуженный участник
Аватара пользователя


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

Добавлено спустя 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}$

 Профиль  
                  
 
 
Сообщение03.01.2009, 12:26 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
juna писал(а):
Во наворотили!


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

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

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

 Профиль  
                  
 
 Число 2009
Сообщение08.01.2009, 20:38 
Аватара пользователя


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

Число 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-мерных гексамино.

 Профиль  
                  
 
 
Сообщение09.01.2009, 07:05 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
General в сообщении #175162 писал(а):
2009! заканчивается пятьюстами нулями.

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

 Профиль  
                  
 
 Re: Число 2009
Сообщение09.01.2009, 12:04 


23/01/07
3415
Новосибирск
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}$

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

 Профиль  
                  
 
 
Сообщение09.01.2009, 13:36 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение09.01.2009, 15:51 


23/01/07
3415
Новосибирск
ИСН писал(а):
Это "те же яйца, вид сбоку", что и разность квадратов. Там сводилось к представлению числа в виде некоторого специального произведения, а тут - к представлению удвоенного числа в виде другого произведения...
шесть вариантов, короче.

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

Тогда, если сравнить два способа факторизации:
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) $ на простые множители,

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

 Профиль  
                  
 
 
Сообщение09.01.2009, 23:14 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Действительно, способов ровно 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-ю вершинами

 Профиль  
                  
 
 
Сообщение10.01.2009, 11:42 


23/01/07
3415
Новосибирск
General писал(а):
$ T_{45}-T_{3}$

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

 Профиль  
                  
 
 
Сообщение10.01.2009, 14:52 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Точно, спасибо

 Профиль  
                  
 
 
Сообщение22.01.2009, 10:16 
Заслуженный участник


09/02/06
4382
Москва
Мое решение.
Рассмотрим рекурентную последовательность $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). Примерно в половине случаев надо округлять в верхнюю сторону, в половине в нижнюю сторону для получения точного количества слагаемых.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group