Which country proposed this problem?

Solution:

That seems very simple so it's probably wrong

It seems to be a correct solution and a very easy problem indeed.

Indeed easy problem.I have the same idea(may be the one possible).

My solution was slightly more complicated than the above one, but it was basically like, WLOG $a_1 \ge 0$, if $a_k$ is the first term of the sequence that's negative, it's easy to show $a_k = -1$, and $a_1, a_2, \ldots, a_{k-1}$ is a permutation of $0, 1, \ldots, k-2$, and then if $a_{k_2}$ is the second term of the sequence that's negative, then once again it's straightforward to show $a_{k_2} = -2$, and the terms between $a_{k_2}$ and $a_k$ are the positive integers from $k-1$ to whatever the difference was, and so on. This seemed like quite a straightforward problem, much easier than many of the problems we got at MOP, so hopefully that bodes well for the USA .

Valentin Vornicu wrote: Let $a_1,a_2,\ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$. Prove that every integer occurs exactly once in the sequence $a_1,a_2,\ldots$. Indeed , I couldn't understand both this problem and schulmannerism's solution For every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$. So , we can understand that : There doesn't exist 2 numbers $ a_i, a_j $ in n numbers $ a_1,a_2 ,...a_n $ such that : $ a_i \equiv a_j $ mod n . So the problem is obviously true

jarod wrote: Valentin Vornicu wrote: Let $a_1,a_2,\ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$. Prove that every integer occurs exactly once in the sequence $a_1,a_2,\ldots$. Indeed , I couldn't understand both this problem and schulmannerism's solution For every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$. So , we can understand that : There doesn't exist 2 numbers $ a_i, a_j $ in n numbers $ a_1,a_2 ,...a_n $ such that : $ a_i \equiv a_j $ mod n . So the problem is obviously true It is true, and even obviously, but I do not understand your arguments. You prove that all numbers are different, but why each integer is a member of a sequence?

it seems to me that it's going to be a really easy IMO.. at least if I didn't make any mistakes, but I think it's really an easy problem. excuse me for not typing in tex, but i'll correct it in short time..

I took a look at others' solutions after typing, so I guess I should of done it before typing :/

I have a solution : Consider $ (a_1,a_2,...,a_n) $ . Suppose $ max($ a_1,a_2,..a_n $) - min($ a_1,a_2,..a_n $) \geq n $ So $ max($ a_1,a_2,..a_n $) \equiv min( $ a_1,a_2,..a_n $ ) $ mod k >n : contradiction ! So $ max( $ a_1,a_2,..a_n $ ) - min($ a_1,a_2,..a_n $) = n-1 $ Then $ |a_1| , |a_2| ,..., |a_n| $ are consective integers : Q.E.D

schulmannerism: I don't think you prove that each integer occurs exactly once in the sequence, which is required by the problem. You only prove that if the sequence contains every integer, then every integer occurs exactly once. I think these two claims are different.

euclid_gemoetry wrote: schulmannerism: I don't think you prove that each integer occurs exactly once in the sequence, which is required by the problem. You only prove that if the sequence contains every integer, then every integer occurs exactly once. I think these two claims are different. No, I think he proved it right. His claim implies that each a1,...,ak is consecutive. Also that at each point, you can only "attach" one more number either from the left side (largest negative number not in the set) or from the right side (smallest positive number). Now if m>0 is not in the sequence, it means that after a while, you can only attach from the left, which means you have finitely many positive numbers. Contradiction. Same argument for m<0.

You must just prove that the function $f : Z \rightarrow (a_n)$ is bijective (injective and surjective). Injective : suppose that $a_i=a_j$ for some $i$ and $j$ such that $i<j$. Then for every $m$ such that $m>j$, we have the sequence : $a_1,a_2,....,a_i,....a_j,....,a_m $ But this sequence contains $a_i$ and $a_j$ such that $a_i=a_j (mod m)$. And it's absurb. Surjective: by induction : let the sequence $a_1,a_2,...,a_n$ which contains n integers. We will construct $a_{n+1}$. $a_{n+1}$ is the missing remainder in $a_1,a_2,...,a_n$. Thus, there is an infinite of values for $a_{n+1}$

cezar lupu wrote: Which country proposed this problem? The Netherlands!!! My lovely home country... I was participant at this year's IMO and I solved this problem, I found it the easiest problem, but I liked it..

: There is very easy number theory on IMO 2005

