Auto colisiones en una pila de tarjetas

Question

(Copiado textualmente de: Un Proyecto de Euler hilo que hice en diciembre de 2009.)

Digamos que usted tiene tarjetas numeradas del 1 al 5. Desea organizarlos en una pila de tal manera que usted puede mover 1 carta de la parte superior a la parte inferior y la vuelta el próximo tarjeta para revelar un 1. Puso a un lado y mover dos cartas de la parte superior de la pila (uno a la vez) a la parte inferior. La siguiente carta se revela y es un 2, que se deje a un lado. Repita hasta que tenga 1 tarjeta de la izquierda, que será de 5. Para lograr esto, las tarjetas deben ser ordenados como tales: [3, 1, 4, 5, 2] Pero lo que si quiero la orden de 10 tarjetas de esta manera? Bueno...la pre-orden es entonces [9, 1, 8, 5, 2, 4, 7, 6, 3, 10]. Entonces empecé a preguntarme si había casos donde la tarjeta del número de la que era su actual posición en la pila antes de la operación. Qué sorpresa! 7 ([5, 1, 3, 4, 2, 6, 7]) tiene 4! Resulta que 7 es el primer número en la secuencia generada por lo tanto tiene más de 2 auto-colisiones, como yo les llamo. El primero que tiene 5 es de 543, el primero que tiene 6 es 3117, y el primero que tiene 7 es 3226. No he encontrado una para 8 sin embargo, pero no puede ser un 9 antes de los 8 primeros. Si alguien puede encontrar una solución analítica a las siguientes preguntas...me va a ser muy sorprendido... :P

¿Cuál es el primero que tiene 8 auto-colisiones? Lo que cerca de las 9? ¿Qué acerca de 10?

P. S. La secuencia de 5 puede ser generado de este modo (fácilmente generalizada):

xxxxx  
x1xxx  
x1xx2  
31xx2  
314x2  
31452

Answer 1

El primer número 8 colisiones es 57,063. No hay casos de 9 o más colisiones por debajo de 1.000.000 de tarjetas.

En general, basado en algunas aproximaciones (básicamente, suponiendo que el número de colisiones por baraja se distribuye Poisson con una media de 1), yo esperaría que el primer número con $n$ colisiones tener magnitud más o menos comparable a $n!$. Así que me imagino que el primer número con 9 colisiones probablemente está en algún lugar en los seis dígitos de la gama, aunque, por supuesto, puede aparecer antes o después de que por casualidad. (Edit: parece que es de hecho más tarde.)

---

Ps. Si alguien más quiere probar la resolución de problemas como este por fuerza bruta, recomiendo el almacenamiento de la cubierta, en un árbol binario. Esto permite que tanto la extracción de una tarjeta y saltar $k$ tarjetas para hacer en $O(\log n)$ operaciones, donde $n$ es el tamaño de la cubierta, dando un tiempo de reproducción total $O(n \log n)$. Me cabe duda de que es posible hacerlo mucho mejor que eso.