Question

Sea $\begin{aligned} N &= \sum_{k=1}^{1000} k \\ &\quad {}\cdot \left(\lceil \log_{\sqrt{2}} k \rceil - \lfloor \log_{\sqrt{2}} k \rfloor\right). \end{aligned}$ Halla el residuo cuando $N$ se divide entre $1000.$ (Aquí $\lfloor x \rfloor$ denota el mayor entero que es menor o igual que $x,$ y $\lceil x \rceil$ denota el menor entero que es mayor o igual que $x.$ )

Let $\begin{aligned} N &= \sum_{k=1}^{1000} k \\ &\quad {}\cdot \left(\lceil \log_{\sqrt{2}} k \rceil - \lfloor \log_{\sqrt{2}} k \rfloor\right). \end{aligned}$ Find the remainder when $N$ is divided by $1000.$ (Here $\lfloor x \rfloor$ denotes the greatest integer that is less than or equal to $x,$ and $\lceil x \rceil$ denotes the least integer that is greater than or equal to $x.$ )

Respuesta

Solución:

La diferencia $\lceil x \rceil - \lfloor x \rfloor$ es igual a $1$ cuando $x$ no es entero y a $0$ cuando sí lo es. Ahora bien, $\log_{\sqrt{2}} k$ es entero exactamente cuando $k = (\sqrt{2})^j$ para algún entero $j,$ y para que $k$ sea entero, $j$ debe ser par, es decir, $k$ debe ser una potencia de $2.$ Las potencias que son a lo sumo $1000$ son $2^0, 2^1, \ldots, 2^9 = 512.$

Por lo tanto $\begin{aligned} N &= \sum_{k=1}^{1000} k - \sum_{j=0}^{9} 2^j \\ &= \frac{1000 \cdot 1001}{2} - 1023 \\ &= 500500 - 1023 = 499477, \end{aligned}$ y el residuo al dividir entre $1000$ es $477.$

The difference $\lceil x \rceil - \lfloor x \rfloor$ equals $1$ when $x$ is not an integer and $0$ when it is. Now $\log_{\sqrt{2}} k$ is an integer exactly when $k = (\sqrt{2})^j$ for some integer $j,$ and for $k$ to be an integer, $j$ must be even — that is, $k$ must be a power of $2.$ The powers at most $1000$ are $2^0, 2^1, \ldots, 2^9 = 512.$

Therefore $\begin{aligned} N &= \sum_{k=1}^{1000} k - \sum_{j=0}^{9} 2^j \\ &= \frac{1000 \cdot 1001}{2} - 1023 \\ &= 500500 - 1023 = 499477, \end{aligned}$ and the remainder upon division by $1000$ is $477.$

2007 AIME I Problema 7

Solución:

El Problema 7 en otros años