2018 AIME II Problem 15

Below is the professionally curated solution for Problem 15 of the 2018 AIME II, 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 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:partitions and compositionsmultiset permutationscaseworkbounding to limit cases

Difficulty rating: 3370

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|x - y| \le |f(x) - f(y)| \le 3|x - y| for all xx and yy in {0,1,2,3,4,5,6}.\{0, 1, 2, 3, 4, 5, 6\}.

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.\binom{6}{0,6,0} + \binom{6}{1,4,1} + \binom{6}{2,2,2} + \binom{6}{3,0,3} = 1 + 30 + 90 + 20 = 141.

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 14Full Exam

Problem 15 in Other Years