Define $S = \{ a_1, a_2, ....\}$ $S_n =\{a_1, a_2, ..., a_n \}$ Lemma 1: $0<|a_i - a_j|<n$ if $i, j \leq n$ Proof: If $|a_i - a_j |= d \geq n$, then consider $S_d$. $a_i, a_j$ are elements of $S_d$ but $a_i = a_j (\mod d)$ contradiction as desired. If $a_i=a_j$ we automatically have contradiction so the desired lemma follows. Hence every integer appears at most once. Lemma 2: $S_n$ is a set of $n$ consecutive integers (not necessarily in any order though) Proof: We prove this by induction. $n=1$ is trivial. Let $\min \{ a_1, a_2, ..., a_k \} = m$. Then Suppose $S_k = \{ m, m+1, m+2, ..., m+k-1 \}$. Consider $S_{k+1}$, $a_{k+1} = m-1(\mod k+1)$ so $a_{k+1}= m-1 + q(k+1)$. Suppose $q>1$ then $|a_{k+1}-m| \geq k+1$, contradiction of lemma 1. Similarly $q<0$ implies $|a_{k+1} - (m+k-1)| \geq k+1$ contradiction of lemma 1 as well . so $a_{k+1} = m+k+1$ or $m-1$ desired lemma follows. // Since we can subtract any integer from each term of our sequence, WLOG let $a_1=0$ let $T$ be the set of positive integers not in $S$, $T'$ be the set of negative integers not in $S$. If $T$ is non-empty, then let $s$ be the smallest element in $S$. Let $t$ be a negative integer in $S$. $T$ cannot contain all integers larger than $s$ so let $r>s$ be in $S$. Hence for some sufficiently large $k$ $S_k$ contain both $r, t$, and all integers between them by lemma 2. Hence $s$ is in $S$ contradiction. Hence $T$ is empty. Similarly if we multiply every element in $S$ by -1, the new sequence still satisfy all the conditions, so by symmetry we have $T'$ of is empty. Hence $S$ contain all integers QED.

pavel kozlov wrote: : There is very easy number theory on IMO 2005 It was the second-hard problem for me I tried to prove it during 2 hours But I've got the solution just like schulmannerism's one

Is there any original solution for this problem ... : Davron

Sjoerd wrote: cezar lupu wrote: Which country proposed this problem? The Netherlands!!! Yes. The problem was composed by Dick de Bruijn (the de Bruijn of the de-Bruijn-sequences, the de-Bruijn-graphs, of the AutoMath project, etc.). De Bruijn is prof emeritus at the TU Eindhoven.

Please can someone check this : Let $(b_1,b_2,...,b_n)$ be the permutations of $(a_1,a_2,...,a_n)$ such that $b_1 \equiv 1(modn)$ $b_2 \equiv 2(modn)$ . . . $b_n \equiv 0(modn)$ We know that there exists $b_i$ and $b_j$ such that $b_1<b_i,b_j<b_n$ we want to show that we never have $b_i=b_j$. Now we may suppose that there exist $b_i=b_j$ such a numbers, thus we have $b_i-b_j=0$ by the way we have $b_i-b_j \equiv 0 (modn)$ but we don't have that since $i$ and $j$ are different from each other which means they give a different remainders up on division by $n$. So resulting we have a contradiction for the statement $b_i=b_j$ Note: that holds if and only if $i=j$ . [please check i know that it is wrong, but can someone say me how can i prove this problem in this way, many thanks] davron

wow uh it seemed really intimidating but actually really easy lol, unless im fakesolving First, note that all terms must be distinct, because if there's an $i>j$ s.t. $a_i=a_j$, taking mod n>i makes two same residues. Now, we claim that in any sequence $a_1,a_2,...,a_k$, these numbers are consecutive in some order. Assume not, so there are $l,m$ s.t. $|a_l-a_m|=d\ge k$ (since otherwise minimum minus maximum is at most k-1, and there are only k numbers so they would be consecutive). Then taking mod d we get $a_l\equiv a_m\pmod {d\ge k}$, contradiction. We can extend this for sufficiently large k infinitely. $\blacksquare$

