Question

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

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

Respuesta

Respuesta: 185

Conceptos:particiones y composiciones permutaciones de multiconjuntos análisis por casos acotación a casos límite

Nivel de dificultad: 3370

Pista pequeña:

Los valores consecutivos difieren en $1,$ $2,$ o $3$ en valor absoluto y las seis diferencias suman $12;$ demuestra que a lo sumo una diferencia puede ser negativa

Consecutive values differ by $1,$ $2,$ or $3$ in absolute value and the six differences sum to $12;$ show at most one difference can be negative

Pista grande:

Trata tres casos: sin descenso; un descenso en algún extremo; un descenso interior, que se ve forzado a ser $-1$ flanqueado por dos $+3$

Handle three cases: no decrease; a decrease at either end; an interior decrease, which is forced to be $-1$ flanked by two $+3$ s

Solución:

Sea $d_i = f(i) - f(i-1),$ de modo que cada $|d_i| \in \{1, 2, 3\}$ y $d_1 + \cdots + d_6 = 12.$ Si $k$ de las diferencias fueran negativas, la suma sería a lo sumo $3(6 - k) - k = 18 - 4k,$ así que $k \le 1.$ Si ninguna diferencia es negativa, las soluciones de $a + b + c = 6,$ $a + 2b + 3c = 12$ (con $a, b, c$ contando los $1$ , los $2$ y los $3$ ) son $(0,6,0),$ $(1,4,1),$ $(2,2,2),$ $(3,0,3),$ y todos esos ordenamientos satisfacen las condiciones para cada par, lo que da $\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 $d_1 \lt 0,$ entonces $|f(2)| \ge 2$ junto con $f(2) \le d_1 + 3$ obliga a $d_1 = -1$ y $d_2 = 3;$ las cuatro diferencias restantes son positivas y suman $10,$ lo que da $\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10$ funciones, y el caso $d_6 \lt 0$ es simétrico: $20$ en total. Por último, si $d_{n+1} \lt 0$ para algún $n = 1, 2, 3, 4,$ las condiciones de pares $|f(n+1) - f(n-1)| \ge 2$ y $|f(n+2) - f(n)| \ge 2$ obligan a $d_{n+1} = -1$ y $d_n = d_{n+2} = 3.$ Las otras tres diferencias son positivas y suman $7,$ lo que se logra con dos $3$ y un $1$ o con un $3$ y dos $2,$ cada uno en $3$ órdenes: $6$ maneras para cada una de las $4$ posiciones, o $24$ funciones.

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

Let $d_i = f(i) - f(i-1),$ so each $|d_i| \in \{1, 2, 3\}$ and $d_1 + \cdots + d_6 = 12.$ If $k$ of the differences were negative, the sum would be at most $3(6 - k) - k = 18 - 4k,$ so $k \le 1.$ If no difference is negative, the solutions of $a + b + c = 6,$ $a + 2b + 3c = 12$ (with $a, b, c$ counting $1$ s, $2$ s, $3$ s) are $(0,6,0),$ $(1,4,1),$ $(2,2,2),$ $(3,0,3),$ and all such orderings satisfy every pair condition, giving $\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 $d_1 \lt 0,$ then $|f(2)| \ge 2$ with $f(2) \le d_1 + 3$ forces $d_1 = -1$ and $d_2 = 3;$ the remaining four differences are positive and sum to $10,$ giving $\binom{4}{1,0,3} + \binom{4}{0,2,2} = 4 + 6 = 10$ functions, and the case $d_6 \lt 0$ is symmetric: $20$ in all. Finally, if $d_{n+1} \lt 0$ for some $n = 1, 2, 3, 4,$ the pair conditions $|f(n+1) - f(n-1)| \ge 2$ and $|f(n+2) - f(n)| \ge 2$ force $d_{n+1} = -1$ and $d_n = d_{n+2} = 3.$ The other three differences are positive and sum to $7,$ achievable as two $3$ s and a $1$ or a $3$ and two $2$ s, each in $3$ orders: $6$ ways for each of the $4$ positions, or $24$ functions.

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

2018 AIME II Problema 15

Respuesta: 185

Nivel de dificultad: 3370

Pista pequeña:

Pista grande:

Solución:

El Problema 15 en otros años