Question

Sea $B$ el conjunto de todos los enteros binarios que pueden escribirse usando exactamente $5$ ceros y $8$ unos, donde se permiten ceros a la izquierda. Si se realizan todas las restas posibles en las que un elemento de $B$ se resta de otro, halla el número de veces que se obtiene el resultado $1$ .

Let $B$ be the set of all binary integers that can be written using exactly $5$ zeros and $8$ ones where leading zeros are allowed. If all possible subtractions are performed in which one element of $B$ is subtracted from another, find the number of times the answer $1$ is obtained.

Respuesta

Solución:

Debemos contar los pares de elementos de $B$ que difieren en $1,$ digamos $m$ y $m + 1.$ Sumar $1$ a un número binario convierte su bloque final $011\cdots1$ (un cero seguido de $k$ unos) en $100\cdots0,$ cambiando el número de unos en $1 - k.$ Ambos números tienen exactamente ocho unos precisamente cuando $k = 1:$ $m$ termina en $01,$ $m + 1$ termina en $10,$ y los dos números coinciden en todo lo demás.

Los primeros once dígitos comunes constan entonces de los siete unos y cuatro ceros restantes, y como se permiten ceros a la izquierda, cada disposición da un par válido: $\binom{11}{4} = 330.$ Cada par produce el resultado $1$ exactamente una vez, así que el total es $330.$

We must count pairs of elements of $B$ differing by $1,$ say $m$ and $m + 1.$ Adding $1$ to a binary number turns its trailing block $011\cdots1$ (a zero followed by $k$ ones) into $100\cdots0,$ changing the number of ones by $1 - k.$ Both numbers have exactly eight ones precisely when $k = 1:$ $m$ ends in $01,$ $m + 1$ ends in $10,$ and the two numbers agree everywhere else.

The shared first eleven digits then consist of the remaining seven ones and four zeros, and since leading zeros are allowed, every arrangement gives a valid pair: $\binom{11}{4} = 330.$ Each pair produces the answer $1$ exactly once, so the count is $330.$

2012 AIME I Problema 5

Solución:

El Problema 5 en otros años