Si las personas en una habitación tuvieran una posición aleatoria de cubo de Rubik, ¿cuántas personas necesitaríamos para que haya un 50% de posibilidades de al menos dos cubos idénticos?

Answer 1

Según esta fuente, hay alrededor de 43 quintillones de posiciones de cubo de Rubik únicas.

Sea p = 1 / [ese número] la probabilidad de una posición particular. Trabajemos en términos de p, para que podamos ser más generales.

Supongamos que tenemos n personas en la sala. Fijar la posición del cubo de la primera persona. La probabilidad de que la siguiente persona tenga una posición de cubo diferente es solo:

[matemáticas] 1 – p [/ matemáticas]

Ahora, toma la tercera persona. Dado que hay dos posiciones de cubo distintas de las que esta persona debe ser diferente, la probabilidad de que esta persona sea diferente de ambas es:

[matemáticas] 1 – 2p [/ matemáticas]

En términos más generales, considere la persona [matemáticas] i ^ {th} [/ matemáticas]; Dado que todas las personas anteriores tienen diferentes posiciones de cubo, la probabilidad de que esta persona sea diferente será:

[matemáticas] 1 – (i-1) p [/ matemáticas]

(Suponiendo n> 1 / p; de lo contrario, la probabilidad es cero, porque tenemos más personas que distintas posiciones de cubo.) Entonces, la probabilidad de que n personas tengan diferentes posiciones de cubo es:

[matemáticas] \ prod_ {i = 1} ^ n 1 – (i – 1) p [/ matemáticas]

que no se simplifica fácilmente, aunque se puede escribir en términos de algunas otras funciones. Queremos saber para una p dada, cuál es el mínimo n tal que:

[matemática] \ prod_ {i = 1} ^ n 1 – (i – 1) p \ leq 0.5 [/ matemática]

(donde 0.5 se puede reemplazar con alguna otra probabilidad objetivo).

No pude encontrar una buena solución de forma cerrada para esto, pero debería ser posible escribir código para hacer una búsqueda binaria. Quería darle un gráfico de esta función en términos de n, pero para valores realmente grandes de n, me encuentro con problemas de memoria. Para valores de n que realmente puedo calcular (en miles), el valor de la función está dentro de un error de redondeo de 1. En otras palabras, es seguro que todos los cubos serán diferentes.

(No digo que esta función sea imposible de calcular para valores grandes de n; solo que requiere algunas técnicas inteligentes de programación dinámica que no valen la pena invertir tiempo).

Tenga en cuenta que para todo n,

[matemáticas] \ prod_ {i = 1} ^ n 1 – (i – 1) p> (1 – (n – 1) p) ^ n> (1 – np) ^ n [/ matemáticas]

En otras palabras, [math] (1 – (n – 1) p) ^ n [/ math], que es una expresión mucho más fácil de trabajar, proporciona un límite inferior para la probabilidad de que cada cubo sea diferente. Este límite inferior alcanza 0.5, aproximadamente [matemática] 5.5 \ veces 10 ^ 9 [/ matemática]. En comparación, hay aproximadamente [matemáticas] 7.4 \ veces 10 ^ 9 [/ matemáticas] humanos vivos en la tierra. Dado lo conservador que es este límite inferior, creo que es seguro decir que incluso si le dio a todos en la Tierra un cubo de Rubik dispuesto al azar, la probabilidad de que todos tengan un arreglo diferente es muy cercana a uno.

Answer 2

Primero intenté decir el número grande, 43252003274489856000. Como era difícil, puedo decir con razón que es realmente grande, por lo que las fórmulas asintóticas deberían ser lo suficientemente buenas. En uno de los viejos Cruxes (solía amar Crux como estudiante de secundaria) [1] podemos encontrar una fórmula asintótica para el problema del cumpleaños, válida para una gran cantidad de “días en un año”, es decir, [matemáticas] n \ a \ infty [/ math].

Entonces, aquí va: [matemáticas] k = \ sqrt {2n \ ln \ frac {1} {1-p}} [/ matemáticas] lo que significa que entre las personas [matemáticas] k [/ matemáticas], dos tendrán el mismo cumpleaños en un año de [matemáticas] n [/ matemáticas] días largos con probabilidad [matemáticas] p [/ matemáticas]. Tomemos [matemáticas] p = 0.5 [/ matemáticas] y [matemáticas] n = 43252003274489856000 [/ matemáticas]. Calcular directamente produce [matemáticas] k \ aprox7.74 \ veces 10 ^ 7 [/ matemáticas]. Ahora, dado que hay 7.500 millones de nosotros en este momento, [2] esto no está muy lejos (si fuéramos quisquillosos, la probabilidad no sería del 50% para la humanidad actual, sino de un 48%).

Notas al pie

[1] https://cms.math.ca/crux/v26/n3/ …

[2] Reloj mundial de la población: 7,5 mil millones de personas (2016)

Answer 3

Podrías usar la aproximación de Stirling: Wikipedia para evitar el cálculo de factoriales masivos y probablemente obtener una respuesta muy precisa.

Además, Ataque de cumpleaños: Wikipedia tiene tablas y cálculos apropiados.

Answer 4

Sin embargo, esta no es la respuesta que está buscando, debido a la naturaleza humana, si hubiera 100 personas, supongo que hay un 100% de posibilidades de 2 patrones idénticos, porque al menos 2 de las personas intentarían acelerar -solucione antes de descubrir lo que se supone que están haciendo, por lo que al menos 2 de estos cubos se RESOLVERÁN (por lo tanto, patrones idénticos) en 5 minutos (algunas personas simplemente no entienden el significado de “resolución rápida”) .