Pierna fantasma

Cubriendo el centro de las líneas, un jugador elige un punto de inicio (A). A continuación, se revelan las líneas y se traza el punto de inicio elegido hasta su extremo (3).

El sorteo de la pierna fantasma es un método de lotería diseñado para crear emparejamientos aleatorios entre dos conjuntos de cualquier cantidad de elementos, siempre que la cantidad de elementos en cada conjunto sea la misma. Se suele utilizar para distribuir cosas entre personas, donde la cantidad de elementos distribuidos es igual a la cantidad de personas. Por ejemplo, las tareas o los premios podrían asignarse de forma justa y aleatoria de esta manera.

Se conoce en japonés como Amidakuji (阿弥陀籤; " lotería Amida ") , ^{[ nb 1 ]} en coreano como Sadaritagi (사다리타기, literalmente "escalada de escalera") y en chino como Guijiaotu ( chino :鬼腳圖, literalmente "diagrama de pierna fantasma").

El diagrama consta de líneas verticales con líneas horizontales que conectan dos líneas verticales adyacentes, dispersas aleatoriamente a lo largo de su longitud; las líneas horizontales se denominan "piernas". El número de líneas verticales es igual al número de jugadores, y en la parte inferior de cada línea hay un elemento: un objeto que se asignará a un jugador. La regla general para jugar es: elegir una línea en la parte superior y seguirla hacia abajo. Al encontrar una línea horizontal, seguirla hasta llegar a otra línea vertical y continuar hacia abajo. Repetir este procedimiento hasta llegar al final de la línea vertical. Entonces, el jugador recibe el objeto escrito en la parte inferior de la línea.

Si los elementos escritos encima de la pata fantasma se consideran una secuencia , y después de usar la pata fantasma se escriben los mismos elementos en la parte inferior, entonces la secuencia inicial se ha transformado en otra permutación . Por lo tanto, la pata fantasma puede considerarse un tipo de operador de permutación.

Proceso

Como ejemplo, consideremos la asignación de papeles a los actores en una obra de teatro.

Para empezar, los dos conjuntos se enumeran horizontalmente en un tablero. Los nombres de los actores se colocan arriba y los papeles abajo. Luego, se trazan líneas verticales que conectan a cada actor con el papel que se encuentra justo debajo.
Los nombres de los actores o los papeles se ocultan para que la gente no sepa qué actor está en qué línea, o qué papel está en qué línea.
A continuación, cada jugador añade una pierna al tablero. Cada pierna debe conectar dos líneas verticales adyacentes y no debe tocar ninguna otra línea horizontal.
Una vez hecho esto, se traza un camino desde la parte superior de cada línea vertical hasta la inferior. Al seguir la línea hacia abajo, si se encuentra un segmento a la izquierda o a la derecha, se debe seguir dicho segmento hasta la línea vertical adyacente a la que se conecta, y luego se continúa trazando hacia abajo hasta llegar a la parte inferior de una línea vertical. El elemento superior desde el que comenzó el camino ahora se empareja con el elemento inferior donde terminó.

Otro proceso consiste en crear la escalera de antemano y luego ocultarla. Después, las personas se turnan para elegir un camino desde la parte superior. Si no se oculta ninguna parte del amidakuji, es posible manipular el sistema para garantizar un emparejamiento específico, frustrando así la idea del azar.

Matemáticas

Parte del atractivo de este juego reside en que, a diferencia de juegos de azar como piedra, papel o tijera , el amidakuji siempre crea una correspondencia 1:1 y admite un número arbitrario de parejas. Se garantiza que dos elementos en la parte superior nunca tendrán el mismo elemento correspondiente en la parte inferior, ni que ningún elemento en la parte inferior carezca jamás de un elemento correspondiente en la parte superior.

Funciona independientemente de cuántas líneas horizontales se añadan. Cada persona podría añadir una, dos, tres o cualquier número de líneas, y la correspondencia 1:1 se mantendría.

Una forma de entender cómo funciona esto es considerar la analogía de las monedas en vasos. Hay n monedas en n vasos, que representan los objetos en el fondo del amidakuji . Cada pata que se añade representa el intercambio de la posición de dos vasos adyacentes. Por lo tanto, al final seguirá habiendo n vasos, y cada vaso contendrá una moneda, independientemente de cuántos intercambios se realicen.

Propiedades

Permutación

Una pierna fantasma transforma una secuencia de entrada en una secuencia de salida con el mismo número de elementos con un orden (posiblemente) diferente. Por lo tanto, puede considerarse una permutación de n símbolos, donde n es el número de líneas verticales en la pierna fantasma, ^{[ 2 ]} por lo que puede representarse mediante la matriz de permutación correspondiente .

