2020 AIME II Problem 14

Below is the professionally curated solution for Problem 14 of the 2020 AIME II, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:floor and ceiling functionsfunctionPascal’s Triangle

Difficulty rating: 3160

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.

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,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, so the remainder when NN is divided by 10001000 is 10.10.

← Problem 13Full ExamProblem 15

Problem 14 in Other Years