Probabilidades de armar un rompecabezas "perfectamente"

Question

Probabilidades de armar un rompecabezas "perfectamente"

Matemáticas
probabilidad
combinatoria
matemáticas-recreativas

estuardo

Muchos de mis compañeros de trabajo se han acostumbrado a armar rompecabezas durante la jornada laboral, así que se me ocurrió la idea de que sería divertido aburrirlos con datos aleatorios. Estoy tratando de pensar en las probabilidades de armar un rompecabezas de 1000 piezas "perfectamente", es decir, elegir cada pieza de manera que encaje con una de las piezas que ya están en el rompecabezas.

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

A partir de aquí, estoy seguro de que la respuesta tiene algo que ver con esto: Probabilidad de rompecabezas 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 entender cómo extrapolar esto más, ya que la próxima iteración parece depender del tipo de pieza que se elija. No estoy seguro de si este es el enfoque correcto, porque puedo imaginar un escenario en el que el rompecabezas se ensambla desde el centro hacia afuera, después de lo cual se garantiza que cada pieza del borde encajará con probabilidad 1, y no estoy seguro de cómo lo anterior La secuencia podría expandirse de una manera que explique eso.

El otro enfoque en el que pensé se inspiró en esto: Prueba por inducción: Problema de piezas de rompecabezas

Si pudiera derivar el número de posibles secuencias "perfectas" de 999 movimientos, ¡podría dividir ese número por 1000! total de posibles secuencias de selecciones y esa sería la probabilidad. Sin embargo, es posible que me esté perdiendo algo aquí, ya que esta línea de pensamiento contrasta con esta publicación: Probabilidad de que un rompecabezas de n piezas se resuelva en el primer intento. ¿Es sólido mi razonamiento? ... lo que supone que solo hay una forma posible de seleccionar todas las piezas que lo resuelva. También se mete en la orientación de las piezas, lo que realmente no me importa.

¡Cualquier pensamiento es bienvenido!

Clayton

¡Esto suena como una gran pregunta! +

1

$1$

Antkam

esta pregunta es mucho más interesante que las 3 preguntas citadas. :) está viendo la cantidad de formas de "hacer crecer" la cuadrícula comenzando con cualquier celda y agregando una celda adyacente a la vez. si considera la cuadrícula como un gráfico, esto me recuerda la búsqueda primero en profundidad, la búsqueda primero en el pan, Dijkstra, etc. en la forma en que agrega un nodo adyacente a la vez. pero no conozco ningún resultado sobre la cantidad de formas distintas de visitar cada nodo.

estuardo

¡Pensar en ello como un gráfico es un enfoque realmente interesante! Un enfoque como ese podría generar más fácilmente la cantidad de recorridos "perfectos" que visitan cada nodo exactamente una vez ... Pensaré en esto por un momento y actualizaré la pregunta si se me ocurre algo útil.

Antkam

aparentemente hay algunas matemáticas llamadas "teoría de la filtración" relacionadas con esto, modelando, por ejemplo, la propagación de infecciones en un gráfico incl. en una rejilla pero el entorno suele suponer una infección paralela, no secuencial. y no parecen estar haciendo una pregunta de enumeración como la suya.

Respuestas (1)

Probabilidades de armar un rompecabezas "perfectamente"

esta pregunta es mucho más interesante que las 3 preguntas citadas. :) está viendo la cantidad de formas de "hacer crecer" la cuadrícula comenzando con cualquier celda y agregando una celda adyacente a la vez. si considera la cuadrícula como un gráfico, esto me recuerda la búsqueda primero en profundidad, la búsqueda primero en el pan, Dijkstra, etc. en la forma en que agrega un nodo adyacente a la vez. pero no conozco ningún resultado sobre la cantidad de formas distintas de visitar cada nodo.
¡Pensar en ello como un gráfico es un enfoque realmente interesante! Un enfoque como ese podría generar más fácilmente la cantidad de recorridos "perfectos" que visitan cada nodo exactamente una vez ... Pensaré en esto por un momento y actualizaré la pregunta si se me ocurre algo útil.
aparentemente hay algunas matemáticas llamadas "teoría de la filtración" relacionadas con esto, modelando, por ejemplo, la propagación de infecciones en un gráfico incl. en una rejilla pero el entorno suele suponer una infección paralela, no secuencial. y no parecen estar haciendo una pregunta de enumeración como la suya.

Ertxiem - reincorporar a Mónica · Answer 1

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

Si el crecimiento del rompecabezas 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$ , entonces, $b \propto \sqrt{p}$ . Y el tamaño del límite sería proporcional al número de lugares posibles para las piezas. Esto debería ser más o menos cierto siempre que queden muchas piezas por colocar.

Cerca del final, casi todas las piezas sobrantes deberían tener un lugar, debido a pequeños agujeros o debido a efectos de borde o percolación. Entonces, la probabilidad $Prob$ para un gran rompecabezas con $N$ las piezas deben depender mayormente de las primeras $n < N$ piezas.

PAG r o b \propto \prod_{pag = 1}^{norte} \frac{\sqrt{pag}}{norte - pag} .

$Prob \propto \ \prod_{p=1}^{n} \frac{\sqrt{p}}{N-p} .$

si asumimos (basado en nada específico) que $n = N/2$ y aproximar el producto a su término medio $p = n/2 = N/4$ , obtenemos

PAG r o b \propto \prod_{pag = 1}^{norte / 2} \frac{\sqrt{norte / 4}}{norte - norte / 4} = {(\frac{\sqrt{norte} / 2}{3 norte / 4})}^{norte / 2} = {(\frac{2 \sqrt{norte}}{3 norte})}^{norte / 2} = {(\frac{2}{3} \frac{1}{\sqrt{norte}})}^{norte / 2},

$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} ,$

PAG r o b \propto {(\frac{2}{3})}^{norte / 2} {norte}^{- norte / 4} .

$Prob \propto \left( \frac{2}{3} \right) ^{N/2} N^{-N/4} .$

No tengo idea de qué tan cerca puede estar esto de la realidad, pero ciertamente decae rápidamente con N.

Probabilidades de armar un rompecabezas "perfectamente"

estuardo

Clayton

Antkam

estuardo

Antkam

Respuestas (1)

Ertxiem - reincorporar a Mónica

Número mínimo de 'movimientos' requeridos para reordenar una lista de números

6 caras seguidas de 6 cruces (lanzamiento de monedas)

En una familia de 101010 miembros, ¿cuál es la probabilidad de que los cumpleaños de los miembros incluyan los siete días de la semana?

¿Cuál es la probabilidad de que una caminata aleatoria que comienza en 0 llegue a +2 en 2 pasos, 3 pasos, 4 pasos, etc.? [duplicar]

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos

¿Por qué surge esta relación de recurrencia en la que nnn elige kkk? [duplicar]

Sacar calcetines al azar de una bolsa

Una pregunta sobre un caso especial del principio de inclusión-exclusión

Contar el número de formas en que las parejas casadas pueden sentarse uno al lado del otro

Combinatoria eligiendo miembros para una clase.