Teoría de juego de mármol

Question

En un juego, existen tres pilas de canicas, cada pila con ,un,b, y c canicas, respectivamente, donde a,b,c son números naturales y todos diferentes. En cada turno, puedes duplicar el número de canicas en una pila por el transporte de los mármoles de otro de mayor tamaño de la pila (en relación a la pila que va a ser doblado, antes de la duplicación). El juego se gana cuando cualquiera de los dos pilas tienen el mismo número de canicas.

Mostrar que el juego se puede ganar de cualquier partida,a, b,c, o demostrar que este no es el caso. (En particular, demostrar que el juego no se puede ganar de cada partida a,b,c.)

Interesante, pero la solución venga no.

Ernst

Answer 1

Si usted comienza con 0,1,2 no funciona.

Estrictamente números positivos este es esencialmente el problema de C3 de la OMI lista de 1994 donde queremos vaciar una cuenta en la misma situación. (Porque usted tiene que tener dos cantidades iguales antes de que una cantidad puede llegar a cero.)

Hay varios sitios web que ofrecen una preselección de soluciones, por ejemplo:

http://mks.mff.cuni.cz/kalva/short/soln/sh94c3.html

No sé si se supone que debo copiar una solución aquí.

Answer 2

Un duplicado de esta pregunta, Vaciar baldes moviendo piedritas alrededor, se le preguntó (y, curiosamente, recibió mucho más upvotes de esta). Antes de que Brian señaló que se trata de un duplicado, se me ocurrió una solución diferente de la lista de preseleccionados de la solución. (I tratar el problema de vaciado de uno de los montones, que, como se discutió en la Phira la respuesta y los comentarios, es equivalente.)

La idea es sucesivamente producir $0$s en las representaciones binarias de dos de los números, empezando por el bit menos significativo. Así que asumir que la última $k$ bits de $b$ $c$ ya son cero; entonces, si ni $b$ ni $c$ es cero, sin embargo, nuestro objetivo es hacer que la última $k+1$ bits de dos de los números de cero.

Así que considere la $(k+1)$-th bits de $b$$c$. Si los dos están de $0$, hemos terminado. Si los dos están de $1$, sólo necesitamos una transferencia entre el $b$ $c$ a hacerlos $0$. Si uno es $0$ y una es $1$, se puede poner el $1$ en el menor de los dos por la transferencia, desde el mayor hasta el menor, hasta que se convierte en la menor.

Sin pérdida de generalidad, supongamos $b\lt c$. Ahora hay dos casos. Si $a\ge b$, podemos deshacernos de la $1$ por una transferencia de$a$$b$. De lo contrario, $a\lt b\lt c$, y la transferencia de primero de $b$ $a$y, a continuación, de$c$$b$, lo que va de$a,b,c$$2a,b-a,c$%#%. Ahora la suma de los dos primeros números es $2a,2(b-a),c+a-b$, lo que ha $2b$s en los últimos $0$ bits, así que podemos hacer la última $k+1$ bits de los dos números de $k+1$ por realizar transferencias entre ellos, cada uno de los cuales se deshace de sus últimos $0$ bits.

Si inicialmente asignamos $1$, $a$ y $b$ tal que $c$ tiene el menor número final de ceros, esta estrategia parece ser ligeramente más eficaz que la lista de preseleccionados de la estrategia: en Comparación con el total de $a$ transferencias mínimo requerido para resolver todas las instancias distintas con los totales de menos de $103505$, esta estrategia hace que $100$ transferencias, mientras que la lista de preseleccionados, la estrategia hace $172865$.