$52$ tarjetas suma recíproca probabilidad

Question

Imagina una baraja de $52$ pero en lugar de tener palos y rangos, sólo tienen rangos enteros secuenciales (únicos) de $1$ a $52$ . También se puede imaginar una baraja estándar de $52$ cartas, pero convierte los rangos y palos en un número entero de $1$ a $52$ para que todas las tarjetas tengan asignados números diferentes.

Así que la pregunta es, ¿cuál es la probabilidad, si eliges al azar exactamente $10$ cartas de esa baraja sin reemplazo, que la suma de los recíprocos de los rangos de las cartas (de $1$ a $52$ ) suma exactamente $1$ ? Por ejemplo, si eliges tarjetas $5,10,15,20,25,30,35,40,45$ y $50$ la suma de los recíprocos sólo sería $0.58579$ ... por lo que es demasiado pequeño.

Como pista, creo que si clasificas las cartas en orden ascendente, la primera carta (la de menor rango) DEBE estar entre un $2$ y $6$ (inclusive) para ser una solución candidata. Esto se debe a que $1/1$ es ya una suma de $1$ por lo que cualquier tarjeta adicional hará que sea una suma demasiado grande. También $7$ como tarjeta más baja no funcionará porque $1/7$ + $1/8$ ... + $1/16$ = $0.93$ ...así que la carta más baja DEBE ser una $2,3,4,5$ o $6$ . Estoy volviendo a ejecutar mi simulación modificada ahora con esa información añadida para podar el espacio de estados que debe comprobar.

También estoy viendo múltiples soluciones por lo que no hay sólo $1$ solución pero la probabilidad es probablemente muy baja, sólo una pequeña fracción de $1$ % yo estimaría.

También hay que tener en cuenta que muchas soluciones están muy cerca de $1$ pero no exactamente $1$ Por lo tanto, la simulación por ordenador de este tipo de problemas es más difícil. Un ejemplo de "solución cercana" es $2,4,13,25,35,41,47,50,51,52$ que se evalúa como $0.99999995750965$ . La suma más cercana que no sea igual a $1$ sucede con $3,4,8,14,17,22,26,29,46,47$ que se evalúa como $1.00000000288991$ . Es decir $8$ ceros después del $1$ .

Una nota interesante... Ese número muy cercano a $1$ se obtiene sumando sólo $10$ condiciones. Esto es impresionante, ya que incluso la suma de potencias negativas de $2$ que converge a $1$ , ( $1/2$ + $1/4$ + $1/8$ ...), se necesita $28$ términos para casi igualar esa cercanía a $1$ y $29$ términos para vencerlo.

Answer 1

Lo más fácil es enumerar todas las posibilidades (pocos segundos de CPU).

Hay 1431 formas de extraer cartas distintas de manera que la suma de sus recíprocos sea 1.

Así que la probabilidad es $$ 1431 / {52\choose 10} \approx 9.0455\cdot 10^{-8} $$

Entre esos 1431, el primero y el último lexicográficamente son $$ \{2, 4, 16, 26, 30, 36, 39, 45, 48, 52\} $$ y $$ \{5, 6, 8, 9, 10, 12, 15, 18, 20, 24\} $$

Mi algoritmo es muy ingenuo. El tiempo de ejecución del programa resultante es inferior a 2 segundos.

Cualquier conjunto bueno (suma de recíprocos igual a $1$ ), puede dividirse en dos subconjuntos de $5$ elementos, uno con suma $s\le\frac{1}{2}$ y la otro con la suma $\frac{1}{2}\le s<1$ .

Sólo hay ${52\choose 5}=2598960$ quintetos, por lo que generarlos no es un problema. En particular, almacené el $422730$ cuya suma está entre $\frac{1}{2}$ y $1$ .

Luego vuelvo a generar los quintetos, buscando aquellos con suma $s\le\frac{1}{2}$ y comprobé si entre los almacenados había alguno con suma $1-s$ y con un conjunto de números no superpuestos.

