Question

Halle el número de enteros positivos menores que $1000$ que se pueden expresar como la diferencia de dos potencias enteras de $2.$

Find the number of positive integers less than $1000$ that can be expressed as the difference of two integral powers of $2.$

Respuesta

Solución:

Una diferencia de potencias de $2$ es $2^a - 2^b = 2^b(2^c - 1)$ donde $c = a - b \ge 1.$ Como $2^c - 1$ es impar, la parte impar del número determina $c$ y la potencia de $2$ determina $b,$ así que pares distintos $(b, c)$ dan enteros distintos. Basta con contar los pares con $2^b(2^c - 1) \lt 1000.$

Para $c = 1, 2, \ldots, 9$ el factor $2^c - 1$ es $1, 3, 7, 15, 31, 63, 127, 255, 511,$ y el número de valores permitidos de $b$ es $10, 9, 8, 7, 6, 4, 3, 2, 1$ respectivamente (el conteo para $63$ baja a $4$ porque $63 \cdot 16 = 1008 \gt 1000,$ mientras que $31 \cdot 32 = 992$ todavía cabe).

El total es $10 + 9 + 8 + 7 + 6$ $+ 4 + 3 + 2 + 1 = 50.$

A difference of powers of $2$ is $2^a - 2^b = 2^b(2^c - 1)$ where $c = a - b \ge 1.$ Since $2^c - 1$ is odd, the odd part of the number determines $c$ and the power of $2$ determines $b,$ so distinct pairs $(b, c)$ yield distinct integers. It suffices to count pairs with $2^b(2^c - 1) \lt 1000.$

For $c = 1, 2, \ldots, 9$ the factor $2^c - 1$ is $1, 3, 7, 15, 31, 63, 127, 255, 511,$ and the number of allowed values of $b$ is $10, 9, 8, 7, 6, 4, 3, 2, 1$ respectively (the count for $63$ drops to $4$ because $63 \cdot 16 = 1008 \gt 1000,$ while $31 \cdot 32 = 992$ still fits).

The total is $10 + 9 + 8 + 7 + 6$ $+ 4 + 3 + 2 + 1 = 50.$

2021 AIME I Problema 3

Solución:

El Problema 3 en otros años