2020 AIME II Problem 14

Attempt Problem 14 of the 2020 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2020 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

14.

For real number xx let x\lfloor x \rfloor be the greatest integer less than or equal to x,x, and define {x}=xx\{x\} = x - \lfloor x \rfloor to be the fractional part of x.x. For example, {3}=0\{3\} = 0 and {4.56}=0.56.\{4.56\} = 0.56. Define f(x)=x{x},f(x) = x\{x\}, and let NN be the number of real-valued solutions to the equation f(f(f(x)))=17f(f(f(x))) = 17 for 0x2020.0 \le x \le 2020. Find the remainder when NN is divided by 1000.1000.

Answer: 10
Concepts:floor and ceiling functionsfunctionPascal’s Triangle
Difficulty rating: 3160
Solution:

On [k,k+1)[k, k+1) with k0k \ge 0 an integer, write x=k+t;x = k + t; then f(x)=(k+t)tf(x) = (k + t)t is strictly increasing from 00 toward k+1,k + 1, so ff maps [k,k+1)[k, k+1) bijectively onto [0,k+1).[0, k+1). Hence for any cc with n<c<n+1,n \lt c \lt n + 1, the equation f(w)=cf(w) = c has exactly one solution in [k,k+1)[k, k+1) for each integer kn,k \ge n, and no others.

The equation f(z)=17f(z) = 17 has one solution zn(n,n+1)z_n \in (n, n+1) for each n17.n \ge 17. In turn, f(w)=znf(w) = z_n has one solution in (k,k+1)(k, k+1) for each kn.k \ge n. Finally, for x[j,j+1)x \in [j, j+1) with 0j2019,0 \le j \le 2019, ff maps [j,j+1)[j, j+1) bijectively onto [0,j+1),[0, j+1), so the number of solutions of f(f(f(x)))=17f(f(f(x))) = 17 there equals the number of such ww with w<j+1,w \lt j + 1, namely the number of pairs (n,k)(n, k) with 17nkj,17 \le n \le k \le j, which is (j152).\binom{j - 15}{2}. (The endpoint x=2020x = 2020 gives f(x)=0f(x) = 0 and is not a solution.)

By the hockey stick identity, N=j=172019(j152)=a=22004(a2)=(20053)=2005200420036=1,341,349,010, \begin{aligned} N &= \sum_{j=17}^{2019} \binom{j - 15}{2} \\ &= \sum_{a=2}^{2004} \binom{a}{2} \\ &= \binom{2005}{3} \\ &= \frac{2005 \cdot 2004 \cdot 2003}{6} \\ &= 1{,}341{,}349{,}010, \end{aligned} so the remainder when NN is divided by 10001000 is 10.10.

← Problem 13#13
Full Exam

Problem 14 in Other Years