He guardado en el archivo los quintetos correspondientes ( $180959$ ) y luego utilicé otro software para eliminar los duplicados (los duplicados se generaron porque había muchos casos de $\frac{1}{2}+\frac{1}{2}$ y me daba pereza implementar un filtro dentro del programa, ya que podía eliminar los duplicados después con un par de instrucciones de Mathematica.

En cuanto a la implementación, he utilizado C++. No soy un programador de C++, soy demasiado viejo para esa OOP, y normalmente uso C, pero la STL contiene tantas estructuras de datos ya implementadas...)

Así que utilicé un multimapa (un mapa que puede contener múltiples elementos con la misma clave y que puede ser buscado eficientemente por una clave específica), donde la clave era una representación de la suma de 5 recíprocos y los datos asociados eran una representación de las 5 cartas.

En la práctica, he utilizado un entero de 64 bits para la clave y un entero de 64 bits para los datos.

Dados cinco números $a$ , $b$ , $c$ , $d$ , $e$ por debajo de 52, es fácil ver que su producto cabe en un entero de 32 bits con signo, porque $52\cdot51\cdot50\cdot49\cdot48=311875200 < 2^{31}$ . Entonces, si reduzco la fracción $$ \frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d}+\frac{1}{e}=\frac{p}{q} $$ donde $(p,q)=1$ , entonces sé que el valor $p\cdot2^{32}+q$ encaja perfectamente en un entero de 64 bits. Esta será mi clave. Cuando en la segunda parte del programa busque quintos que coincidan, pondré mi clave en $\frac{q-p}{p}$ , para buscar entre los ya almacenados uno que sumado al actual dé suma $1$ .

La representación de los cinco números $a$ , $b$ , $c$ , $d$ , $e$ puede gestionarse de varias maneras, pero he decidido utilizar un número de 64 bits sin signo y ajustado a $1$ el $a$ -a, $b$ -th, ..., y $e$ -ésima parte. De este modo, es fácil comprobar si dos quíntuples tienen números en común, ya que basta con comprobar si el AND a nivel de bits es cero o no.

Creo que es todo.

Apéndice . El algoritmo anterior se debe a mi mala vista. Cuando calculé el valor ${51\choose 10}$ (la tarjeta ' $1$ ' es inútil) No me di cuenta de que era un número tan pequeño. Leí mal el exponente. Efectivamente, sólo es de $1.28\cdot 10^{10}$ . Con los ordenadores modernos es muy fácil. De hecho, escribí apresuradamente un programa tonto en C que en unos 36 segundos imprimió las 1431 soluciones.

He aquí una versión corta (¡no debe tomarse como un ejemplo de buena programación!)

#include<stdio.h>
int main()
{
  long double Inv[53],s0,s1,s2,s3,s4,s5,s6,s7,s8,s9,Err=6.0E-11;
  long double Min=1-Err, Max=1+Err;
  for (int i=1; i<53; i++) Inv[i]=1/(long double)i;
#define FOR(p,c) for(int i##c=52; i##c>i##p && (s##c=(s##p+Inv[i##c]))<Max;i##c--)
  int i0, cnt=0;
  for (i0=2, s0=0.5; i0<=52; s0=Inv[++i0])
  FOR(0,1) FOR(1,2) FOR(2,3) FOR(3,4)
  FOR(4,5) FOR(5,6) FOR(6,7) FOR(7,8) FOR(8,9)
  if (s9>Min) printf("%4d %.15Lf %d %d %d %d %d %d %d " 
  "%d %d %d\n",++cnt,s9, i0,i1,i2,i3,i4,i5,i6,i7,i8,i9);
  return 0; 
}

Answer 2

El caso a=6 se puede eliminar con lápiz y papel.
Considera que 1/1 = 1, 1/2 = 7, 1/3 = 9 y 1/4 = 10, todos mod 13. El único múltiplo de 13 que podemos obtener de las sumas de estos números es 7+9+10=26, lo que demuestra que 1/26+1/39+1/52=1/12 es factible, pero 1/13 no debe aparecer en la suma.
También 1/1 = 1, 1/2 = 6, 1/3 = 4, 1/4 = 3, todos mod 11. El único múltiplo de 11 en este caso es 1+6+4=11, por lo que 1/44 está excluido, y si 1/11 está en la suma, entonces 1/22 y 1/33 también deben estarlo.
Estas dos consideraciones por sí solas significan que a=6 es imposible:

