Интересная последовательность

[Xenia1996]

Дана последовательность
$a_n=1^n+2^n+3^n+\dots+11^n$
Доказать, что не найдутся 11 подряд идущих её элементов, каждый из которых делится на 2011.

[nnosipov]

Xenia1996 в сообщении #441536 писал(а):

Дана последовательность
$a_n=1^n+2^n+3^n+\dots+11^n$
Доказать, что не найдутся 11 подряд идущих её элементов, каждый из которых делится на 2011.

LXVIII Московская олимпиада. Давайте уж сразу общий случай: если $k>1$ --- натуральное число, то ни для какого простого числа $p \geqslant k$ не существует $k$ идущих подряд членов последовательности

$$ a_n=1^n+2^n+\ldots+k^n, $$

делящихся на $p$.

[Xenia1996]

nnosipov в сообщении #441538 писал(а):

LXVIII Московская олимпиада.

На $LXVIII$ олимпиаде было $1+2^n+3^n+4^n+5^n$

(Оффтоп)

Я задачи не копипастю. Я не данки, я манки

[nnosipov]

Xenia1996 в сообщении #441542 писал(а):

(Оффтоп)

Я задачи не копипастю. Я не данки, я манки

(Оффтоп)

Минут пять думал о смысле последней фразы. Почти понял, но до конца не уверен. Это из какого-то мультфильма или игры?

[Xenia1996]

nnosipov в сообщении #441546 писал(а):

Xenia1996 в сообщении #441542 писал(а):

(Оффтоп)

Я задачи не копипастю. Я не данки, я манки

(Оффтоп)

Минут пять думал о смысле последней фразы. Почти понял, но до конца не уверен. Это из какого-то мультфильма или игры?

(Оффтоп)

Это шутка из мира программистов. В жизни программера есть три этапа:
00. Donkey
01. Monkey
10. Programmer

Данки (осёл) сам ничего не пишет, тырит у других и копипастит.
Манки (обезьянка) тырит у другого, частично переделывает, что-то добавляет, затем уже пастит.
Ну, а Программер уже пишет всё сам от начала до конца.

[nnosipov]

Xenia1996 в сообщении #441549 писал(а):

(Оффтоп)

Это шутка из мира программистов. В жизни программера есть три этапа:
00. Donkey
01. Monkey
10. Programmer

Данки (осёл) сам ничего не пишет, тырит у других и копипастит.
Манки (обезьянка) тырит у другого, частично переделывает, что-то добавляет, затем уже пастит.
Ну, а Программер уже пишет всё сам от начала до конца.

(Оффтоп)

А, теперь понятно. Буду знать.

[Sonic86]

Решается от противного заменой переменных $x_j=j^n$ через определитель Вандермонда

[Xenia1996]

Sonic86 в сообщении #441572 писал(а):

Решается от противного заменой переменных $x_j=j^n$ через определитель Вандермонда

Так-тааак, это уже поинтересней.
Извольте детализировать.

[Sonic86]

Xenia1996 писал(а):

Так-тааак, это уже поинтересней.
Извольте детализировать.

Пусть начиная с номера $n$ $a_n \equiv a_{n+1} \equiv ... \equiv a_{n+k-1} \equiv 0 \pmod p$. Делая замену $x_j=j^n$ получаем систему сравнений:

$$ \left\{ \begin{array}{llll} 1^0 x_1 + 2^0x_2 + ... + k^0 x_k \equiv 0 \pmod p \\ 1^1 x_1 + 2^1x_2 + ... + k^1 x_k \equiv 0 \pmod p \\ ........................... \\ 1^k x_1 + 2^kx_2 + ... + k^k x_k \equiv 0 \pmod p \end{array} $$

Матрица системы $C = (j^{i-1})$, значит ее определитель - определитель Вандермонда и $\det A = \prod\limits_{1 \leq i < j \leq k} (i-j)^2$.
Поскольку $p$ простое и $p \geq k$, то $\det A \not \equiv 0 \pmod p$, а значит существует единственное решение данной СЛУ, а именно: $x_j \equiv 0 \pmod p$, что невозможно.
P.S. По-моему, nnosipov заранее все знал, обобщение максимально точно.

[nnosipov]

Sonic86 в сообщении #441581 писал(а):

P.S. По-моему, nnosipov заранее все знал, обобщение максимально точно.

А чего тут знать-то? Но интересно было бы обойтись без Вандермонда. Хотя это, скорее всего, будет завуалированным вычислением этого определителя.

[nnosipov]

Впрочем, можно и вот так. Рассмотрим разностный оператор $L=\Delta_1\Delta_2\ldots\Delta_{k-1}$, где $\Delta_\lambda$ --- разностный оператор, действующий по правилу $\Delta_\lambda(a_n)=a_n-\lambda a_{n-1}$. Имеем $L(1^n+2^n+\ldots+k^n)=L(k^n)=(k-1)!k^{n-k+1}$. Теперь утверждение очевидно, поскольку $p>k$. (Вандермонда здесь формально нет, но его уши виднеются.)