Show that there exists a sequence of positive integers $x_1, x_2,…x_n,…$ that satisfies the following two conditions: (i) Every positive integer appears exactly once, (ii) For every $n=1,2,…$ the partial sum $x_1+x_2+…+x_n$ is divisible by $n^n$.
Problem
Source: Cono Sur 2003 #6
Tags: number theory, cono sur
01.01.2023 10:25
salve pro LL e pro dr estranho , we'll do this by induction, the base is $x_1 = 1$. Suppose that $n^n$ divides $x_1 + \dots + x_n$ for $n = 1, \dots k$. Let $L$ be the smallest positive integer that doesn't appear in $x_1, \dots x_k$. Take $x_{k+1}$ in such a way that $x_{k+1} \equiv - (x_1 + \dots + x_k) ~(mod~(k+1)^{k+1})$ and $x_{k+1} \equiv - (x_1 + \dots + x_k) - L ~(mod~(k+2)^{k+2})$ (by chinese remainder theorem we can do it) and $x_{k+2} = L$. with this algorithm, we can guarantee the condition for all $n$ and we are done,
01.01.2023 12:04
How did you gaurantee that each positive integer appeared at least once?
01.01.2023 18:19
youthdoo wrote: How did you gaurantee that each positive integer appeared at least once? Plugging the smallest positive integer that still doesn't appear in at most 2 steps forward. With the CRT we can take the $x_{k+1}$ big enough in a way that it doesn't appear in the sequence yet.