sum(1.0/[6,7,8,9,10,11,12,13,14,15]) =    1.034896
sum(1.0/[6,7,8,9,10,11,12,14,22,33]) =   0.9670634
sum(1.0/[6,7,8,9,10,12,14,15,16,17]) =   0.9883869

Consideraciones similares excluyen un total de 20 tarjetas. Con esto, junto con la exclusión de la carta 1 por su magnitud, la baraja se reduce a 31 cartas y sólo hay 4 posibilidades para la carta más baja. Añade una prueba de salida temprana en torno a la séptima carta y el código compilado se reduce a unos 30 ms. El código interpretado debería pasar en un tiempo tolerable. Obviamente, no es una mejora de la fuerza bruta, ya que es lo suficientemente rápida y menos propensa a errores.

Answer 3

Mi simulación es mucho más sencilla (requiere mucha menos reflexión). Tengo $10$ bucles anidados (a,b,c,d,e,f,g,h,i,j). a va de $2$ a $6$ ya que la carta con el número más bajo sólo puede ser una de esas opciones. Cada bucle interno comienza en $1$ más que el bucle que se encuentra inmediatamente fuera de él. El límite superior de los bucles es $43$ para un, $44$ para b, ... $51$ para i, $52$ para j. Está funcionando ahora pero es lento y tendrá que funcionar durante la noche. Estoy almacenando los ganadores en una base de datos para poder estudiarlos más tarde. Compararé los resultados cuando el programa termine y comprobaré todas las respuestas en la base de datos para asegurarme de que realmente son iguales $1$ .

Mi programa hace una comprobación de que la suma de los recíprocos es igual a $1.00000000000000000$ ( $17$ ceros). Creo que ese es el límite de la precisión. Dudo que cualquier fallo cercano se trunque en el $18$ o un dígito decimal más alto y no ser un $1$ .

La verdad es que me sorprende que no se hayan reportado soluciones con la tarjeta más baja que es el 6.

Así que éste parece uno de esos problemas que sólo pueden resolverse prácticamente a través de ordenadores, no utilizando un método de papel y lápiz. Al menos no he visto ese tipo de solución presentada aquí todavía. Le daré más tiempo a la gente porque parece un problema difícil de resolver de esa manera.

$Update$ : Por alguna misteriosa razón, mi programa se perdió algunas soluciones como $5,6,8,9,10,12,15,18,20,24$ . Se confirma como un error de redondeo, por lo que necesito utilizar un método diferente en el que multiplico todos los a,b,c,d,e,f,g,h,i,j (todos los rangos de la tarjeta), establezco ese producto como p, y luego compruebo si (p/a+p/b+p/c+p/d+p/e+p/f+p/g+p/h+p/i+p/j) = p. De esta manera no hay fracciones decimales porque estoy garantizando que no habrá ningún resto en la división, ya que todos los rangos son factorizados, por lo tanto pueden ser factorizados. Tengo que volver a hacer esto, así que me llevará muchas más horas. Un ejemplo sencillo de cómo funciona este algoritmo es si tomamos sólo $4$ tarjetas ( $2$ , $4$ , $5$ y $20$ ). Sabemos que $1/2 + 1/4 + 1/5 + 1/20$ = $1$ . Para comprobarlo, multiplicamos $2*4*5*20$ y obtener $800$ . Ahora básicamente convertimos todos los recíprocos en $800$ en el denominador por lo que $1/2$ = $400/800 $ ... Los suman y (en este caso), si coinciden $800/800$ entonces son una solución.

$Update 2$ . También tengo $1431$ ahora con mi nuevo algoritmo. Simulando todas las posibilidades de $10$ cartas extraídas al azar de la baraja de $52$ pero con la primera tarjeta sólo $2,3,4$ o $5$ mi programa está mostrando alrededor de $7.6$ mil millones de combinaciones de tarjetas escaneadas. Así que ahora mi siguiente paso (ya que tengo la respuesta correcta, creo), es acelerar el algoritmo, ya que no es necesario comprobar todos los 7,6 mil millones de manos, ya que algunos pueden ser "cortocircuitado" (detenido antes de tiempo) cuz la suma es ya demasiado alto.

