Las probabilidades de armar un rompecabezas "perfectamente"

Question

Un grupo de mis compañeros de trabajo se ha dedicado a armar rompecabezas durante la jornada laboral, así que se me ocurrió que sería divertido aburrirlos con hechos al azar. Intento pensar en las posibilidades de montar un puzzle de 1000 piezas "a la perfección", es decir, elegir cada pieza de tal manera que encaje con una de las que ya están en el puzzle.

Asumiendo que cada pieza es exactamente de 1 pulgada cuadrada, eso significa que probablemente tenemos un rompecabezas de 40x25 pulgadas. Usando alguna deducción básica, puedo concluir que esto deja 4 piezas de "esquina" con dos posibles conexiones, 122 piezas de "borde" con tres posibles conexiones, y 874 piezas internas con cuatro posibles conexiones.

Desde aquí, estoy seguro de que la respuesta tiene algo que ver con esto: Probabilidad de Jigsaw Usando esa lógica, la probabilidad de que nuestras dos primeras piezas coincidan es:

(4/1000) * (2/999) + (122/1000)*(3/999) + (874/1000) * (4/999)

El problema es que no puedo averiguar cómo extrapolar esto más allá, ya que la siguiente iteración parece que dependería del tipo de pieza elegida. No estoy seguro de que este sea el enfoque correcto, porque puedo imaginar un escenario donde el rompecabezas se ensambla desde el centro hacia afuera, después del cual cada pieza del borde se garantiza que encaje con la probabilidad 1, y no estoy seguro de cómo la secuencia anterior podría ser expandida de una manera que dé cuenta de eso.

El otro enfoque que pensé fue inspirado por esto: Prueba por inducción: Piezas del rompecabezas Problema

Si pudiera derivar el número de posibles secuencias "perfectas" de 999 movimientos, podría dividir ese número por 1000! secuencias totales posibles de selecciones y esa sería la probabilidad. Sin embargo, puede que me esté perdiendo algo aquí, ya que esta línea de pensamiento está en contraste con este post: Probabilidad de que un rompecabezas de n piezas se resuelva en el primer intento. ¿Mi razonamiento es correcto? ...lo que hace suponer que sólo hay una forma posible de seleccionar todas las piezas que lo resuelven. También se mete en la orientación de las piezas, lo cual no me importa.

¡Cualquier pensamiento es bienvenido!

Answer 1

No he podido responder a esta pregunta, pero me gustaría compartir algunas ideas:

Si el crecimiento del puzzle es razonablemente compacto, el tamaño del límite $b$ debe ser aproximadamente proporcional a la raíz cuadrada del número de piezas ya colocadas $p$ Así que.., $b \propto \sqrt{p}$ . Y el tamaño de la frontera sería proporcional al número de lugares posibles para las piezas. Esto debería ser aproximadamente cierto mientras queden muchas piezas por colocar.

Cerca del final, casi todas las piezas sobrantes deberían tener un lugar, debido a los pequeños agujeros o a los efectos de borde o percolación. Por tanto, la probabilidad $Prob$ para un gran rompecabezas con $N$ piezas debería depender sobre todo de la primera $n < N$ piezas. $$ Prob \propto \ \prod_{p=1}^{n} \frac{\sqrt{p}}{N-p} . $$

si suponemos (sin basarnos en nada concreto) que $n = N/2$ y aproximar el producto a su término medio $p = n/2 = N/4$ obtenemos $$ Prob \propto \prod_{p=1}^{N/2} \frac{\sqrt{N/4}}{N-N/4} = \left( \frac{\sqrt{N}/2}{3N/4} \right) ^{N/2} = \left( \frac{2\sqrt{N}}{3N} \right) ^{N/2} = \left( \frac{2}{3} \frac{1}{\sqrt{N}} \right) ^{N/2} , $$ $$ Prob \propto \left( \frac{2}{3} \right) ^{N/2} N^{-N/4} . $$

No tengo ni idea de lo cerca que puede estar esto de la realidad, pero ciertamente decae rápidamente con N.