Lemma 1: We are done if we can find, for some $k$, values $a_{i_1},\ldots,a_{i_k}$ such that \[ \frac{n^{k-1}a_{i_1} + n^{k-2}a_{i_2}+\cdots+n^0a_{i_k}}{n^k-1} \in \mathbb{Z}. \]Proof: Suppose such a $k$ and $(a_{i_1},\ldots,a_{i_k})$ exists. Then let \[ (b_1,b_2,\ldots) = (a_{i_1},\ldots,a_{i_k}, \ a_{i_1},\ldots,a_{i_k}, \ldots),\]so then by infinite geometric series sum, \begin{align*} \sum_{k\ge 1} \frac{b_k}{n^k} &= \frac{\frac{a_{i_1}}{n^1}+\cdots+\frac{a_{i_k}}{n^k}}{1 - \frac{1}{n^k}} \\ &= \frac{n^{k-1}a_{i_1} + n^{k-2}a_{i_2}+\cdots+n^0a_{i_k}}{n^k-1} \in \mathbb{Z}, \end{align*}as needed. $\blacksquare$ Lemma 2: There exists an infinite sequence $(x_1,x_2,\ldots)$ satisfying $x_i \in \{a_1,\ldots,a_n\}$ for each $i\ge 1$ and \[ Q_k:=\frac{n^{k-1}x_k + n^{k-2}x_{k-1}+\cdots+n^0x_1}{n^k} \in \mathbb{Z} \]for each $k\ge 1$. Proof: Induct on $k$. For $k=1$, set $x_1=a_n$, so then $a_n/n \in \mathbb{Z}$ since $a_n \equiv n \equiv 0 \pmod{n}$. Now, we want to find $x_{k+1} \in \{a_1,\ldots,a_n\}$ such that $n^kx_{k+1}+n^{k-1}x_k+\cdots+x_1\equiv 0 \pmod{n^{k+1}}$. Dividing this relation by $n^k$, we get \[ x_{k+1} \equiv -\left( \frac{n^{k-1}x_k+\cdots+x_1}{n^k}\right) \pmod{n}. \]Hence $x_{k+1} \equiv \ell \pmod{n}$ for some integer $\ell$, since by induction we know that the RHS above is an integer. Then set $x_{k+1} =a_\ell$, since $a_\ell \equiv \ell \pmod{n}$. This finishes the induction. $\blacksquare$ Lemma 3: [Main idea to get from denominators of form $n^k$ to get to denominators of form $n^k-1$] For any $a,b,c,d$, notice \[ Q = \frac{a}{b} = \frac{c}{d} \implies Q= \frac{a-c}{b-d}. \]Proof: Trivial. $\blacksquare$ Consider the infinite sequence $(x_1,x_2,\ldots)$ from Lemma 2. We claim $(Q_1,Q_2,\ldots)$ lies in a bounded interval. Indeed, it can be confirmed easily that if $a_{\text{min}}$ and $a_{\text{max}}$ are the minimum and maximum of $(a_i)$, then for all $k$, \[ \frac{1}{n} a_{\text{min}} \le Q_k \le \frac{1}{n-1}a_{\text{max}}. \]Therefore, since $(Q_k)$ is a bounded infinite sequence of integers, there exists some $k$ and $m$ such that $Q_k = Q_{k+m} =:Q$. Then \begin{align*} &\qquad Q = \frac{n^{k-1}x_k+\cdots+n^0x_1}{n^k} = \frac{n^{k+m-1}x_{k+m-1}+\cdots+n^0x_1}{n^{k+m}} \\ &\implies Q = \frac{n^{k+m-1}x_{k+m-1} + \cdots + n^kx_k}{n^{k+m}-n^k} = \frac{n^{m-1}x_{k+m-1} + \cdots + n^0x_k}{n^m-1}, \end{align*}where the last step follows from Lemma 3. Since $Q\in \mathbb{Z}$, we are done by Lemma 1.