Periodicidad

Al aplicar una secuencia de entrada un número finito de veces mediante una operación de repetición, se genera finalmente una secuencia de salida idéntica a la secuencia de entrada original.

Es decir, si M es una matriz que representa una pierna fantasma en particular, entonces M ⁿ = I para algún n finito .

Reversibilidad

Para cualquier pierna fantasma con representación matricial M , existe una pierna fantasma con representación M ⁻¹ , tal que M M ⁻¹ = I

Propiedad par-impar de las permutaciones

A medida que cada pata intercambia los dos elementos vecinos en sus extremos, el número de patas indica la propiedad de permutación par/impar de la pata fantasma. Un número impar de patas representa una permutación impar, y un número par de patas da lugar a una permutación par.

Piernas fantasma infinitas con la misma permutación

Es posible expresar cada permutación como una pata fantasma, pero la expresión no es biyectiva; es decir, una permutación particular no corresponde a una única pata fantasma. Un número infinito de patas fantasma representa la misma permutación.

Principal

Dado que existen infinitas formas de representar una permutación determinada, estas formas de representar una permutación tiene una equivalencia. Entre estas formas equivalentes, las que tienen el menor número de formas se denominan "primas".

Ordenación de burbuja y máxima simplicidad

Se puede construir una secuencia fantasma de forma arbitraria, pero dicha secuencia no necesariamente es prima. Se puede demostrar que solo las secuencias fantasma construidas mediante el algoritmo de ordenación de burbuja contienen el menor número de segmentos y, por lo tanto, son primas. Esto equivale a decir que el algoritmo de ordenación de burbuja realiza el mínimo número de intercambios adyacentes para ordenar una secuencia.

Número máximo de patas de un número primo

Para una permutación con n elementos, el número máximo de intercambios de vecinos es = ${\frac {n(n-1)}{2}}$

De la misma manera, el número máximo de piernas en un primo con n pistas = ${\frac {n(n-1)}{2}}$

Burbujeo

Para una pierna fantasma arbitraria, es posible transformarla en prima mediante un procedimiento llamado "burbujeo". Cuando se aplica el burbujeo, se aplican repetidamente las siguientes dos identidades para mover y eliminar las piernas "inútiles".

⇒
⇒

Cuando las dos identidades ya no se pueden aplicar, se demuestra que la pierna fantasma es exactamente la misma que la pierna fantasma construida por el algoritmo de ordenación de burbuja , por lo que la burbujización puede reducir las piernas fantasma a números primos.

Aleatoriedad

Dado que, como se mencionó anteriormente, un número impar de patas produce una permutación impar y un número par de patas produce una permutación par, un número dado de patas puede producir un máximo de la mitad del total de permutaciones posibles (menos de la mitad si el número de patas es pequeño en relación con el número de pistas, llegando a la mitad a medida que el número de patas aumenta más allá de un cierto número crítico).

Si las patas se extraen al azar (según definiciones razonables de "extraer al azar"), la uniformidad de la distribución de permutaciones aumenta con el número de patas. Si el número de patas es pequeño en relación con el número de pistas, las probabilidades de las diferentes permutaciones alcanzables pueden variar considerablemente; para un gran número de patas, las probabilidades de las diferentes permutaciones alcanzables tienden a la igualdad.

Notas

↑ Llamado así porque en el período Muromachi, las representaciones impresas del sistema se dibujaban radialmente (con puntos de inicio en el exterior y puntos finales en el interior), asemejándose así al diseño de "círculo que emite rayos" utilizado popularmente para representar el halo de Amida^{[ 1 ].}

Referencias

↑ Frédéric, Louis (2002). Enciclopedia de Japón . ISBN 9780674017535.
↑ Ho 2012, pág. 31

Enlaces externos

https://web.archive.org/web/20091023070628/http://geocities.com/Athens/Acropolis/7247/amidakuji.html
Escaleras: Un artículo de investigación de David Senft (PDF)
Man-Kit Ho, Hoi-Kwan Lau, Ting-Fai Man, Shek Yeung (2012). «Ghost Leg», Colección de trabajos ganadores de los Premios de Matemáticas Hang Lung, 2004. International Press. ISBN 978-1-57146-254-1.

[2] Llamado así porque en el período Muromachi, las representaciones impresas del sistema se dibujaban radialmente (con puntos de inicio en el exterior y puntos finales en el interior), asemejándose así al diseño de "círculo que emite rayos" utilizado popularmente para representar el halo de Amida^{[ 1 ].}

[1] Frédéric, Louis (2002). Enciclopedia de Japón . ISBN 9780674017535.

[3] Ho 2012, pág. 31

[ nb 1 ]

[ 2 ]

[ 1 ].