In fact, this sequence is always some permutation of a set of consecutive integers. We use induction to prove this; for our base case, consider when $n=1$; a single integer is definitely a permutation of a set of consecutive integers. For the inductive step, if $a_1, a_2, \dots, a_n$ are $n$ consecutive integers, consider $a_{n+1}$. If $a_{n+1}$ differs from $a_1$ by some integer $x > n$, then the remainders when $a_1, a_2, \dots, a_x$ are divided by $x$ won't all be distinct. In particular, $x \neq n+1$ since then $a_1 \equiv a_{n+1} \pmod{n+1}$. Similarly, $a_{n+1}$ differs from $a_n$ by no more than $n$. Furthermore, $a_{n+1}$ obviously can't equal any of $a_1, a_2, \dots, a_n$, hence either $a_{n+1} = \min (a_1, \dots, a_n) -1$ or $a_{n+1} = \max (a_1, \dots, a_n) + 1$. Combining this with the condition that there are infinitely many positive and negative integers, we clearly can't skip over any integers.

Actually, we have the following characterization of $\{a_i\}$: Claim: $a_1$, $a_2$, $\dots$, $a_n$ is a permutation of some $n$ consecutive numbers. (This solves the problem by the infinitely many positive/negative condition.) Proof. Induct - base case $n=1$ is vacuous. Clearly none of the $a_i$ are equal (otherwise take modulo sufficiently large to obtain a contradiction). Note that $\lvert \max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n) \rvert \le n -1$, otherwise consider $\pmod{\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)}$ - this finishes.

We will show by induction that $a_i$ equals one of $\min{(a_1,a_2,\dots,a_{i-1})}-1$ and $\max{(a_1,a_2,\dots,a_{i-1})}+1.$ For the base case we have $i=2.$ If $|a_2-a_1|=k \ne 1,$ then we would have $a_1 \equiv a_2 \pmod{k},$ contradiction. For the inductive step, if $a_i < \min{(a_1,a_2,\dots,a_{i-1})}-1$ then we have $a_i \equiv \max{(a_1,a_2,\dots,a_{i-1})} \pmod{\max{(a_1,a_2,\dots,a_{i-1})}-a_i},$ and $\max{(a_1,a_2,\dots,a_{i-1})}-a_i > i,$ impossible. Similarly $a_i > \max{(a_1,a_2,\dots,a_{i-1})}$ is impossible, and our inductive hypothesis is equivalent to every $k$ with $\min{(a_1,a_2,\dots,a_{i-1})} \le k \le \max{(a_1,a_2,\dots,a_{i-1})}$ being an $a_j$ for some $j,$ so our induction is complete. It is clear that each positive integer appears at most once. Notice that our claim above implies that $\max{(a_1,a_2,\dots,a_{i-1})}$ and $\min{(a_1,a_2,\dots,a_{i-1})}$ can only change by at most one when going from $i$ to $i+1,$ so if $x > a_1$ appears, then all $y$ with $a_1 \le y \le x$ appear, and similarly if $x < a_1$ appears then all $y$ with $x \le y \le a_1$ appear. Since the sequence has infinitely many positive and negative terms, this gives that every integer appears at least once, by taking an arbitrary large or small $x,$ so we are done.

We claim that $a_1$, $a_2$, \dots, $a_n$ must be $n$ consecutive numbers which obviously is the problem. We prove this by induction. Our base case is pretty obvious. Now assume FTSOC that $a_1$, $a_2$, \dots, $a_{n-1}$ are consecutive numbers and $a_n$ is not a part of that block. WLOG let $a_{n-1}$ be the greatest number and WLOG let $a_n$ be such that $a_n > a_{n-1}+1$. Also, WLOG let $a_1$ be the smallest number. We can see that we have $a_n -a_1 \geq n$. Thus we consider that when we divide by $a_n-a_1$ we will not have distinct remainders for $a_n$ and $a_1$. $\blacksquare$

We'll prove two claims about the sequence, which when combined imply the desired result. Claim 1: All elements in the sequence are distinct. Proof. Assume otherwise; pick any $i < j$ such that $a_i = a_j$. Then, the integers $a_1, a_2, \cdots, a_j$ must have different remainders when divided by $j$, a contradiction, as $a_i$ is also among them. $\blacksquare$ Claim 2: We have $|a_i - a_j| \le n - 1$ for all $1\le i, j \le n$. Proof. Assume otherwise, and let $a_i - a_j = k \ge n$. Then, the integers $a_1, a_2, \cdots, a_k$ must have different remainders when divided by $k$, but since $k \ge n \ge i, j$, $a_i$ and $a_j$ are also among these numbers, which gives a contradiction. $\blacksquare$ So, $a_1, a_2, \cdots, a_n$ are $n$ consecutive numbers in some order for all $n$, since they're all distinct, and the maximum difference between two of them doesn't exceed $n - 1$. Thus, $a_1, a_2, \cdots, a_n$ contain all the integers in the range $[l, r]$ for some $l, r$ with $r - l + 1 = n$. Also, since the next integer $a_{n + 1}$ can't lie in the range $[l, r]$ since all the numbers are distinct, and it can't be $< l - 1$, or $>r + 1$, since we don't skip any number either, this means that $a_{n + 1} = l - 1,$ or $a_{n + 1} = r + 1$. So, either $l$ gets decremented by $1$, or $r$ gets incremented by $1$. It suffices to show that each of these operations happens infinitely many times. Assume that only one of them occurs an infinite number of times, and the other occurs only a finite number of times; WLOG $l$ gets decremented only finitely many times. Then, if the initial value of $l$ was $k$, and it gets decremented $d$ times, any number $x < k - d$ doesn't appear in the sequence at all, a contradiction, since there are infinitely many negative numbers in the sequence. So, each operation occurs an infinite number of times, and we're done.

