2018 AIME II Problema 15

A continuación está la solución preparada profesionalmente para el Problema 15 del 2018 AIME II, de LIVE by Po-Shen Loh. También puedes intentar el examen cronometrado completo, ver todas las soluciones del 2018 AIME II, o revisar la clave de respuestas.

Todos los problemas se usan con el permiso legal oficial de la Mathematical Association of America (MAA).

Conceptos:particiones y composicionespermutaciones de multiconjuntosanálisis por casosacotación a casos límite

Nivel de dificultad: 3370

15.

Halla el número de funciones ff de {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\} a los enteros tales que f(0)=0,f(0) = 0, f(6)=12,f(6) = 12, y xyf(x)f(y)3xy \begin{aligned} |x - y| &\le |f(x) - f(y)| \\ &\le 3|x - y| \end{aligned} para todo xx e yy en {0,1,2,3,4,5,6}.\{0, 1, 2, 3, 4, 5, 6\}.

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\}.

Solución:

Sea di=f(i)f(i1),d_i = f(i) - f(i-1), de modo que cada di{1,2,3}|d_i| \in \{1, 2, 3\} y d1++d6=12.d_1 + \cdots + d_6 = 12. Si kk de las diferencias fueran negativas, la suma sería a lo sumo 3(6k)k=184k,3(6 - k) - k = 18 - 4k, así que k1.k \le 1. Si ninguna diferencia es negativa, las soluciones de a+b+c=6,a + b + c = 6, a+2b+3c=12a + 2b + 3c = 12 (con a,b,ca, b, c contando los 11, los 22 y los 33) son (0,6,0),(0,6,0), (1,4,1),(1,4,1), (2,2,2),(2,2,2), (3,0,3),(3,0,3), y todos esos ordenamientos satisfacen cada condición de pares, lo que da (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}

Si d1<0,d_1 \lt 0, entonces f(2)2|f(2)| \ge 2 junto con f(2)d1+3f(2) \le d_1 + 3 obliga a d1=1d_1 = -1 y d2=3;d_2 = 3; las cuatro diferencias restantes son positivas y suman 10,10, lo que da (41,0,3)+(40,2,2)=4+6=10\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10 funciones, y el caso d6<0d_6 \lt 0 es simétrico: 2020 en total. Por último, si dn+1<0d_{n+1} \lt 0 para algún n=1,2,3,4,n = 1, 2, 3, 4, las condiciones de pares f(n+1)f(n1)2|f(n+1) - f(n-1)| \ge 2 y f(n+2)f(n)2|f(n+2) - f(n)| \ge 2 obligan a dn+1=1d_{n+1} = -1 y dn=dn+2=3.d_n = d_{n+2} = 3. Las otras tres diferencias son positivas y suman 7,7, lo que se logra con dos 33 y un 11 o con un 33 y dos 2,2, cada uno en 33 órdenes: 66 maneras para cada una de las 44 posiciones, o 2424 funciones.

El total es 141+20+24=185.141 + 20 + 24 = 185.

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.

← Problema 14#14Examen completo

El Problema 15 en otros años