Question

Sea $N$ la cantidad de enteros positivos menores o iguales que $2003$ cuya representación en base $2$ tiene más dígitos $1$ que dígitos $0$ . Halla el residuo de dividir $N$ 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

Respuesta: 155

Conceptos:base numérica combinaciones Triángulo de Pascal simetría

Nivel de dificultad: 2920

Pista pequeña:

Todo entero así tiene a lo sumo $11$ dígitos binarios; para los números de $(d+1)$ dígitos, cuenta según la cantidad de dígitos $1$ usando la fila $d$ del triángulo de Pascal.

Every such integer has at most $11$ binary digits; for $(d+1)$ -digit numbers, count by the number of $1$ ’s using row $d$ of Pascal’s triangle

Pista grande:

Las filas $0$ a $10$ contribuyen $\frac{2047 + 351}{2}$ números por simetría; luego descarta los enteros que califican de $2004$ a $2047.$

Rows $0$ through $10$ contribute $\frac{2047 + 351}{2}$ numbers by symmetry; then discard the qualifying integers from $2004$ to $2047.$

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$ dígitos $1$ más entre los $d$ dígitos restantes da $\binom{d}{k}$ números con $k + 1$ unos; los dígitos $1$ superan a los dígitos $0$ 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 dígitos $1$ entre once dígitos; 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

Respuesta: 155

Nivel de dificultad: 2920

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años