¿Existe una solución general de esta 'Contar los números de' juego?

Question

Hace un par de días, un amigo mío me enseñó un número del juego. Puede ser famoso, pero yo no he sabido de ella. Les voy a mostrar a usted.

Imagina que tienes una especie de página de un calendario de días, y que juega un número de juego de cada mañana. La página de hoy' en la página dice lo siguiente:

"8 11 2013.
Cuántas $0$s son en este papel? La respuesta es $()$.
Cuántas $1$s son en este papel? La respuesta es $()$.
Cuántas $2$s son en este papel? La respuesta es $()$.
Cuántas $3$s son en este papel? La respuesta es $()$.
Cuántas $4$s son en este papel? La respuesta es $()$.
Cuántas $5$s son en este papel? La respuesta es $()$.
Cuántas $6$s son en este papel? La respuesta es $()$.
Cuántas $7$s son en este papel? La respuesta es $()$.
Cuántas $8$s son en este papel? La respuesta es $()$.
Cuántas $9$s son en este papel? La respuesta es $()$."

Este juego es bastante simple. Llenar los espacios en blanco. Por supuesto, la respuesta es no el siguiente.

"8 11 2013.
Cuántas $0$s son en este papel? La respuesta es $(2)$.
Cuántas $1$s son en este papel? La respuesta es $(4)$.
Cuántas $2$s son en este papel? La respuesta es $(2)$.
Cuántas $3$s son en este papel? La respuesta es $(2)$.
Cuántas $4$s son en este papel? La respuesta es $(1)$.
Cuántas $5$s son en este papel? La respuesta es $(1)$.
Cuántas $6$s son en este papel? La respuesta es $(1)$.
Cuántas $7$s son en este papel? La respuesta es $(1)$.
Cuántas $8$s son en este papel? La respuesta es $(2)$.
Cuántas $9$s son en este papel? La respuesta es $(1)$."

Este juego es bastante simple, pero no es muy fácil. El punto clave es que usted tiene que contar los números que usted escribe en los espacios en blanco así! Entonces, he estado luchando para resolver el hoy del juego, y ahora tengo una de las respuestas.

"8 11 2013.
Cuántas $0$s son en este papel? La respuesta es $(2)$.
Cuántas $1$s son en este papel? La respuesta es $(7)$.
Cuántas $2$s son en este papel? La respuesta es $(6)$.
Cuántas $3$s son en este papel? La respuesta es $(3)$.
Cuántas $4$s son en este papel? La respuesta es $(1)$.
Cuántas $5$s son en este papel? La respuesta es $(1)$.
Cuántas $6$s son en este papel? La respuesta es $(2)$.
Cuántas $7$s son en este papel? La respuesta es $(2)$.
Cuántas $8$s son en este papel? La respuesta es $(2)$.
Cuántas $9$s son en este papel? La respuesta es $(1)$."

Acabo de probar y disfrutar de ella. Te darás cuenta de lo difícil que es! Para ser honesto, me dieron esta respuesta sólo por casualidad.

Entonces, aquí están mis preguntas.

Pregunta1: ¿existe una solución general de este juego, excepto por el uso de la computadora?

Pregunta2: ¿Podemos obtener una respuesta de por vida?

Pregunta3: Podemos generalizar este juego?

Mi respuesta para Pregunta3 es la famosa pregunta:

Pregunta: Encontrar todos los enteros-secuencias de $(x_0, x_1, \cdots, \ x_n)$ tal que $x_j$ es igual al número de $j$ que aparecen en la secuencia para cada $j\ (0 \le j\le n). $

La respuesta: $$(2, 0, 2, 0), (1, 2, 1, 0), (2, 1, 2, 0, 0), (p, 2, 1, 0, 0, \cdots, 0, 1, 0, 0, 0)$$ $\ (p \ge 3$ y $\:\text{the number of $0$s sandwiched by two $1$s is $p-3$})$

Prueba: Supongamos que la secuencia de $(x_1, x_2, \cdots, \ x_n)$ satisface la condición. Desde $x_j$ es igual al número de $j$ que aparecen en la secuencia, tenemos que $x_j$ es un entero no negativo y $x_j\le {n+1}$. Aquí, si no existe $i$ tal que $x_i=n+1$, el número de $\ i\ $s es $n+1$. En otras palabras, cada índice es $i$. Entonces, tenemos una contradicción: $x_i=n+1=i\le n$. Por lo tanto, obtenemos $0\le x_i\le n$ cualquier $i\ (0\le i\le n)$.

