2018 AIME II Problem 15

Attempt Problem 15 of the 2018 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 2018 AIME II solutions, or check the answer key.

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

15.

Find the number of functions ff from {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\} to the integers such that f(0)=0,f(0) = 0, f(6)=12,f(6) = 12, and xyf(x)f(y)3xy \begin{aligned} |x - y| &\le |f(x) - f(y)| \\ &\le 3|x - y| \end{aligned} for all xx and yy in {0,1,2,3,4,5,6}.\{0, 1, 2, 3, 4, 5, 6\}.

Answer: 185
Concepts:partitions and compositionsmultiset permutationscaseworkbounding to limit cases
Difficulty rating: 3370
Solution:

Let di=f(i)f(i1),d_i = f(i) - f(i-1), so each di{1,2,3}|d_i| \in \{1, 2, 3\} and d1++d6=12.d_1 + \cdots + d_6 = 12. If kk of the differences were negative, the sum would be at most 3(6k)k=184k,3(6 - k) - k = 18 - 4k, so k1.k \le 1. If no difference is negative, the solutions of a+b+c=6,a + b + c = 6, a+2b+3c=12a + 2b + 3c = 12 (with a,b,ca, b, c counting 11s, 22s, 33s) are (0,6,0),(0,6,0), (1,4,1),(1,4,1), (2,2,2),(2,2,2), (3,0,3),(3,0,3), and all such orderings satisfy every pair condition, giving (60,6,0)+(61,4,1)+(62,2,2)+(63,0,3)=1+30+90+20=141. \begin{aligned} &\binom{6}{0,6,0} + \binom{6}{1,4,1} \\ &\quad {}+ \binom{6}{2,2,2} + \binom{6}{3,0,3} \\ &= 1 + 30 + 90 + 20 = 141. \end{aligned}

If d1<0,d_1 \lt 0, then f(2)2|f(2)| \ge 2 with f(2)d1+3f(2) \le d_1 + 3 forces d1=1d_1 = -1 and d2=3;d_2 = 3; the remaining four differences are positive and sum to 10,10, giving (41,0,3)+(40,2,2)=4+6=10\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10 functions, and the case d6<0d_6 \lt 0 is symmetric: 2020 in all. Finally, if dn+1<0d_{n+1} \lt 0 for some n=1,2,3,4,n = 1, 2, 3, 4, the pair conditions f(n+1)f(n1)2|f(n+1) - f(n-1)| \ge 2 and f(n+2)f(n)2|f(n+2) - f(n)| \ge 2 force dn+1=1d_{n+1} = -1 and dn=dn+2=3.d_n = d_{n+2} = 3. The other three differences are positive and sum to 7,7, achievable as two 33s and a 11 or a 33 and two 22s, each in 33 orders: 66 ways for each of the 44 positions, or 2424 functions.

The total is 141+20+24=185.141 + 20 + 24 = 185.

← Problem 14#14
Full Exam

Problem 15 in Other Years