Estúpido juego de los números

Question

En ocasiones me encuentro con un recurrente ejemplo de la estupidez cuando enseño matemáticas, a saber, que alguien le pregunta si podemos jugar a un juego conocido en danés bajo el nombre de "bum", ya que la persona cree que ese juego tiene algo relevante que ver con las matemáticas.

El juego continúa de la siguiente manera

Usted tiene que decidir en un dígito decimal,$a$. Entonces la gente en la sala de contar a través de los números naturales, en turnos, cada persona gritando un número, a continuación, pasar a la siguiente persona. Pero cada vez que el número de gritar es divisible por $a$ o tiene el dígito $a$ en algún lugar, que la persona que grita "bum" en su lugar.

Hoy he respondido a la sugerencia de jugar a ese juego con $a=7$ diciendo, que he encontrado el juego de matemáticas relevancia. Pero si tuviéramos que hacer nada matemáticamente interesante de esto, deberíamos averiguar cuántas veces la palabra "vago" se gritó en un impecable "bum"-un juego que se ejecuta de $1$ a través de $10^6$.

Yo estima que esta cifra como $10^6-9^6\cdot \frac 67=544479.\overline{142857}$. Más tarde me escribió un fragmento de código de trabajo fuera de la respuesta exacta como $544480$.

Pregunta

Hay una buena manera para obtener la figura $544480$ matemáticamente sin necesidad de escribir un programa?

Answer 1

Ha $6$ dígitos, cada uno de los cuales debe ser en $[0,9]\setminus\{7\}$. Los restos modulo $7$ de los dígitos de los valores de $10^k$$k\in[0,5]$$1,3,2,6,4,5$, respectivamente, que son todos los invertible en a $\mathbb Z_7$. El grupo de los admisible dígitos como $[0,6]\cup\{8,9\}$. Si alguno de los dígitos es en $[0,6]$, mientras que el primero de esos dígitos varía a lo largo de $[0,6]$ el resto de la cantidad del modulo $7$ también varía de $[0,6]$, por lo que exactamente $1/7$ de dichos números son bummers. Eso deja sólo la $2^6=64$ números de que consta sólo de $8$s y $9$s, equivalente a $1$s y $2$s. Ya que la suma de los dígitos de los valores es un múltiplo de a $7$, esto es equivalente a $0$ $1$s. Así que la pregunta que queda es ¿cuántos subconjuntos de a $[1,6]$ agregar a a $0$ modulo $7$. No tenemos que probar todos los $64$ desde un subconjunto suma a $0$ si y sólo si su complemento. Los subconjuntos con menos de $3$ elementos son fáciles de encontrar: solo $\{\}$, $\{1,6\}$, $\{2,5\}$, $\{3,4\}$ agregar a a $0$. De los con $3$ elementos, solo necesitamos comprobar los contengan $1$, y de un momento de reflexión muestra que, de éstos, sólo $\{1,2,4\}$ califica. Que arroja un total de $2(1+3+1)=10$ $64$ subconjuntos que se suman a $0$, por lo que el número total de bummers es $10^6-\frac67(9^6-64)-64+10=544480$.

Esto también arroja algo de luz sobre el por qué de su estimación era tan bueno – fue sólo el $64$ números para que su estimación $64/7\simeq9.1$ fue de aproximadamente $1$.