Question

Para cada entero positivo $n,$ sea $f(n)$ la suma de los dígitos en la representación en base cuatro de $n$ y sea $g(n)$ la suma de los dígitos en la representación en base ocho de $f(n).$ Por ejemplo, $f(2020) = f(133210_4) = 10$ $= 12_8,$ y la suma de los dígitos de $12_8$ es $3,$ así que $g(2020) = 3.$ Sea $N$ el menor valor de $n$ tal que la representación en base dieciséis de $g(n)$ no se puede expresar usando solo los dígitos del $0$ al $9.$ Halle el residuo cuando $N$ se divide entre $1000.$

For each positive integer $n,$ let $f(n)$ be the sum of the digits in the base-four representation of $n$ and let $g(n)$ be the sum of the digits in the base-eight representation of $f(n).$ For example, $f(2020) = f(133210_4) = 10$ $= 12_8,$ and the digit sum of $12_8$ is $3,$ so $g(2020) = 3.$ Let $N$ be the least value of $n$ such that the base-sixteen representation of $g(n)$ cannot be expressed using only the digits $0$ through $9.$ Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

La representación en base dieciséis de $g(n)$ necesita un dígito mayor que $9$ exactamente cuando $g(n) \ge 10.$ Así que necesitamos que la suma de dígitos en base ocho de $f(n)$ sea al menos $10.$ Revisando los valores en orden, todo número menor que $31$ tiene suma de dígitos en base ocho a lo sumo $9,$ mientras que $31 = 37_8$ tiene suma de dígitos $10.$ Como el menor $n$ que alcanza una suma de dígitos en base cuatro dada crece con esa suma, buscamos el menor $n$ con $f(n) = 31.$

Un dígito en base cuatro es a lo sumo $3,$ así que una suma de dígitos de $31$ requiere al menos $11$ dígitos, y la menor elección de $11$ dígitos es un $1$ inicial seguido de diez $3$ s: $\begin{aligned} N &= 13333333333_4 \\ &= 4^{10} + (4^{10} - 1) \\ &= 2 \cdot 4^{10} - 1 = 2097151. \end{aligned}$

El residuo cuando $N = 2097151$ se divide entre $1000$ es $151.$

The base-sixteen representation of $g(n)$ needs a digit beyond $9$ exactly when $g(n) \ge 10.$ So we need the base-eight digit sum of $f(n)$ to be at least $10.$ Checking values in order, every number less than $31$ has base-eight digit sum at most $9,$ while $31 = 37_8$ has digit sum $10.$ Since the least $n$ achieving a given base-four digit sum increases with that sum, we want the least $n$ with $f(n) = 31.$

A base-four digit is at most $3,$ so a digit sum of $31$ requires at least $11$ digits, and the smallest $11$ -digit choice is a leading $1$ followed by ten $3$ s: $\begin{aligned} N &= 13333333333_4 \\ &= 4^{10} + (4^{10} - 1) \\ &= 2 \cdot 4^{10} - 1 = 2097151. \end{aligned}$

The remainder when $N = 2097151$ is divided by $1000$ is $151.$

2020 AIME II Problema 5

Solución:

El Problema 5 en otros años