Combinatoria Tarjeta Flip Juego

Question

Recientemente, me han dado un interesante tipo de problema que estoy teniendo un tiempo difícil demostrar. El problema gira en torno a un juego, con reglas como la siguiente:

"Usted tiene una cubierta que contiene n cartas en orden aleatorio. La parte superior de la tarjeta tiene algún número k en ella. En la parte superior k las cartas de la parte superior de la cubierta, la inversa de su orden, y poner de nuevo en la parte superior de la cubierta. Un nuevo número, r, es ahora en la parte superior de la cubierta. Tomar r cartas de la parte superior de la cubierta, la inversa de su orden, y poner de nuevo en la parte superior de la cubierta. Repita este proceso hasta que el juego termina (Tarjeta #1 está en la parte superior de la baraja)."

La supuesta resultado del juego es que va a tardar más de F(n+1) - 1 "pasos" para terminar el juego. He probado experimentalmente, y han sido capaces de comprobar el resultado para los distintos valores de n, pero la forma de demostrarlo es otra historia.

Answer 1

Usted puede probar el juego termina por inducción. Un $1$ cartas de la baraja, termina inmediatamente. Supongamos ahora que hemos demostrado que termina por todas las cubiertas de hasta el $n$. Si nos imaginamos jugando a un juego con $n+1$ tarjetas, si la tarjeta de $n+1$ llega a la parte superior de la cubierta, esta va a ser inferior y no pueden entrar en el juego de nuevo. Entonces estamos jugando un $n$ juego de cartas, que sabemos que termina. Si la tarjeta de $n+1$ nunca llega a la parte superior de la cubierta, nunca volveremos a ver la tarjeta en la parte inferior de la cubierta, por lo que podemos pretender que no está ahí, en cuyo caso estamos jugando nuevamente un $n$ juego de cartas. Así que el juego termina siempre.

Añadido: yo creo que un límite superior para el número máximo de vueltas es uno menos que los números de Fibonacci, $F(n)$ con el índice de desplazamiento por $1$. Deje $G(n)$ ser el máximo número de vueltas para $n$ tarjetas. $G(1)=0$ como tarjeta de $1$ es en la parte superior. $G(2)=1$ para el fin de $2,1$. $G(3)=2$ para la orden de $3,1,2$ encontrar la recurrencia, usted no desea $1$ en la parte inferior o te lo enviaremos tan pronto como usted encontrar la tarjeta de $n$. Así que usted está jugando un $n-2$ juego de cartas que termina cuando se encuentra la tarjeta de $n$ y no he encontrado la tarjeta de $1$. Usted juega $1$ vuelta para poner la tarjeta de $n$ en el fondo, luego de jugar un $n-1$ juego de cartas. Por lo que la recurrencia es $G(n)=1+G(n-1)+G(n-2)$ A demostrarlo por inducción, nota: $G(1)=F(2)-1, G(2)=F(3)-1$ y asumir que hemos probado hasta el $n-1$, luego $ G(n)=1+G(n-1)+G(n-2)=1+(F(n)-1)+(F(n-1)-1)=F(n+1)-1$

Sin embargo, esto supone que se puede jugar el $n-1$ tarjeta de juego evitando $1$ durante muchas vueltas como un $n-2$ juego de cartas. Para $4$ tarjetas funciona esto con el fin de $2413$ de los que tomaron $4$ se mueve, y para $5$ también funciona con $31452$ de los que tomaron $7$. Pero para $6$ tarjetas de falla. La manera de encontrar estos es tomar el máximo de la serie para $n-1$, poner la tarjeta de $n$ sobre la parte inferior y trabajar hacia atrás. Para $6$ te quedas atascado y $456213$ sólo toma $10$ turnos. No he probado que no hay $11$ mover cubiertas.

Answer 2

Como Arturo Magidin señaló, mi iniciación en la última respuesta no poseen, por lo que aquí es una prueba de la terminación. Hay un número finito de órdenes de $n$ tarjetas sin $1$ en la parte superior, específicamente $n!-(n-1)!.$ Si el juego no se termina, se debe tener un bucle que viene de nuevo a un visto anteriormente fin. Considere la posibilidad de $m$, la más grande de la tarjeta visto en el curso de jugar a través del bucle. Después de ver esto, pasa a la posición $m$ y ninguna otra tarjeta en el bucle puede recuperar, y nunca volveremos a ver a $m$ nuevo. Por lo tanto, no hay ningún bucle.