Question

Defina una sucesión recursivamente por $f_1(x) = |x - 1|$ y $f_n(x) = f_{n-1}(|x - n|)$ para enteros $n \gt 1.$ Halle el menor valor de $n$ tal que la suma de los ceros de $f_n$ supere $500{,}000.$

Define a sequence recursively by $f_1(x) = |x - 1|$ and $f_n(x) = f_{n-1}(|x - n|)$ for integers $n \gt 1.$ Find the least value of $n$ such that the sum of the zeros of $f_n$ exceeds $500{,}000.$

Respuesta

Solución:

Como $f_n(x) = f_{n-1}(|x - n|),$ los ceros de $f_n$ son exactamente $x = n \pm z$ cuando $z$ recorre los ceros no negativos de $f_{n-1}.$ Los primeros conjuntos de ceros son $\{1\},$ $\{1, 3\},$ $\{0, 2, 4, 6\},$ $\{-2, 0, 2, \ldots, 10\}.$ Escribiendo $T_k = \frac{k(k+1)}{2},$ afirmamos que los ceros de $f_n$ son uno de cada dos enteros desde $n - T_{n-1}$ hasta $T_n.$ En efecto, por inducción los ceros no negativos de $f_{n-1}$ son uno de cada dos enteros desde $0$ o $1$ hasta $T_{n-1},$ y aplicando $n \pm z$ se obtiene todo entero de la paridad adecuada desde $n - T_{n-1}$ hasta $n + T_{n-1} = T_n.$

Esta progresión tiene $\frac{T_n + T_{n-1} - n}{2} + 1 = \frac{n(n-1)}{2} + 1$ términos, y sus términos primero y último suman $(n - T_{n-1}) + T_n = 2n,$ por lo que la suma de los ceros es $S_n = n\left(\frac{n(n-1)}{2} + 1\right),$ que es creciente en $n.$

Ahora $S_{100} = 100 \cdot 4951$ $= 495{,}100 \le 500{,}000,$ mientras que $S_{101} = 101 \cdot 5051$ $= 510{,}151 \gt 500{,}000.$ El menor $n$ con esa propiedad es $101.$

Since $f_n(x) = f_{n-1}(|x - n|),$ the zeros of $f_n$ are exactly $x = n \pm z$ as $z$ runs over the nonnegative zeros of $f_{n-1}.$ The first few zero sets are $\{1\},$ $\{1, 3\},$ $\{0, 2, 4, 6\},$ $\{-2, 0, 2, \ldots, 10\}.$ Writing $T_k = \frac{k(k+1)}{2},$ we claim the zeros of $f_n$ are every other integer from $n - T_{n-1}$ through $T_n.$ Indeed, by induction the nonnegative zeros of $f_{n-1}$ are every other integer from $0$ or $1$ up to $T_{n-1},$ and applying $n \pm z$ yields every integer of the appropriate parity from $n - T_{n-1}$ through $n + T_{n-1} = T_n.$

This progression has $\frac{T_n + T_{n-1} - n}{2} + 1 = \frac{n(n-1)}{2} + 1$ terms, and its first and last terms sum to $(n - T_{n-1}) + T_n = 2n,$ so the sum of the zeros is $S_n = n\left(\frac{n(n-1)}{2} + 1\right),$ which is increasing in $n.$

Now $S_{100} = 100 \cdot 4951$ $= 495{,}100 \le 500{,}000,$ while $S_{101} = 101 \cdot 5051$ $= 510{,}151 \gt 500{,}000.$ The least such $n$ is $101.$

2020 AIME II Problema 8

Solución:

El Problema 8 en otros años