un problema de 1977 todos Olimpiada Matemática de la Unión Soviética

Question

Siete enanos están sentados en una mesa redonda. Cada uno tiene una taza, y algunas tazas de contener leche. Cada enano a su vez vierte toda su leche en los otros seis tazas, dividiéndolo en partes iguales entre ellos. Después de que el séptimo enano ha hecho esto, se encuentra que cada taza contiene nuevamente su cantidad inicial de la leche. ¿Qué cantidad de leche que hace cada taza contiene, si hubo 42 onzas de leche por completo?

El problema puede ser encontrada aquí Inutilidad Armario

Answer 1

Deje de $n+1$ ser el número de enanos, podemos poner $n=6$ más tarde. Podemos imaginar a un entrenamiento de la ronda de $n+1$ movimientos en que se realizó (el que trae de nuevo la configuración inicial), de modo que cada enano se han distribuido al menos una vez, y podemos entonces (por el momento) el número de los enanos $0,1,\ldots,n$, según el número de movimientos, ya que fueron más recientemente distribuidor. Podemos describir la distribución por una secuencia de $(x_0,x_1,\ldots,x_n)$ ($x_0=0$) de las cantidades según el número de ellos. Después de un movimiento, que nos renumerar los enanos de acuerdo con la misma regla, y encontrar un nuevo valor de $(x_0,x_1,\ldots,x_n)$, de nuevo con $x_0=0$. (Si usted encuentra renumeración enanos confuso, usted puede imaginar sus números fijos, enano número $$ n haciendo la distribución de cada momento, y todo el mundo pasando luego a su taza a la siguiente numeradas enano modulo $n+1$; el punto es que acaba de grabar, la correspondencia de los números de la cantidad, enanos y tazas de estar auxiliar.) Dejando a un lado $x_0$, que es siempre $0$, la transformación de $(x_1,\ldots,x_n)$ es lineal, y dada por la matriz (que actúan sobre vectores columna): $$ A = \begin{pmatrix}0&0&\ldots&0&1/n\\ 1&0&\ldots&0&1/n\\0&1&\ldots&0&1/n\\\vdots&\ddots&\ddots&0&1/n\\ 0&\ddots&0&1&1/n \end{pmatrix}. $$ Necesitamos encontrar un autovector de $A^{n+1}$ para el autovalor $1$.

Los autovalores de $\lambda$ de $Un$ que dan lugar a un autovalor de $A^{n+1}$ son aquellos con $\lambda^{n+1}=1$. Ahora $A$ es el compañero de la matriz del polinomio $P=X^n-\frac1n(X^{n-1}+\cdots+X+1)$, que es, por tanto, el mínimo y el polinomio característico de $A$. Claramente $$ tiene un autovalor $\lambda=1$ ($A$ es una columna estocástico de la matriz), el cual es fácilmente controlado a ser una raíz simple de $P$. Pero cualquier otra $n+1$-st raíz de la unidad es una raíz de $X^n+X^{n-1}+\cdots+X+1$, y ya que este polinomio es primo relativo a $P$ por la inspección, $A$ no tiene esas raíces como autovalor; el autovalor $1$ de $A^{n+1}$ va a ser sencillo, con los mismos vectores propios como los de la $\lambda=1$ de $Un$. Por lo tanto, podemos simplemente calcular los vectores propios, que es fácil; son los múltiplos escalares de $$ \begin{pmatrix}1\\2\\3\\\vdots\\n\end{pmatrix}. $$ Por último podemos elegir las múltiples con la suma de las entradas. Para $n=6$ y la suma de las entradas $42$ las múltiples es por $2$, por lo que la solución $x_i=2i$ por $i=0,1,\ldots,6$ en este caso.

Si no te gusta la idea de la exclusión de la taza vacía de consideraciones, que pueden incluir, que se extiende a $A$ a $(n+1)\times(n+1)$ de la matriz inicial de la fila cero, lo que es todavía una columna estocástico compañero de la matriz; el polinomio $P$ es multiplicada por el valor de $X$, pero los argumentos serán idénticos. La renumeración esquema se ha convertido el proceso en una forma muy simple de la cadena de Markov. Tenga en cuenta también que el esquema elimina cualquier dependencia en el orden en el que los enanos vacía su taza, que es irrelevante la condición de que cada enano vacía exactamente una vez, y que la formación de la ronda sigue el mismo orden como la siguiente "real" de la ronda de movimientos.