Question

Sea $S$ la sucesión creciente de enteros positivos cuya representación binaria tiene exactamente $8$ unos. Sea $N$ el $1000$ -ésimo número de $S.$ Halle el residuo cuando $N$ se divide entre $1000.$

Let $S$ be the increasing sequence of positive integers whose binary representation has exactly $8$ ones. Let $N$ be the $1000$ th number in $S.$ Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Hay $\binom{12}{8} = 495$ elementos de $S$ por debajo de $2^{12}$ y $\binom{13}{8} = 1287$ por debajo de $2^{13},$ así que $N$ tiene $13$ dígitos binarios, y exactamente $1287 - 1000 = 287$ elementos por debajo de $2^{13}$ lo superan. Los $\binom{11}{6} = 462$ elementos cuya representación binaria empieza por $11$ son los mayores, así que $N$ empieza por $11$ y es el $462 - 287 = 175$ -ésimo menor de ellos.

Entre estos, $\binom{9}{6} = 84$ empiezan por $1100,$ los siguientes $\binom{8}{5} = 56$ empiezan por $11010,$ y los siguientes $\binom{7}{4} = 35$ empiezan por $110110.$ Como $84 + 56 + 35 = 175,$ el número $N$ es el mayor elemento que empieza por $110110,$ a saber $1101101111000$ en binario.

Su valor es $2^{12} + 2^{11} + 2^9 + 2^8$ $+ 2^6 + 2^5 + 2^4 + 2^3 = 7032,$ así que el residuo al dividir entre $1000$ es $32.$

There are $\binom{12}{8} = 495$ members of $S$ below $2^{12}$ and $\binom{13}{8} = 1287$ below $2^{13},$ so $N$ has $13$ binary digits, and exactly $1287 - 1000 = 287$ members below $2^{13}$ exceed it. The $\binom{11}{6} = 462$ members whose binary representations begin $11$ are the largest ones, so $N$ begins with $11$ and is the $462 - 287 = 175$ th smallest of them.

Among these, $\binom{9}{6} = 84$ begin $1100,$ the next $\binom{8}{5} = 56$ begin $11010,$ and the next $\binom{7}{4} = 35$ begin $110110.$ Since $84 + 56 + 35 = 175,$ the number $N$ is the largest member beginning $110110,$ namely $1101101111000$ in binary.

Its value is $2^{12} + 2^{11} + 2^9 + 2^8$ $+ 2^6 + 2^5 + 2^4 + 2^3 = 7032,$ so the remainder upon division by $1000$ is $32.$

2012 AIME II Problema 7

Solución:

El Problema 7 en otros años