46-я Международная Математическая OлимпиадаМексика, Мериде, 2005 год

Пусть ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{n}}$, $\ldots$ — последовательность целых чисел, в которой содержится бесконечно много как положительных, так и отрицательных членов. Известно, что для каждого натурального $n$ все $n$ остатков от деления ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{n}}$ на число $n$ различны. Докажите, что каждое целое число встречается в этой последовательности ровно один раз.

Комментарий/решение

Пусть $a_k=a_j\Longrightarrow n=a_k\cdot x+y=a_j\cdot x+y \longrightarrow n\equiv y\pmod {a_k};$ $n\equiv y\pmod {a_j}$

И что это должно значит?

Это значит, что вы не поняли, но пытаетесь сделать вид,что поняли

Это значить что число $a_k \equiv a_j \pmod n$. Это уже противоречие

Как это доказывает что каждое целое число встречается в нашей последовательности.

Я же сказал что если найдутся число $a_k=a_j$ то это противоречие и доказал.

Надо доказать что $:$

$$\forall \ k\in \mathbb{Z} \quad \exists \ l\in \mathbb{N} \ \ \text{что} \ \ a_l=k$$

Было доказано что все $\ a_i \ $ различны. Так почему из этого следует то что нам нужно доказать?

Пусть $a_k=a_j=l$ Тогда $a_k\equiv l \pmod n;$. Так как $a_k=a_j=l \Longrightarrow l \equiv a_j \pmod n$ $\Longrightarrow a_k \equiv a_j\pmod n\longrightarrow \varnothing$

Прочтите вопрос внимательней

Тогда наверное так:

Пусть $a_k=a_j\Longrightarrow n=a_k\cdot x+y=a_j\cdot x+y \longrightarrow n\equiv y\pmod {a_k};$ $n\equiv y\pmod {a_j}$

я хотел сказать что не индексы (значить не факт что $k=j$), а числа равны ($a_k=a_j$)

Если допустим $k>n$ то это еще не значит что $a_k \ne a_j (\mod n)$

Эссе для вас griezman.567:

В теории чисел существует важное правило, которое гласит, что если два числа равны, то они дают одинаковый остаток при делении на одно и то же число. Однако возникло недоразумение, что индексы, например $k$, могут влиять на результат операции взятия остатка при делении на число $n$, особенно когда $k > n$. Давайте разберемся, почему это не так, и почему значение индекса не влияет на остаток при делении.

Прежде всего, важно понять, что операция взятия остатка от деления, или операция модуль, работает независимо от индексов и того, что эти индексы могут быть больше, чем сам делитель. Операция деления с остатком имеет такую форму: для числа $a$ и делителя $n$ мы можем записать $a = n \cdot q + r$, где $q$ — целая часть от деления, а $r$ — остаток, который всегда будет числом от 0 до $n-1$. Это определение остается верным независимо от того, какое число мы делим.

Если числа $a_k$ и $a_j$ равны, то есть $a_k = a_j$, то независимо от их индексов и их размеров, остатки от их деления на $n$ будут одинаковыми. Это объясняется тем, что операцией деления мы лишь определяем, как число $a$ «разбивается» на части, а остаток зависит только от самого числа и делителя. Даже если $k > n$, это не меняет результата деления, потому что индексы $k$ и $j$ не влияют на число $a$, которое мы делим.

Для понимания этого на примере: допустим, $a_k = 15$ и $a_j = 15$, и $n = 4$. Тогда $15 \mod 4 = 3$, и этот остаток будет одинаковым, независимо от того, является ли $k = 10$ или $k = 100$. Индекс $k$ просто указывает на то, какое число рассматривается, но на остаток это не влияет.

Таким образом, ключевым моментом является то, что остаток при делении зависит только от величины числа и делителя. Индекс, такой как $k$, не имеет никакого влияния на результат операции модуль. Это свойство остается верным независимо от того, больше ли индекс $k$, чем число $n$, или меньше.

В условии сказано что числа $a_1,a_2 \cdots a_n$ дают различный остаток при делении на $n$ то есть $a_i \ne a_j (\mod n)$ при любых различных $i$ и $j$ принадлежащих множеству $1,2 \cdots n$ а вот если $k>n$ то $k$ не пренадлежит множеству $1,2 \cdots n$ следовательно это еще не означает что $a_k \ne a_j (\mod n)$($j-$любой индекс) Кажется вы прочитали условие так что каждые два числа в этой последовательности дают различный остаток $(\mod n)$ Но говорится что любые два числа из множества $a_1,a_2 \cdots a_n$ не сравнимы с друг другом по $\mod n$

Очевидно, каждое число встречается не более одного раза (иначе возьмем $n$ гораздо больше). Теперь докажем, что каждое число встречается хотя бы один раз.

$\textbf{Утверждение.}$ Для любых $i < j$ имеем

$a_i - a_j< j.$

$\textit{Доказательство.}$ Предположим противное: пусть $n = a_i - a_j\neq0$. Тогда $i, j \in [1, n]$ и $a_i \equiv a_j \pmod{n}$, что является противоречием. $\square$

$\textbf{Утверждение.}$ Для любого $n$ множество $\{a_1, \dots, a_n\}$ имеет вид $\{k+1, \dots, k+n\}$ для некоторого целого $k$.

$\textit{Доказательство.}$ Докажем индукцией. База $n=1$ тривиальна. Пусть утверждение верно для $n$, то есть

$\{a_1, \dots, a_n\} = \{k+1, \dots, k+n\}.$

Тогда

$a_{n+1} \equiv k \pmod{n+1}$

Кроме того, из предыдущего утверждения следует

$|a_{n+1} - a_1| < n+1.$

Отсюда заключаем, что $a_{n+1} \in \{k, k+n+1\}$, что и требовалось. $\square$

Таким образом, последовательность полностью описывается следующим образом: выбираем $a_1$, а затем каждое следующее $a_n$ получается как либо $\max S + 1$, либо $\min S - 1$, где $S = \{a_1, \dots, a_{n-1}\}$ — множество $n-1$ последовательных целых чисел.

$\textbf{Заключение.}$ Замечаем, что поскольку в последовательности бесконечно много положительных и отрицательных членов (что мы до сих пор не использовали), то она не ограничена сверху и снизу. Следовательно, она содержит все целые числа.