Here's an interesting proof that sweeps most of the annoying details under the rug of analysis and topology: Define the maps $f_\ell \colon \{1,2,\ldots, n\}^{\mathbb{N}} \to \mathbb{R}/\mathbb{Z}$ by \[f_\ell((b_k)_{k \in \mathbb{N}}) = \sum_{k=1}^\ell \frac{b_k}{n^k}.\]One can show by induction on $\ell$ that the range of $f_\ell$ is $n^{-\ell}\mathbb{Z}/\mathbb{Z}$. Now let $f((b_k)_{k \in \mathbb{N}}) = \lim_{\ell \to \infty} f_\ell((b_k))$. Since \[\sum_{k=\ell+1}^\infty \frac{b_k}{n^k} \to 0\]uniformly as $\ell \to \infty$, we find that $f_\ell \to f$ uniformly. Therefore $f$ is the uniform limit of the continuous functions $f_\ell$ and is thus continuous; the range of $f$ is dense, since for all $x \in \mathbb{R}/\mathbb{Z}$ and $\ell$ we can find a $y$ with $d(x, f_\ell(y)) < n^{-\ell}$, where $d$ is the standard metric on $\mathbb{R}/\mathbb{Z}$. Then \[d(x, f(y)) < n^{-\ell} + \sup_z d(f_\ell(z), f(z)),\]which can be made arbitrarily small. On the other hand, by Tychonoff's theorem, the domain is compact. Thus the range of $f$ is a compact, dense subset of $\mathbb{R}/\mathbb{Z}$, so it must be the whole thing. Therefore, there is some $(b_k)$ with $f((b_k)) = 0$. This solves the problem.

We consider the set of positive integers at most $\frac{\max_i a_i}{n-1}$. Notice the series' sum can never exceed this. Actually, $b_k$ has to be periodic. Why? If I push an element to the left of $b_1$ such that $\frac{b_0}{n} + \frac 1n \sum_{l\ge 1} b_ln^{-l}$ then since $b_i$ are injective mod $n$, it follows that there exists one $b_i$ and this new sum is just $\frac{S+a_{-S}}{n}$ where $S=\sum_{l\ge 1} b_ln^{-l}$. After doing this for some time, I will hit the same $S$ twice, so the sequence must be periodic. Let $a_i=a_{i (\bmod\; n)}$. Consider a functional graph from this set to itself such that $x\rightarrow \frac{x+a_{-x}}{n}$, which is obviously an integer. If I start from any integer and travel this way, by pigeonhole principle, since I can travel as long as I want but there are at most $\frac{\max_i a_i}{n-1}$ distinct numbers that I travel, I will reach a number twice, i.e., I reach a cycle, call $x_1\rightarrow x_2\rightarrow \cdots \rightarrow x_k\rightarrow x_1$ Hence $x_2=\frac{x_1+a_{-x_1}}{n}$ $x_3=\frac{x_2+a_{-x_2}}{n}=x_1n^{-2}+\frac{a_{-x_1}}{n^2}+\frac{a_{-x_2}}{n}$ Eventually, we can see $x_1=x_1n^{-k} + \sum\limits_{i=1}^k a_{-x_i}n^{-k-1+i}$ Therefore, $b_l\equiv b_{l (\bmod\; k)}$ and $b_l=a_{-x_{k+1-l}}$ for $1\le l\le k$ works.

Evidently we may select integers \(z_0\), \(z_1\), \(z_2\), \(\ldots\) all in \(\{a_1,a_2,\ldots,a_n\}\) so that \[z_0+z_1n+\cdots+z^{k-1}n^{k-1}\equiv0\pmod{n^k}\]for each \(k\). Thus each of the numbers \[\frac{z_0}n,\quad\frac{z_1}n+\frac{z_0}{n^2},\quad\frac{z_2}n+\frac{z_1}{n^2}+\frac{z_0}{n^3},\quad\ldots\]are integers. Now since these integers are bounded, we may find \(k\) and \(\ell\) with \[\frac{z_{k-1}}n+\cdots+\frac{z_0}{n^k}=\frac{z_{k+\ell-1}}n+\cdots+\frac{z_0}{n^{k+\ell}}=:A.\]This implies that \[\frac{z_{k+\ell-1}}n+\cdots+\frac{z_k}{n^\ell}=\left(1-\frac1{n^\ell}\right)A.\] Finally, let \((b_1,b_2,\ldots)=(z_{k+\ell-1},\ldots,z_0,z_{k+\ell-1},\ldots,z_0,\ldots)\), so that \[\frac{b_1}n+\frac{b_2}{n^2}+\cdots=\frac{\frac{z_{k+\ell-1}}n+\cdots+\frac{z_k}{n^\ell}}{1-\frac1{n^\ell}}=\frac{z^{k-1}}n+\cdots+\frac{z_0}{n^\ell}=A,\]which is an integer.