Si $x_0=0$, $x_0$ sí es $0$, por lo que tenemos una contradicción. Por lo tanto, $x_0\gt0$. Deje que el número de los números positivos en $x_1, x_2, \cdots, x_n$$m$. Suponiendo que $x_0=p\ (\ge1)$, obtenemos $x_p\ge 1$. Por lo tanto, obtenemos $m\ge 1$.Aquí, desde $S=\sum_{i=1}^nx_i$ significa contar los números de$\ \ge1$ en la secuencia, obtenemos $S=m+1$. (esto es debido a que $x_0\gt 0$ y porque tenemos $m$ los índices de cada uno de los cuales es$1$$x_1, x_2, \cdots, x_n$.) Desde $m$ positivos índices en $S$, obtenemos que la una es $2$ y el otro$m-1$$1$. Por lo tanto, tenemos que el índice que es de más de $2$ es, incluso si existe, sólo $x_0$, y que si $x_j\gt0$$j\gt2$, obtenemos $j=x_0$. Luego, desde los enteros positivos $j$ tal que $x\ge1$ debe ser cualquiera de $j=1, 2, x_0$, obtenemos $m\le3$. En la siguiente, hemos separado en tres de los casos por el valor de $m$. Tenga en cuenta que los números de $1$s y $2$s son, respectivamente,$m-1$$1$, y los restos son todos los $0$$x_1, x_2, \cdots, x_n$. Vamos a llamar a este aviso de Una.

1. El caso de $m=1$. Si $x_i=2$$i\not=2$, de acuerdo a Una, tenemos dos diferentes número de $2, i$$x_1, x_2, \cdots, x_n$. Esto contradice $m=1$. Por lo tanto, obtenemos $x_2=2$. Esta secuencia tiene sólo una $2$ a excepción de $x_2$. Sin embargo, de acuerdo a Una, cada índice de $x_1, x_2, \cdots, x_n$ $0$ a excepción de $x_2$, con lo que conseguimos $x_0=2$. Por lo tanto, obtenemos $(2, 0, 2, 0)$.

2. El caso de $m=2$. Llegamos $x_1=2$ o $x_2=2$. Por el mismo argumento anterior, obtenemos $(1, 2, 1, 0)$ $(2, 1, 2, 0, 0)$ respectivamente.

3. El caso de $m=3$. Llegamos $x_p\gt 0$$p\ge 3$. Por lo tanto, obtenemos $x_0=p, x_p=1$, con lo que conseguimos $x_1=2, x_2=1$. Ya que cada índice positivo se determina, obtenemos $$(p, 2, 1, 0, 0, \cdots, 0, 1, 0, 0, 0).$$ Note that the number of $0$s sandwiched by two $1$s is $p-3$.

Ahora la prueba se ha completado.

Answer 1

Esto no es una respuesta a todas sus preguntas de arriba. Yo intento de formalizar el problema por lo tanto, obtener una idea de la estructura de la solución. Para ese propósito vamos a $D:=\{1,\ldots,9\}$$i\in D$. Considere el sistema de ecuaciones

$ x_i = c_i + \sum_{j\D} \delta_{x_j,i} $

con $\delta_{i,j}$ la delta de Kronecker. Su pregunta 2, ahora se traduce a

P2: ¿este sistema tiene soluciones $x_i\in D$ por $c_i\in D$?

Entiendo @Nick R s comentario, de tal manera que uno puede refutar la existencia inicial para todos los valores de $c$ por una diagonal argumento. Sin embargo, para algunas opciones de $c_i$ solución podría existir y tu pregunta 1 es encontrar una solución sin tener que buscar a través de todas las posibilidades. Vamos a tratar de abordar ese.

Sumando obtenemos el invariante

$ I := \sum_{i\in D} x_i = 10 + \sum_{i\in D}c_i $

y las desigualdades, como por ejemplo

$ yo x_i + (1-\delta_{x_i,i}) x_i \leq I. $

Esto puede ser usado para reducir el espacio de búsqueda considerablemente. En el ejemplo que nos ha $c_0 := 2, c_1 := 4, c_2 := 2, c_3 := 2, c_4 = 1, c_5 = 1, c_6 = 1, c_7 = 1, c_8 = 2$ $c_9 = 1.$ Que los rendimientos de $ I = 27 $. Puesto que todas las $c_i$ son mayores que cero, nos encontramos con $x_0 = 2$. Las desigualdades que conducen a fuertes restricciones para la gran $i$. Consideremos $i=9$. Tenemos

$ 9 x_9 + (1-\delta_{x_9,9}) x_9 \leq 27. $

Esto excluye $x_9 = 9$ y, por tanto,$\delta_{x_9,9}=0$. Junto con $x_i\geq c_i$ y desde $x_i\in D$ tenemos

$ 1\leq x_9\leq 2. $

Es cierto que todavía no he tratado de abordar todo el problema, pero podría ser factible de ser resuelto con esta estrategia sin necesidad de un ordenador. Especialmente desde que las desigualdades probablemente con un poco de trabajo optimizados.

Su última pregunta sobre razonable generalizaciones del juego ahora puede ser parcialmente respondió con ayuda de dicho formalismo. Uno podría, por ejemplo, el uso de una base diferente a $D$ o ajustar las ecuaciones anteriores para $x_i$ a más de un dígito.