Suppose FTSOC we have $a_i = a_j$ for some $i < j$. Then we have a contradiction for any $n \ge j$, so all terms are distinct. We now prove the stronger statement that $a_1,\ldots,a_n$ are consecutive integers for $n \in \mathbb{N}$, which would finish. Use induction, with $n=1$ trivial. We aim to show $a_1,\ldots,a_k$ are consecutive integers assuming that $a_1,\ldots,a_{k-1}$ are consecutive integers. Notice that the difference between any of these terms is at most $k-1$; otherwise, we have a contradiction when we set $n$ equal to this difference. Hence the only possible values of $a_k$ will continue the consecutive trend from either above or below. $\blacksquare$

Notice that for all $j>i$, we have \[ 0<|a_j-a_i|<j. \]This is because $a_j\equiv a_i\pmod{|a_j-a_i|}$ for $|a_j-a_i|>1$. We first prove $0$ occurs in the sequence. If $a_1=0$ we are done so assume $a_1\neq 0$. Let $a_{k+1}$ be the first term with opposite sign as $a_1$. Then \[ \max\{|a_1|,\ldots,|a_k|\}+|a_{k+1}|=\max\{|a_1-a_{k+1}|,\ldots,|a_k-a_{k+1}|\}\leq k. \]Since $|a_{k+1}|\geq 1$, it follows that \[ \max\{|a_1|,\ldots,|a_k|\}\leq k-1 \]so $|a_1|,\ldots,|a_k|$ is a permutation of $\{0,1,\ldots,k-1\}$. In particular, $0\in\{a_1,\ldots,a_k\}$. Suppose $a_s=0$. Let $n$ be a nonzero integer. Let $a_k$ be the $[\max(s,|n|)]$th term with the same sign as $n$, which exists because there are infinitely many positive and negative terms. Let $M$ and $-m$ be the maximum and minimum of $\{a_1,\ldots,a_k\}$, respectively. Since $0\in\{a_1,\ldots,a_k\}$, it follows that $M,m\geq 0$. We also have $M+m<k$. But $a_1,\ldots,a_k$ has $\leq M$ positive terms and $\leq m$ negative terms so $k\leq M+m+1$. It follows that $M+m=k-1$ and all inequalities are equalities. In particular, $a_1,\ldots,a_k$ has $M$ positive terms and $m$ negative terms so it is a permutation of $\{0,1,\ldots,M,-1,\ldots,-m\}$. By the definition of $k$, if $n$ is positive we have $M=k\geq n$, and if $n$ is negative we have $-m=-k\leq n$. In either case, $n\in\{a_1,\ldots,a_k\}$. $\square$

For the first part assume FTSOC that $a_i=a_j$, then these two terms will give a same residue modulo any $n$. For the second part, we start with a claim. Claim: the numbers $a_1, a_2, \dots, a_n$ are consecutive. We prove to at with induction, for the base case $n=1$ is trivial, now assume that $a_1,\dots, a_k$ are consecutive. We show that for $k+1$ as well. We can see that the difference is at most $k$ between these numbers, if not then we take mod that difference, this will give us a contradiction. Hence all numbers will continue to be consecutive starting from $1$, meaning it will cover all positive integers

