Question

Sea $N$ la cantidad de enteros positivos que son menores o iguales que $2003$ y cuya representación en base $2$ tiene más $1$ 's que $0$ 's. Halla el residuo cuando $N$ se divide entre $1000.$

Let $N$ be the number of positive integers that are less than or equal to $2003$ and whose base- $2$ representation has more $1$ 's than $0$ 's. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Como $2003 \lt 2^{11} = 2048,$ todo entero en cuestión tiene a lo sumo $11$ dígitos binarios. Un número binario de $(d+1)$ dígitos empieza con $1,$ y elegir $k$ $1$ 's más entre los $d$ dígitos restantes da $\binom{d}{k}$ números con $k + 1$ unos; los $1$ 's superan a los $0$ 's exactamente cuando $k \ge \frac{d}{2}.$ Así que la cuenta sobre todos los números hasta $2047$ es el total de las entradas en el centro o a la derecha del centro de las filas $0$ a $10$ del triángulo de Pascal.

Esas filas suman $1 + 2 + \cdots + 2^{10} = 2047,$ y las entradas centrales suman $\sum_{i=0}^{5}\binom{2i}{i}$ $= 1 + 2 + 6 + 20 + 70 + 252$ $= 351,$ así que por simetría la cuenta es $\frac{2047 + 351}{2} = 1199.$

Los $44$ enteros de $2004$ a $2047$ superan todos $1984 = 11111000000_2,$ así que cada uno tiene el prefijo $11111$ más al menos un $1,$ por lo que tiene al menos seis $1$ 's entre once dígitos, todos los $44$ fueron contados. Por lo tanto $N = 1199 - 44 = 1155,$ cuyo residuo al dividir entre $1000$ es $155.$

Since $2003 \lt 2^{11} = 2048,$ every integer in question has at most $11$ binary digits. A $(d+1)$ -digit binary number starts with $1,$ and choosing $k$ more $1$ 's among the remaining $d$ digits gives $\binom{d}{k}$ numbers with $k + 1$ ones; the $1$ 's outnumber the $0$ 's exactly when $k \ge \frac{d}{2}.$ So the count over all numbers up to $2047$ is the total of the entries on or to the right of the center of rows $0$ through $10$ of Pascal's triangle.

Those rows sum to $1 + 2 + \cdots + 2^{10} = 2047,$ and the central entries sum to $\sum_{i=0}^{5}\binom{2i}{i}$ $= 1 + 2 + 6 + 20 + 70 + 252$ $= 351,$ so by symmetry the count is $\frac{2047 + 351}{2} = 1199.$

The $44$ integers from $2004$ to $2047$ all exceed $1984 = 11111000000_2,$ so each has the prefix $11111$ plus at least one more $1,$ hence at least six $1$ 's among eleven digits — all $44$ were counted. Therefore $N = 1199 - 44 = 1155,$ whose remainder upon division by $1000$ is $155.$

2003 AIME I Problema 13

Solución:

El Problema 13 en otros años