Competition problem — Combinatorics

Library / /16 of 56

Combinatorics Difficulty 5.3 AIME, harder Prove it Singapore

Let $a_1, a_2, \dots$ be a sequence of integers defined recursively by $a_1 = 2013$ and for $n \ge 1$ , $a_{n+1}$ is the sum of the $2013$ th power of the digits of $a_n$ . Do there exist distinct positive integers $i, j$ such that $a_i = a_j$ ?

Solution

The answer is yes. For any positive integer $n$ , let $f(n)$ be the sum of $2013$ th power of the digits of $n$ . Let $S = \{1, 2, \dots, 10^{2017} - 1\}$ , and $n = \overline{a_1a_2\dots a_{2017}} \in S$ . Then
$f(n) = \sum a_i^{2013} \le 2017 \cdot 9^{2013} < 10^4 \cdot 10^{2013} = 10^{2017} \in S.$
Since $a_i = f^{(i)}(2013) \in S$ , there exist distinct positive integers $i, j$ such that $a_i = a_j$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.