$Update 3$ . Puse algunos ajustes en mi programa para que no tenga que comprobar todo $7.6$ mil millones de manos. Básicamente, mantiene un total acumulado del recíproco para el número de cartas que se han visto hasta ahora en la mano. Si ya está en $1$ (o por encima), esa mano se abandona antes y se intenta la siguiente. Además, con el $10$ bucles anidados, compruebo en cada bucle si la suma acumulada superará $1$ si se añade el valor mínimo de los bucles interiores. Esto significaría que, independientemente de los valores de los bucles interiores, la suma de los recíprocos con cualquier combinación de las cartas restantes añadidas será superior a $1$ para que esa mano pueda ser abandonada también. Puedo hacer esto porque mis bucles anidados están ordenados de tal manera que cada bucle interno comienza en $1$ más alto que el bucle que se encuentra inmediatamente fuera de él.

Algunos ejemplos de abandono de una mano antes de tiempo (con fines ilustrativos).

Recuerda que mis bucles anidados se llaman a,b,c,d,e,f,g,h,i,j empezando por el más externo.

Primero una fácil. $2,3,4$ d,e,f,g,h,i,j. Podemos abandonar esta mano ya que $1/2 + 1/3 + 1/4$ ya es más que $1$ así que no nos importa lo que son d,e,f,g,h,i y j, así que nos saltamos todos esos e intentamos $2,3,5$ ,d,e,f,g,h,i,j pero que también es más que $1$ ( $1/2+1/3+1/5$ ) por lo que abandonamos todos los $2,3,5$ combinaciones...

La segunda comprobación que hago para abandonar una mano es cuando la suma acumulada hasta el momento se acerca a $1$ (como $0.97619$ ) como es el caso cuando a,b,c (los más externos $3$ bucles) son $2,3,7$ . Eso da $1/2$ + $1/3$ + $1/7$ = $0.97619$ .... No hay manera $2,3,7$ puede ser parte de una solución ya que el resto $7$ tarjetas (como mínimo) contribuiría $1/46$ , $1/47$ , $1/48$ ... $1/52$ . Así que mi programa comprueba esto y ni siquiera termina el $10$ mano de la tarjeta en casos como éste.

$Update - 4$ . Pongo otro cheque para acelerar el programa. Compruebo el caso en que en cada bucle anidado, la suma de los recíprocos de las cartas restantes no puede sumar 1 porque incluso con el valor máximo del recíproco de los rangos de las cartas restantes, la suma será demasiado baja (por debajo de $1$ ). Este ajuste mejoró enormemente la velocidad de ejecución del programa interpretado. El simple hecho de recorrer en bucle todos los $7.9$ mil millones de combinaciones de cartas llevó mucho tiempo $10$ horas más o menos (durante la noche). Con la "mano abandonada" comprueba si es demasiado alta (por encima de $1$ ) o demasiado bajo (por debajo de $1$ ) antes de comprobar si es igual a $1$ Pude conseguir que el programa se redujera a sólo $4.5$ minutos de ejecución (más de $100$ veces más rápido corriendo). Además, sólo alrededor de $73$ millones de manos se verificaron realmente para la igualdad a $1$ . La salida en mi pantalla es divertido ver cuz lo que solía arrastrarse como todos $7.9$ mil millones de manos se revisaron ahora "rasgaduras" como sobre sólo $1$ en $100$ manos (en comparación con las anteriores) ahora se comprueban.

$Update-5$ Con la ayuda de la lista de exclusión, mi casi $200$ líneas de código interpretado se ejecutan en $6.7$ segundos. Un agradecimiento especial a todos los que han participado en la elaboración de esta lista de exclusión. El programa original no optimizado solía tardar unos $10$ horas que es $36,000$ segundos. El programa altamente optimizado ahora sólo tarda $6.7$ segundos que es más que $5000$ veces más rápido para obtener la misma respuesta correcta de $1431$ . Todavía es posible que haya algunas optimizaciones más. ¿Quizás la lista de exclusión no esté completa?