Note that proving $n^k-1 \mid b_1n^{k-1}+b_2n^{k-2}+...+b_k$ for some $k$ is enough to prove the statement of the problem. Now let $b_k=c_2n-c_1, b_{k-1}=c_3n-c_2,...,b_1=c_{k+1}n-c_k$, such that the expression on the right reduces to $c_{k+1}n^k-c_1$. Hence, if we can force $c_{k+1}=c_1$ for some $k$, we're done. Observe that, given the constraints of the problem, $c_1$ can be freely chosen from the integers, and each subsequent $c_i$ is forced. Moreover, any repetition in this sequence of $c_i$'s finishes the problem, as if $c_i=c_j (i<j)$, set $c_i$ as $c_1$ and $c_j$ as $c_{k+1}$ to form a new sequence for which $c_1=c_{k+1}$. But this repetition can be easily forced—let $c_1$ be between $\text{min}(a_i)$ and $\text{max}(a_i)$, and as $c_{i+1}=\frac{c_i+a_j}{n}$ (for some appropriate $j$), the entire sequence is bounded between $\text{min}(a_i)$ and $\text{max}(a_i)$. As the sequence is infinite and composed wholly of integers, it must indeed have a repetition! Hence proved.

Actually, before I figured out the solution. I was wondering what on earth does we care about $a_1, a_2, \dots, a_n \pmod n$. Very very nice problem, congratulation. We show that there exist a finite sequence $c_1, c_2, \dots, c_t$ with $t$ terms such that $c_k \in \{a_1, a_2, \dots, a_n\}$ and \[ n^t-1 \mid \sum_{k=1}^t c_in^{t-k}\]The motivation is that if we let $b_k = c_{k'}$, where $k' \equiv k \pmod t$ and $1\le k' \le t$. We have \[\sum_{k=1}^\infty \frac{b_k}{n^k} = (\sum_{k=1}^t c_in^{t-k})(\frac{1}{n^t} + \frac{1}{n^{2t}} + \cdots) = ( \sum_{k=1}^t c_in^{t-k})\cdot \frac{1}{n^t-1} \], which is an integer. Now we prove our claim is true. Let $x_1 = a_n/n$ , $y_1 = a_n$. For $k \ge 2$, select $y_k \in \{a_1, a_2, \dots, a_n\}$ such that $n \mid y_k + x_{k-1}$ ($y_k$ is well-defined since $\{a_1, a_2, \dots, a_n\}$ forms a complete residue system modulo $n$) . And $x_k := (x_{k-1} + y_k)/n$. Note that $x_k$ is an integer. Denote $M = \max \{|a_1|, |a_2|, \dots, |a_n|\}$, then \[|x_k| = |\sum_{i=1}^k y_i n^{-i}| \le M(n^{-1}+n^{-2}+ \cdots n^{-k}) \le M/(n-1)\]Which means $\{x_k\}$ is bounded. Hence by pigeon hole, there exist $x_i = x_j$ for some $i<j$. That is \[ x_j = (x_i + y_{i+1} + y_{i+2}n + \cdots y_jn^{i-j-1})/n^{j-i}\]Which means \[ y_{i+1} + y_{i+2}n + \cdots y_jn^{i-j-1} = (n^{j-i}-1) x_i\]Let $t = i-j$, $c_k = y_{j+1-k}$ for $1 \le k \le t$. Then we are done.

Let $b_n(m)$ denote the number of $0$'s at the right end of the expansion of $m$ in base $n$. For example, $b_{10}(1010) = 1$. Define $a(m)\in \{a_1,a_2,\cdots,a_n\}$ such that $n\mid m+a(m)$ for all $m$. Define $c_0 = 1$ and for all $i\ge 1$, \[c_i = n^{i-1}\cdot \left[\frac{c_{i-1}}{n^{i-1}} + a\left(\frac{c_{i-1}}{n^{i-1}}\right)\right].\]This ensures $n^i\mid c_i$ for all $i$, as $n^0\mid 1$. Let $a = \max_i |a_i|$. Then it is clear that \[|c_i|\le an^{i-1}+an^{i-2}+\cdots + a < \frac{an^i}{n-1},\]so \[\frac{|c_i|}{n^i}<\frac{a}{n-1}.\]Thus the number of digits before the last $i$ instances of $0$ in $c_i$ is bounded. In particular, this means that for large enough $i$ and some particular $t$, we have \[c_{i+t} = c_i\cdot n^t.\]Thus we have a particular $\frac{c_i}{n^{i+t}}\cdot (n^t-1)$ that can be attained by summing the terms of a series of $\frac{b_k}{n^k}$ for $1\le k\le t$. Thus we can repeat the $b_k$ to yield a sum of $\frac{c_i}{n^i}$ which is an integer as desired.

Can someone help point out what I am doing wrong? $\frac{1}{n}+ \frac{1}{n^2} \cdots =\frac{1}{n-1} $ Scale everything up. Let $b_i = n-1$ Then it equals to 1?? an integer??

PickleSauce wrote: Can someone help point out what I am doing wrong? $\frac{1}{n}+ \frac{1}{n^2} \cdots =\frac{1}{n-1} $ Scale everything up. Let $b_i = n-1$ Then it equals to 1?? an integer?? If $n-1\notin \{a_1,a_2,\cdots,a_n\}$, then you cannot choose $b_i=n-1$.

Here's my solution The main claim is as follows: Claim: There exists a positive integer $k$, and integers $b_1,b_2,...,b_k\in\{a_1,a_2,\ldots, a_n\}$, such that $n^k-1 \mid b_1n^{k-1}+b_2n^{k-2}+...+b_k$. Proof: Consider a new (infinite) sequence, $c_1,c_2,...$, defined as follows: $c_x\in\{a_1,a_2,\ldots, a_n\}$ for all $x$, and $c_1+nc_2+n^2c_3+...+n^{x-1}c_x \equiv 0 \pmod{n^x}$ for all $x$. This exists and is unique, as the $a_i$s cover all residue classes modulo $n$. Now consider $d_x \coloneqq \frac{c_1+nc_2+n^2c_3+...+n^{x-1}c_x}{n^x}$. Obviously, $d_x$ is always an integer, and can only take finitely many values, as it is bounded both above and below. Hence, there must exist $i<j$ with $d_i=d_j$. Then, \begin{align*} &n^{j-1}c_j+n^{j-2}c_{j-1}+...+n^ic_{i+1} = d_jn^j-d_in^i = d_in^i(n^{j-i}-1) \\ \Rightarrow \qquad &n^{j-i-1}c_j+n^{j-i-2}c_{j-1}+...+c_{i+1} = d_i(n^{j-i}-1) \end{align*}Hence we can take $k=j-i$ and $b_x=c_{j+i-x}$ for $x=1,2,...,k$, as desired. \(\square\) Now to the main problem. I claim that we may take $b_1,b_2,...,b_k$ as in the claim, and $b_x=b_y$ whenever $x \equiv y \pmod{k}$. Obviously, this satisfies the first condition. For the second condition, note that given our construction, \begin{align*} \sum\limits_{m=1}^{\infty}\frac{b_m}{n^m} &= \sum\limits_{m=1}^{\infty}\frac{b_1n^{k-1}+b_2n^{k-2}+...+b_k}{(n^k)^m} \\ &= \sum\limits_{m=1}^{\infty}\frac{d_i(n^{k}-1)}{(n^k)^m} \qquad \textrm{(taking $d_i$ from the claim)}\ \\ &= d_i \end{align*}which is an integer. So we are done. \(\blacksquare\) Comment: The main leap of faith in solving this problem is guessing that the $b_i$s are periodic. This is motivated by the fact that the only condition given concerns divisibility, with no restrictions given on the size of the $a_i$s, making it very difficult to force $\sum\limits_{k=1}^{\infty}\frac{b_k}{n^k}$ to tend to an integer.

Define a sequence $(R)_{n \ge 0}$ where $R_0=1$ and $R_{i+1}$ is the unique positive integer such that $nR_{i+1} - R_i \in \{a_1, a_2, \dots, a_n\}$. This exists and is unique by the $n \mid a_i - i$ condition. Note that $\frac{\min a + R_i}{n} \le R_{i+1} \le \frac{\max a + R_i}{n}$, hence by some induction, $\frac{\min a}{n-1} \le R_{i+1} \le \frac{\max a}{n-1}$. Since $R$ is bounded, by the pigeonhole principle, $R$ is eventually periodic. Say $R_j, R_{j+1}, \dots R_{j+k}$ is one such periodic block (i.e. $R_{j-1} = R_{j+k}$). Then by the definition of $R$, we can safely choose $b$ such that \[ \sum_{k=1}^\infty \frac{b_k}{n^k} = \frac{nR_{j+k} - R_{j+k-1}}{n} + \frac{nR_{j+k-1} - R_{j+k-2}}{n^2} + \;\cdots\; + \frac{nR_{j+1} - R_{j}}{n^k} + \frac{nR_j - R_{j-1}}{n^{k+1}} + \frac{nR_{j+k} - R_{j+k-1}}{n^{k+2}} + \;\cdots,\]which telescopes to $R_{j+k}$, an integer, as desired. $\blacksquare$

My solution from when I wrote ELMO for storage: We construct only finite sequences instead of finite sequences with the required property i.e. for every $k$, we find a sequence $b_1,\cdots b_k$ such that $\sum_{i=1}^k \frac{b_i}{n^k}\in \mathbb{Z}$. For this, we proceed by induction. This is clear for $k=1$ and assume we have proved it for some $k$, then we have some $a_i$ such that $n|a_i+\sum_{i=1}^k \frac{b_i}{n^k}\in \mathbb{Z}$. Thus, $\frac{a_i}{n}+\sum_{i=1}^{k} \frac{b_i}{n^{i+1}}\in \mathbb{Z}$ and this concludes our proof of the finite case. Now, let these sequences be $S$ be the set of all these sequences. Some $a_i$ occurs as the first term of infinitely many of these sequences. We call this term as $b_1$ and now remove any sequence from $S$ that doesn't start with $a_1$, now there are infinitely many sequences in $S$ and infinitely many of them have a second term, so pick an $a_j$ that is the second term of infinitely many of them and label it as $b_2$ and trim $S$ to only have sequences starting with $b_1b_2$ and keep going. This will let us define a $b_k \forall k\in \mathbb{N}$. This sequence works by just showing that it is convergent as it is Cauchy and must converge to an integer by just comparing with sequences in $S$ which have high enough overlap with our sequence.

Step 1: Since $\sum\limits_{k=1}^{\infty}\frac{b_k}{n^k}$ is rational, it is clear that $(b_k)$ is eventually periodic. By expansion, it follows that $(b_k)$ is periodic for all $k \ge 1$, and if the repeating part is $c_0, c_1, \dots, c_{\ell-1}$, then $\sum\limits_{k=1}^{\infty}\frac{b_k}{n^k}$ being an integer is equivalent to \[ c_0+c_1 \cdot n + \dots + c_{\ell-1} \cdot n^{\ell-1} \equiv 0 \pmod{n^{\ell} - 1}. \]Thus, we just need to find $(c_i)$ with $c_i \in \{a_1, \dots, a_n\}$ such that the above congruence is satisfied. Step 2: Let $m$ and $M$ be the minimum and maximum of $(a_i)$, respectively. Then realize that over all choices of $\ell$ and $(c_i)$, the integer values of $(c_0+c_1 \cdot n + \dots + c_{\ell-1} \cdot n^{\ell-1})/(n^{\ell}-1)$ are bounded by $m/(n-1)$ and $M/(n-1)$; thus, the number of these values is finite. Let $G$ denote the digraph on these values given by $j \to (j+a_{-j \bmod{n}})/n$, which is clearly a well-defined adjacency. It is clear that there must exist a cycle $i_0 \to i_1 \to \dots \to i_{\ell - 1} \to i_0$. Step 3: Via some bash, it is easy to see that \[ i_0 = \frac{i_0}{n^{\ell}} + \sum_{j=0}^n a_{-i_j \bmod{n}} \cdot n^{-j} . \]Taking modulo $n^{\ell}-1$ of both sides, \[ i_0 \equiv i_0 + \sum_{j=0}^n a_{-i_j \bmod{n}} \cdot n^{\ell-j} \pmod{n^{\ell}-1}, \]so taking $c_j = a_{-i_{\ell-j} \bmod{n}}$ finishes.