Logo para LIVE por Po-Shen Loh

LIVE

2020 AIME II Problema 8

Intenta el Problema 8 del 2020 AIME II a continuación y luego compara tu respuesta con la solución preparada profesionalmente de LIVE by Po-Shen Loh. También puedes intentar el examen cronometrado completo, ver todas las soluciones del 2020 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).

8.

Defina una sucesión recursivamente por f1(x)=∣x−1∣f_1(x) = |x - 1| y fn(x)=fn−1(∣x−n∣)f_n(x) = f_{n-1}(|x - n|) para enteros n>1.n \gt 1. Halle el menor valor de nn tal que la suma de los ceros de fnf_n supere 500,000.500{,}000.
Define a sequence recursively by f1(x)=∣x−1∣f_1(x) = |x - 1| and fn(x)=fn−1(∣x−n∣)f_n(x) = f_{n-1}(|x - n|) for integers n>1.n \gt 1. Find the least value of nn such that the sum of the zeros of fnf_n exceeds 500,000.500{,}000.
Respuesta: 101
Conceptos:valor absolutorecursiónnúmero triangularinducción
Nivel de dificultad: 2920
Pista pequeña:
fn(x)=0f_n(x) = 0 exactamente cuando ∣x−n∣|x - n| es un cero no negativo de fn−1.f_{n-1}. Calcule los conjuntos de ceros para los primeros n.n.
fn(x)=0f_n(x) = 0 exactly when ∣x−n∣|x - n| is a nonnegative zero of fn−1.f_{n-1}. Compute the zero sets for the first few n.n.
Pista grande:
Con Tk=k(k+1)2,T_k = \frac{k(k+1)}{2}, los ceros de fnf_n son uno de cada dos enteros desde n−Tn−1n - T_{n-1} hasta Tn,T_n, por lo que su suma es n(1+n(n−1)2)n\left(1 + \frac{n(n-1)}{2}\right)
With Tk=k(k+1)2,T_k = \frac{k(k+1)}{2}, the zeros of fnf_n are every other integer from n−Tn−1n - T_{n-1} up to Tn,T_n, so their sum is n(1+n(n−1)2)n\left(1 + \frac{n(n-1)}{2}\right)
Solución:
Como fn(x)=fn−1(∣x−n∣),f_n(x) = f_{n-1}(|x - n|), los ceros de fnf_n son exactamente x=n±zx = n \pm z cuando zz recorre los ceros no negativos de fn−1.f_{n-1}. Los primeros conjuntos de ceros son {1},\{1\}, {1,3},\{1, 3\}, {0,2,4,6},\{0, 2, 4, 6\}, {−2,0,2,…,10}.\{-2, 0, 2, \ldots, 10\}. Escribiendo Tk=k(k+1)2,T_k = \frac{k(k+1)}{2}, afirmamos que los ceros de fnf_n son uno de cada dos enteros desde n−Tn−1n - T_{n-1} hasta Tn.T_n. En efecto, por inducción los ceros no negativos de fn−1f_{n-1} son uno de cada dos enteros desde 00 o 11 hasta Tn−1,T_{n-1}, y aplicando n±zn \pm z se obtiene todo entero de la paridad adecuada desde n−Tn−1n - T_{n-1} hasta n+Tn−1=Tn.n + T_{n-1} = T_n.
Esta progresión tiene Tn+Tn−1−n2+1=n(n−1)2+1\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−Tn−1)+Tn=2n,(n - T_{n-1}) + T_n = 2n, por lo que la suma de los ceros es Sn=n(n(n−1)2+1),S_n = n\left(\frac{n(n-1)}{2} + 1\right), que es creciente en n.n.
Ahora S100=100⋅4951S_{100} = 100 \cdot 4951 =495,100≤500,000,= 495{,}100 \le 500{,}000, mientras que S101=101⋅5051S_{101} = 101 \cdot 5051 =510,151>500,000.= 510{,}151 \gt 500{,}000. El menor nn con esa propiedad es 101.101.
Since fn(x)=fn−1(∣x−n∣),f_n(x) = f_{n-1}(|x - n|), the zeros of fnf_n are exactly x=n±zx = n \pm z as zz runs over the nonnegative zeros of fn−1.f_{n-1}. The first few zero sets are {1},\{1\}, {1,3},\{1, 3\}, {0,2,4,6},\{0, 2, 4, 6\}, {−2,0,2,…,10}.\{-2, 0, 2, \ldots, 10\}. Writing Tk=k(k+1)2,T_k = \frac{k(k+1)}{2}, we claim the zeros of fnf_n are every other integer from n−Tn−1n - T_{n-1} through Tn.T_n. Indeed, by induction the nonnegative zeros of fn−1f_{n-1} are every other integer from 00 or 11 up to Tn−1,T_{n-1}, and applying n±zn \pm z yields every integer of the appropriate parity from n−Tn−1n - T_{n-1} through n+Tn−1=Tn.n + T_{n-1} = T_n.
This progression has Tn+Tn−1−n2+1=n(n−1)2+1\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−Tn−1)+Tn=2n,(n - T_{n-1}) + T_n = 2n, so the sum of the zeros is Sn=n(n(n−1)2+1),S_n = n\left(\frac{n(n-1)}{2} + 1\right), which is increasing in n.n.
Now S100=100⋅4951S_{100} = 100 \cdot 4951 =495,100≤500,000,= 495{,}100 \le 500{,}000, while S101=101⋅5051S_{101} = 101 \cdot 5051 =510,151>500,000.= 510{,}151 \gt 500{,}000. The least such nn is 101.101.
Problema 7#7
Examen completo
Problema 9#9

El Problema 8 en otros años

1983 AIME · 1984 AIME · 1985 AIME · 1986 AIME · 1987 AIME · 1988 AIME · 1989 AIME · 1990 AIME · 1991 AIME · 1992 AIME · 1993 AIME · 1994 AIME · 1995 AIME · 1996 AIME · 1997 AIME · 1998 AIME · 1999 AIME · 2000 AIME I · 2000 AIME II · 2001 AIME I · 2001 AIME II · 2002 AIME I · 2002 AIME II · 2003 AIME I · 2003 AIME II · 2004 AIME I · 2004 AIME II · 2005 AIME I · 2005 AIME II · 2006 AIME I · 2006 AIME II · 2007 AIME I · 2007 AIME II · 2008 AIME I · 2008 AIME II · 2009 AIME I · 2009 AIME II · 2010 AIME I · 2010 AIME II · 2011 AIME I · 2011 AIME II · 2012 AIME I · 2012 AIME II · 2013 AIME I · 2013 AIME II · 2014 AIME I · 2014 AIME II · 2015 AIME I · 2015 AIME II · 2016 AIME I · 2016 AIME II · 2017 AIME I · 2017 AIME II · 2018 AIME I · 2018 AIME II · 2019 AIME I · 2019 AIME II · 2020 AIME I · 2021 AIME I · 2021 AIME II · 2022 AIME I · 2022 AIME II · 2023 AIME I · 2023 AIME II · 2024 AIME I · 2024 AIME II · 2025 AIME I · 2025 AIME II · 2026 AIME I · 2026 AIME II