Translate the sequence such that $a_1 = 0$, clearly this does not change anything. We claim that $\{a_1 \cdots a_n \}$ is always a group of consecutive $n$ elements, combined with the infinitely many positive and negative terms condition this finishes the problem. We prove this inductively. Let the largest nonnegative element be $x$ and the smallest nonpositive element be $y$, without loss of generality $x + y \ge 0$. If the next element added $j$ is positive and not $x + 1$, taking the first $j$ elements of the sequence, we see they all must be distinct mod $j$, except this is clearly false since $a_1 \equiv 0 \mod j$. If $j$ is negative and at least $-x - 1$ and not $y - 1$, taking the first $x - y + 1$ elements of the sequence we see that this fails since $-y \equiv -x - 1 \mod x - y + 1$, the former of which must be in the sequence as a consequence of $x + y \ge 0$. If $j$ is negative and less than $-x - 1$, an identical argument taking the first $j$ elements and considering $\mod j$ finishes. Since all cases where adding $j$ does not form a block of consecutive numbers are exhausted, we are done.

For injectivity, assume for the sake of a contradiction that $a_i = a_j,$ then they will be congruent mod any $n,$ a contradiction. For surjectivity, we will show by induction that $a_1, a_2, \dots, a_n$ are in some order consecutive integers. The base case, $n=1,$ is trivial so assume that the proposition holds for $n=k.$ Then for $a_{k+1},$ clearly $|a_{k+1}-a_i| < k+1$ for each $1 \leq i \leq n$ since otherwise taking mod $|a_{k+1}-a_i|$ would give $a_{k+1} \equiv a_i,$ a contradiction. Thus for $a_{k+1}$ to be distinct from the rest it must either be $\max\{a_1, a_2, \dots, a_n\}+1$ or $\min\{ a_1, a_2, \dots, a_n\}-1,$ and this finishes our induction. Thus the sequence is bijective to the set of integers and we are done. QED

We claim $\{a_1,a_2,\dots a_n\}\equiv \{x,(x+1),\dots,(x+n-1)\}$ for some integer $x$ and we prove by induction. Proof: Just check that the condition of the problem is equivalent to: $M-j<a_j<m+j$, where $M,m=max,min(a_1, a_2, \dots a_n)$ and $a_i\neq a_j \forall i<j$. The base case is clear for $a_1-1\leq a_j \leq a_1+1$. and if it was true for $a_1,a_2,\dots a_n$, that is $\{a_1,a_2,\dots a_n\}\equiv \{x,(x+1),\dots,(x+n-1)\}$, then $x+n-1-n-1<a_{n+1}<x+n+1$, in other words $a_n=\{x-1,x+n\}$, as desired. The fact that there're infinitely many positive and negative terms complete the problem.

Obviously, the sequence is injective. Otherwise, suppose $a_i=a_j$ and take $n=\max({i,j})$ to see that $a_i\equiv aj \pmod n .$ Thus, it suffices to show that the sequence is surjective. The main idea is to prove that the first $n$ terms are always consecutive. We proceed by induction. Claim$|a_{i+l}-a_i| \leq i+l-1 $ for all positive integers $ i $ and $l.$ Proof: Otherwise, $a_{i+l} \equiv a_i \pmod{|a_{i+l}-a_i|}$ which is a contradiction. For $i=l=1,$ $|a_2-a_1|\leq 1$ and the sequence is injective thus, $a_1$ and $a_2$ are consecutive. Suppose now that the first $n$ terms are consecutive. Ovserve that $|a_{n+1}-a_i|\leq n $ for all $1\leq i \leq n$ to see that the distance from the new term to the previous consecutive terms is at most the number of terms which means that either $a_{n+1}=\max({a_1,\dots a_n})+1$ or $a_{n+1}=\min({a_1,\cdots a_n})-1$. In both cases, the first $n+1$ terms are also consecutive and we're done. The condition of positive and negative terms is simply saying $a_{n+1}$ is chosen as the minimum value -1 and maximum +1, both , infinitely many times. Thus, the sequence is bijective and we're done.

Very cool ideas! Note that $a_i \ne a_j \forall i \ne j$ as otherwise $a_i \equiv a_j \pmod{\max(i, j)}$, contradiction. Now the main claim is as follows: Claim: For all $i < j$, we have $|a_i - a_j| < j$. Proof: Assume $|a_i - a_j| = k \ge j$, then we have $$a_i \equiv a_j \pmod{k},$$a contradiction to the fact that $a_1, a_2, \dots, a_k$ are distinct $\pmod{k}$. $\square$ From here we can prove by induction that $a_1, a_2, \dots, a_n$ always form a group of $n$ consecutive numbers by induction, and then we're done because of the infinitely many positive and negative terms. (In particular, we have to choose the "lower" option infinitely many times as well as the "upper" option, so we end up covering the entirety of $\mathbb{Z}$. $\blacksquare$