En una pila de n cartas distintas en orden {1,2,3,4,...,n} desde arriba, defina la distancia entre 2 tarjetas como el número de tarjetas que las separan. 2 cartas son vecinas si son adyacentes en la pila original, si su índice difiere en 1.
¿Cuántas reordenaciones de cartas (permutaciones) satisfacen lo siguiente?
I) La suma de las distancias entre cualquier tarjeta y su vecina/s (llame a esa suma $S_n$ para la tarjeta $n$ ), es distinta para todos los $n$ tarjetas.
II) $S_n$ es distinta para todos los $n$ y sólo toman valores menores que $n$ .
Edición 1 Un ejemplo aclara las condiciones.
Digamos que tenemos 3 cartas en la pila original en orden 1,2,3 desde arriba. Reordenar las cartas en el orden 2,3,1 desde arriba. Entonces:
La tarjeta 1 está a la distancia 1 de su antigua tarjeta vecina 2. $S_1$ =1
La tarjeta 2 está a la distancia 1 de la tarjeta 1 pero a la distancia 0 de la tarjeta 3. $S_2$ =1+0=1
La tarjeta 3 está a distancia 0 de la tarjeta 2. $S_3$ =0
Por lo tanto, esta reordenación/barajada no satisface las condiciones de la pregunta, ya que tanto $S_1$ y $S_2$ son 1.
Edición 2 : JLee y LaBird amablemente escribieron programas para generar los datos (¡muchas gracias!). Usando los datos hice un gráfico rápido para adivinar las posibles relaciones entre n y la proporción de permutaciones que satisfacen la condición 1 con respecto al número total de permutaciones de longitud n. Este es un enfoque menos que científico, pero en el espíritu de la contribución, espero que esto pueda "desencadenar" formas de resolver el problema.
Breve comentario: Parece que la pendiente del gráfico logarítmico se está estabilizando en torno a -1/2, aunque esto es una mera suposición sin más datos.
Mi intento: Hice una lista de observaciones básicas, tratando de relacionar este problema con métodos conocidos, pero con poco éxito.
i) Dejemos que el orden original de las cartas sea 1,2,3,4 ..,n para simplificar desde la parte superior de la pila. Después de que el orden de las cartas sea aleatorio, la distancia entre las cartas 2 y 3 contribuirá tanto a S2 como a S3, ya que antes eran vecinas.
ii) La cuestión es análoga a una rana que da n-1 saltos en un tablero de 1*n, etiquetado como 1,2,3,4 ..n de izquierda a derecha. Empezando por la casilla que representa la nueva posición de la carta 1, la rana da saltos de manera que en la mª vuelta se encuentra en la casilla que representa la nueva posición de la mª carta. Las restricciones son que cada casilla debe ser cubierta exactamente una vez y la magnitud del primer y último salto, y la suma de las magnitudes de 2 saltos consecutivos cualesquiera deben ser distintos.
iii) Las cartas 1 y n sólo tienen 1 vecino, por lo que después de reordenar, S1 y Sn son las distancias entre la carta 1 y su antiguo vecino y la carta n y su antiguo vecino, respectivamente.
iv) En la parte i) Sn puede tomar cualquier valor de 0 a 2n-5. Si una carta k permanece adyacente a sus vecinas, entonces Sk=0. Si Sn>n-3 para algún n, entonces podemos deducir que las antiguas cartas vecinas están ahora ambas por encima o ambas por debajo de la carta n Sn alcanza un valor máximo de 2n-5 cuando una carta está en la parte inferior del mazo y sus dos antiguas vecinas en la parte superior del mazo. Sólo es necesario utilizar n de esos valores, por lo que n-4 quedará sin utilizar.
v) Para la parte ii), Sn sólo puede tomar valores de 0 a n-1. Por tanto, cada valor debe tomarse una vez. Esto significa que exactamente una carta k debe permanecer junto a todas sus antiguas vecinas en la nueva disposición. Esto se hace para que Sk pueda tomar el valor 0. No estoy seguro de que esta disposición sea posible.
vi) En n=4, hay exactamente 4 valores posibles para Sn : (0,1,2,3). Para cada valor mayor de n, los valores posibles de Sn superan a n.
¿Existen estrategias para analizar/abordar problemas como éste? ¿Puede resolverse este problema para un n pequeño como n=5?
gracias como siempre
