Un hermoso juego de monedas de oro y plata

Question

Una pila de monedas de plata que hay en la mesa.

Para cada paso nos puede quitar una moneda de plata y escribir el número de monedas de oro en un pedazo de papel, o se puede añadir una moneda de oro y escribir el número de monedas de plata en otra hoja de papel.

Nos detenemos cuando sólo las monedas de oro están a la izquierda.

Demostrar que la suma de los números en estos dos trabajos son iguales.

Trató de jugar el juego y parece que el problema de la derecha cada vez, pero no puedo pasar de ahí. Se hace por inducción?

Answer 1

El estado del juego puede ser desribed por $$(g,s,G,S),$$ donde $g$ es el número de monedas de oro sobre la mesa, $s$ es el número de monedas de plata sobre la mesa, $G$ es la suma de los números en el primer papel, y $S$ es la suma de los números en el segundo documento. El estado inicial es de $(0,n,0,0)$, y queremos demostrar que si el estado del juego es de $(g,0,G,S)$, entonces $G=S$.

Si estamos en $(g_i,s_i,G_i,S_i)$ y agregar una moneda de oro, el estado de cambios en $$(g_{i+1},s_{i+1},G_{i+1},S_{i+1}) = (g_i+1,s_i,G_i,S_i+s_i),$$ y si sacamos una moneda de plata, el estado de cambios en $$(g_{i+1},s_{i+1},G_{i+1},S_{i+1}) = (g_i,s_i-1,G_i+g_i,S_i).$$

Un plan para resolver el problema es encontrar un invariante, por ejemplo, una función de $(g,s,G,S)$ a enteros, de tal manera que estas transformaciones no se cambia el valor de dicha función. Mirando las ecuaciones para un tiempo sugiere algo con $gs$, por que cómo íbamos a conseguir cambios de tamaño de $g$ y $s$. Un poco más nos da $$f(g,s,G,S) = gs+G-S.$$ Una vez que hemos encontrado la fórmula anterior, es fácil comprobar que un paso no afecta el valor de $gs+G-S$.

Por lo tanto, si partimos de $f(0,n,0,0)=0$ y al final con $f(g,0,G,S) = G-S$, podemos ver que $G=S$.

Answer 2

Cuando se agrega una moneda de oro, escribe $$ n para el número de monedas de plata de la izquierda.

Cada vez que se quite uno de esos $n$ monedas de plata, que la moneda de oro son contados una vez como parte de la cantidad de monedas de oro - de un total de $n$ veces, ya que todas las monedas de plata son finalmente eliminados.

Answer 3

Dicen que usted comienza con $n$ monedas de plata. Como siempre que quitar sólo las monedas de plata, que no deje de escribir $0$s. Estos movimientos no afectan a la suma en papel, por lo que también podría ignorarlos y asumir que el primer paso es agregar una moneda de oro, escrito $n$ en el segundo documento. Cada vez que se quita una moneda de plata antes de agregar otra moneda de oro, voy a escribir otro $1$ en el segundo documento, por lo que si se quita de $s_1$ monedas, podrás agregar $s_1$ a el total en el primer papel.

A continuación, puede agregar una segunda moneda de oro, que agrega $n-s_1 de dólares para el total de la segunda papel. Digamos que, a continuación, retire$s_2$monedas de plata (donde$s_2$podría$0$); que agrega$2s_2$a el total en el primer papel y te deja con$n-(s_1+s_2)$ monedas de plata.

Cuando, a continuación, añadir una tercera moneda de oro, escribe $n-(s_1+s_2)$ en el segundo trabajo, y si a continuación, quita la otra $s_3$ monedas de plata, que van a escribir $3$ en el primer papel $s_3$ veces.

En general, cuando hayas añadido el $k$-th moneda de oro, que van a escribir $n-\sum_{i=1}^{k-1}s_i de dólares en el segundo trabajo, y cuando, a continuación, quitar otros$s_k$monedas de plata, que van a escribir$k$en el primer papel$s_k$veces. En este punto el total de la primera ponencia será de$$\sum_{i=1}^kis_i\;,$$ y el total en el segundo documento que será

$$\sum_{j=0}^{k-1}\left(n-\sum_{i=1}^js_i\right)=kn-\sum_{j=1}^{k-1}\sum_{i=1}^js_i=kn-\sum_{i=1}^{k-1}\sum_{j=i}^{k-1}s_i=kn-\sum_{i=1}^{k-1}(k-i)s_i\;.$$

(Tenga en cuenta que $\sum_{i=1}^0s_i=0$.)

Supongamos que al final hay $m$ monedas de oro. Escribir las expresiones para los totales de los dos papeles en términos de $m$ y $n$; las expresiones implicará sumatorias. A continuación, mostrar que las expresiones son iguales; es bastante simple manipulación algebraica en ese punto. Si usted recibe completamente atascado, pase el ratón sobre el spoiler bloque protegido a continuación.

Si hay $m$ monedas de oro al final, el total de la primera ponencia será de $$\sum_{i=1}^mis_i\;,$$ y el total en el segundo será de $$mn-\sum_{i=1}^{m-1}(m-i)s_i=mn-\sum_{i=1}^m(m-i)s_i\;.$$ Usted necesita darse cuenta de que $\sum_{i=1}^ms_i$ puede ser simplificado enormemente.

Answer 4

Deje que el número de monedas de oro y monedas de plata x y y. Imaginar el xy-rejilla y deja que nuestro estado inicial y final del estado de ser representado por (0, y) y (x, 0) respectivamente.

Con cada paso, (x, y) se convierte en (x+1, y) o (x, y-1), que corresponde al de una moneda de oro es añadido o una moneda de plata se retira. Considere la ruta trazada por el punto en movimiento desde (0, y) a (x, 0), y también hay que considerar el área limitada por la curva, el eje x positivo, y el eje y positivo.

El área se mencionó anteriormente puede evaluarse de dos maneras, ya sea como suma de áreas de rectángulos con ancho de 1 y de mayor altura, o la suma de áreas de rectángulos con altura de 1 y más grande posible de ancho. Cada pedazo de papel de las listas de las áreas de los rectángulos individuales, y puesto que el área total es el mismo, la suma en cada papel es el mismo y ambos son iguales al valor de la zona, en la ruta trazada.

Answer 5

Vamos a empezar con solo una moneda de plata. Ahora podemos agregar $k$ monedas de oro, hasta que nos quite nuestra $1$ moneda de plata y el juego termina.
Para cada una de las monedas de oro, escribimos $1$ en nuestro pedazo de papel, por lo que es un total de $k$ 1. Cuando finalmente se retira la moneda de plata, escribimos $k$ en el otro pedazo de papel, una vez. Es fácil ver que ambas sumas son de $k$.

Vamos a pasar a $2$ en monedas de plata. Añadimos ahora $m$ monedas de oro, luego quitamos la primera moneda de plata, luego añadimos otro $k$ monedas de oro y quitar la segunda moneda de plata.
En un pedazo de papel tenemos $m$ 2 y $k$ 1, en la otra tenemos $m$ (a partir de cuando se quita la primera moneda de plata) y $m + k$ (a partir de cuando se quita la segunda moneda de plata). Como tanto la suma de $2m + k$, de nuevo, las sumas son iguales.

Si definimos $g_s$ como el número de monedas de oro agregado entre la eliminación de monedas de plata de $s$ y $s-1$, podemos ver que la $s$ cotiza a $g_s$ veces, mientras que $g_s$ ocurre $s$ veces como un sumando de un número en la lista de otros, para todos los $g, s \in \mathbb Z_{\ge 0}$