Question

Para enteros positivos $n,$ sea $\tau(n)$ el número de divisores enteros positivos de $n,$ incluyendo $1$ y $n.$ Por ejemplo, $\tau(1) = 1$ y $\tau(6) = 4.$ Defina $S(n)$ por $S(n) = \tau(1) + \tau(2) + \cdots + \tau(n).$ Sea $a$ el número de enteros positivos $n \le 2005$ con $S(n)$ impar, y sea $b$ el número de enteros positivos $n \le 2005$ con $S(n)$ par. Halle $|a - b|.$

For positive integers $n,$ let $\tau(n)$ denote the number of positive integer divisors of $n,$ including $1$ and $n.$ For example, $\tau(1) = 1$ and $\tau(6) = 4.$ Define $S(n)$ by $S(n) = \tau(1) + \tau(2) + \cdots + \tau(n).$ Let $a$ denote the number of positive integers $n \le 2005$ with $S(n)$ odd, and let $b$ denote the number of positive integers $n \le 2005$ with $S(n)$ even. Find $|a - b|.$

Respuesta

Solución:

Los divisores de $n$ se emparejan como $d$ y $\frac{n}{d},$ así que $\tau(n)$ es impar exactamente cuando $n$ es un cuadrado perfecto. Por tanto $S(n)$ cambia de paridad exactamente en los cuadrados, lo que significa que $S(n)$ es impar exactamente cuando el número de cuadrados hasta $n,$ a saber $\lfloor\sqrt{n}\rfloor,$ es impar.

Para cada $k,$ hay $2k + 1$ enteros $n$ con $\lfloor\sqrt{n}\rfloor = k,$ a saber $k^2 \le n \le k^2 + 2k.$ Como $44^2 = 1936$ $\le 2005$ $\lt 2025 = 45^2,$ los valores impares $k = 1, 3, \ldots, 43$ tienen todos sus bloques completos dentro del rango, así que $\begin{aligned} a &= \sum_{k \text{ odd},\, k \le 43} (2k + 1) \\ &= 2(1 + 3 + \cdots + 43) + 22 \\ &= 2 \cdot 484 + 22 \\ &= 990. \end{aligned}$

Entonces $b = 2005 - 990 = 1015,$ y $|a - b| = 25.$

Divisors of $n$ pair up as $d$ and $\frac{n}{d},$ so $\tau(n)$ is odd exactly when $n$ is a perfect square. Hence $S(n)$ changes parity exactly at the squares, which means $S(n)$ is odd exactly when the number of squares up to $n,$ namely $\lfloor\sqrt{n}\rfloor,$ is odd.

For each $k,$ there are $2k + 1$ integers $n$ with $\lfloor\sqrt{n}\rfloor = k,$ namely $k^2 \le n \le k^2 + 2k.$ Since $44^2 = 1936$ $\le 2005$ $\lt 2025 = 45^2,$ the odd values $k = 1, 3, \ldots, 43$ all have their full blocks within range, so $\begin{aligned} a &= \sum_{k \text{ odd},\, k \le 43} (2k + 1) \\ &= 2(1 + 3 + \cdots + 43) + 22 \\ &= 2 \cdot 484 + 22 \\ &= 990. \end{aligned}$

Then $b = 2005 - 990 = 1015,$ and $|a - b| = 25.$

2005 AIME I Problema 12

Solución:

El Problema 12 en otros años