Question

Para enteros positivos $n$ y $k,$ sea $f(n, k)$ el residuo cuando $n$ se divide entre $k,$ y para $n \gt 1$ sea $F(n) = \max_{1 \le k \le \frac{n}{2}} f(n, k).$ Halla el residuo cuando $\sum_{n = 20}^{100} F(n)$ se divide entre $1000.$

For positive integers $n$ and $k,$ let $f(n, k)$ be the remainder when $n$ is divided by $k,$ and for $n \gt 1$ let $F(n) = \max_{1 \le k \le \frac{n}{2}} f(n, k).$ Find the remainder when $\sum_{n = 20}^{100} F(n)$ is divided by $1000.$

Respuesta

Solución:

Para $k \le \frac{n}{2}$ el cociente $\lfloor n/k \rfloor$ es al menos $2,$ así que el residuo satisface $f(n, k) \le n - 2k$ al igual que $f(n, k) \le k - 1.$ Escribe $n = 3m + r$ con $r \in \{0, 1, 2\}.$ Al dividir entre $k = m + 1$ se obtiene cociente $2$ y residuo $m + r - 2,$ así que $F(n) \ge m + r - 2.$ Recíprocamente, para $k \ge m + 1,$ $f(n, k) \le n - 2k \le m + r - 2,$ y para $k$ más pequeño la cota $f(n, k) \le k - 1$ completa el trabajo: cuando $r = 2$ da a lo sumo $m$ para $k \le m + 1;$ cuando $r = 1$ da a lo sumo $m - 1$ para $k \le m;$ y cuando $r = 0$ da a lo sumo $m - 2$ para $k \le m - 1,$ mientras que $k = m$ divide $3m$ exactamente, dejando residuo $0.$ Por lo tanto $\begin{aligned} F(3m) &= m - 2, \\ F(3m + 1) &= m - 1, \\ F(3m + 2) &= m. \end{aligned}$

Agrupando $n = 20, \ldots, 100$ en tríos $3m - 1,$ $3m,$ $3m + 1$ para $m = 7, \ldots, 33$ (nota que $F(3m - 1) = F(3(m-1) + 2)$ $= m - 1$ ), cada trío aporta $(m - 1) + (m - 2) + (m - 1)$ $= 3m - 4,$ así que $\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.$

For $k \le \frac{n}{2}$ the quotient $\lfloor n/k \rfloor$ is at least $2,$ so the remainder satisfies $f(n, k) \le n - 2k$ as well as $f(n, k) \le k - 1.$ Write $n = 3m + r$ with $r \in \{0, 1, 2\}.$ Dividing by $k = m + 1$ gives quotient $2$ and remainder $m + r - 2,$ so $F(n) \ge m + r - 2.$ Conversely, for $k \ge m + 1,$ $f(n, k) \le n - 2k \le m + r - 2,$ and for smaller $k$ the bound $f(n, k) \le k - 1$ finishes the job: when $r = 2$ it gives at most $m$ for $k \le m + 1;$ when $r = 1$ it gives at most $m - 1$ for $k \le m;$ and when $r = 0$ it gives at most $m - 2$ for $k \le m - 1,$ while $k = m$ divides $3m$ exactly, leaving remainder $0.$ Hence $\begin{aligned} F(3m) &= m - 2, \\ F(3m + 1) &= m - 1, \\ F(3m + 2) &= m. \end{aligned}$

Grouping $n = 20, \ldots, 100$ as triples $3m - 1,$ $3m,$ $3m + 1$ for $m = 7, \ldots, 33$ (note $F(3m - 1) = F(3(m-1) + 2)$ $= m - 1$ ), each triple contributes $(m - 1) + (m - 2) + (m - 1)$ $= 3m - 4,$ so $\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.$

2013 AIME II Problema 14

Solución:

El Problema 14 en otros años