Logo para LIVE por Po-Shen Loh

LIVE

2013 AIME II Problema 14

Intenta el Problema 14 del 2013 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 2013 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).

14.

Para enteros positivos nn y k,k, sea f(n,k)f(n, k) el residuo cuando nn se divide entre k,k, y para n>1n \gt 1 sea F(n)=max⁡1≤k≤n2f(n,k).F(n) = \max_{1 \le k \le \frac{n}{2}} f(n, k). Halla el residuo de ∑n=20100F(n)\sum_{n = 20}^{100} F(n) al dividirlo entre 1000.1000.
For positive integers nn and k,k, let f(n,k)f(n, k) be the remainder when nn is divided by k,k, and for n>1n \gt 1 let F(n)=max⁡1≤k≤n2f(n,k).F(n) = \max_{1 \le k \le \frac{n}{2}} f(n, k). Find the remainder when ∑n=20100F(n)\sum_{n = 20}^{100} F(n) is divided by 1000.1000.
Respuesta: 512
Conceptos:aritmética modularacotación a casos límitesumatoria
Nivel de dificultad: 3270
Pista pequeña:
Para k≤n2k \le \frac{n}{2} el cociente es al menos 2,2, así que el residuo es a lo sumo min⁡(k−1, n−2k);\min(k - 1,\ n - 2k); prueba kk cerca de n3\frac{n}{3}.
For k≤n2k \le \frac{n}{2} the quotient is at least 2,2, so the remainder is at most min⁡(k−1, n−2k);\min(k - 1,\ n - 2k); try kk near n3\frac{n}{3}
Pista grande:
Muestra que F(3m)=m−2,F(3m) = m - 2, F(3m+1)=m−1,F(3m+1) = m - 1, y F(3m+2)=m,F(3m+2) = m, cada uno alcanzado en k=m+1,k = m + 1, luego suma sobre el rango.
Show F(3m)=m−2,F(3m) = m - 2, F(3m+1)=m−1,F(3m+1) = m - 1, and F(3m+2)=m,F(3m+2) = m, each achieved at k=m+1,k = m + 1, then sum over the range
Solución:
Para k≤n2k \le \frac{n}{2} el cociente ⌊nk⌋\lfloor \frac{n}{k} \rfloor es al menos 2,2, así que el residuo satisface f(n,k)≤n−2kf(n, k) \le n - 2k al igual que f(n,k)≤k−1.f(n, k) \le k - 1. Escribe n=3m+rn = 3m + r con r∈{0,1,2}.r \in \{0, 1, 2\}. Al dividir entre k=m+1k = m + 1 se obtiene cociente 22 y residuo m+r−2,m + r - 2, así que F(n)≥m+r−2.F(n) \ge m + r - 2. Recíprocamente, para k≥m+1,k \ge m + 1, f(n,k)≤n−2k≤m+r−2,f(n, k) \le n - 2k \le m + r - 2, y para kk más pequeño la cota f(n,k)≤k−1f(n, k) \le k - 1 completa el trabajo: cuando r=2r = 2 da a lo sumo mm para k≤m+1;k \le m + 1; cuando r=1r = 1 da a lo sumo m−1m - 1 para k≤m;k \le m; y cuando r=0r = 0 da a lo sumo m−2m - 2 para k≤m−1,k \le m - 1, mientras que k=mk = m divide 3m3m exactamente, dejando residuo 0.0. Por lo tanto F(3m)=m−2,F(3m+1)=m−1,F(3m+2)=m. \begin{aligned} F(3m) &= m - 2, \\ F(3m + 1) &= m - 1, \\ F(3m + 2) &= m. \end{aligned}
Agrupando n=20,…,100n = 20, \ldots, 100 en tríos 3m−1,3m - 1, 3m,3m, 3m+13m + 1 para m=7,…,33m = 7, \ldots, 33 (nota que F(3m−1)=F(3(m−1)+2)F(3m - 1) = F(3(m-1) + 2) =m−1= m - 1), cada trío aporta (m−1)+(m−2)+(m−1)(m - 1) + (m - 2) + (m - 1) =3m−4,= 3m - 4, así que ∑n=20100F(n)=∑m=733(3m−4)=3⋅(7+33)⋅272−4⋅27=1620−108=1512. \begin{aligned} \tiny \sum_{n=20}^{100} F(n) &= \sum_{m=7}^{33} (3m - 4) \\ &= 3 \cdot \frac{(7 + 33) \cdot 27}{2} - 4 \cdot 27 \\ &= 1620 - 108 = 1512. \end{aligned}
El residuo pedido es 512.512.
For k≤n2k \le \frac{n}{2} the quotient ⌊nk⌋\lfloor \frac{n}{k} \rfloor is at least 2,2, so the remainder satisfies f(n,k)≤n−2kf(n, k) \le n - 2k as well as f(n,k)≤k−1.f(n, k) \le k - 1. Write n=3m+rn = 3m + r with r∈{0,1,2}.r \in \{0, 1, 2\}. Dividing by k=m+1k = m + 1 gives quotient 22 and remainder m+r−2,m + r - 2, so F(n)≥m+r−2.F(n) \ge m + r - 2. Conversely, for k≥m+1,k \ge m + 1, f(n,k)≤n−2k≤m+r−2,f(n, k) \le n - 2k \le m + r - 2, and for smaller kk the bound f(n,k)≤k−1f(n, k) \le k - 1 finishes the job: when r=2r = 2 it gives at most mm for k≤m+1;k \le m + 1; when r=1r = 1 it gives at most m−1m - 1 for k≤m;k \le m; and when r=0r = 0 it gives at most m−2m - 2 for k≤m−1,k \le m - 1, while k=mk = m divides 3m3m exactly, leaving remainder 0.0. Hence F(3m)=m−2,F(3m+1)=m−1,F(3m+2)=m. \begin{aligned} F(3m) &= m - 2, \\ F(3m + 1) &= m - 1, \\ F(3m + 2) &= m. \end{aligned}
Grouping n=20,…,100n = 20, \ldots, 100 as triples 3m−1,3m - 1, 3m,3m, 3m+13m + 1 for m=7,…,33m = 7, \ldots, 33 (note F(3m−1)=F(3(m−1)+2)F(3m - 1) = F(3(m-1) + 2) =m−1= m - 1), each triple contributes (m−1)+(m−2)+(m−1)(m - 1) + (m - 2) + (m - 1) =3m−4,= 3m - 4, so ∑n=20100F(n)=∑m=733(3m−4)=3⋅(7+33)⋅272−4⋅27=1620−108=1512. \begin{aligned} \tiny \sum_{n=20}^{100} F(n) &= \sum_{m=7}^{33} (3m - 4) \\ &= 3 \cdot \frac{(7 + 33) \cdot 27}{2} - 4 \cdot 27 \\ &= 1620 - 108 = 1512. \end{aligned}
The requested remainder is 512.512.
Problema 13#13
Examen completo
Problema 15#15

El Problema 14 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 · 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 · 2020 AIME II · 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