3 votos

Elección de 26 de 52 cartas, probabilidad recíproca.

Aquí tenemos una baraja de $52$ tarjetas numeradas $1$ a través de $52$ (sólo números enteros). Seleccionamos aleatoriamente $26$ de esos $52$ tarjetas (sin sustitución). Cada carta es equiprobable. La tarea consiste en averiguar cuántas manos tienen la suma de los recíprocos de los rangos elegidos exactamente igual a $2$ . $52 \choose 26$ es bastante grande (alrededor de $496$ trillón) por lo que un recuento directo podría no ser posible en algunos ordenadores en un tiempo razonable. $26$ resulta ser muy conveniente, ya que hay $26$ letras del alfabeto, lo que me permite ejecutar bucles anidados con nombres de letras individuales de a,b,c. .z.

Estoy interesado en ver qué "poda" y exclusiones de rango se pueden hacer a este problema cuz este es un espacio de estado mucho más grande que $16$ mil millones (si se elige sólo $10$ cartas de una baraja de $52$ ). Acerca de $31,000$ veces mayor.

Una ligera insinuación/empieza de cabeza: La suma máxima posible es de aproximadamente $3.85442$ y la suma mínima posible es de aproximadamente $0.6836$ . Esta es una de las razones por las que elegí $2$ como parece que es posible. Ni siquiera sé todavía si hay una solución única, pero sospecho que hay muchas, aunque un porcentaje muy pequeño.

5voto

Lefteris Puntos 6249

Si no cometí un error horrible, hay 32 soluciones.

Por ejemplo, $$ 2=\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{9}+\frac{1}{ 10}+\frac{1}{11}+\frac{1}{12}+\frac{1}{15}+\frac{1}{16}+\frac{1}{18}+ \frac{1}{20}+\frac{1}{21}+\frac{1}{22}+\frac{1}{24}+\frac{1}{26}+\frac{1}{30} +\frac{1}{33}+\frac{1}{35}+\frac{1}{36}+\frac{1}{39}+\frac{1}{40}+\frac{1 }{42}+\frac{1}{45}+\frac{1}{48}+\frac{1}{52} $$

En realidad, este problema es más fácil que el anterior, después de algunas podas iniciales. Acabo de analizar 6287724 configuraciones.

Para cada primo $p\ge7$ He comprobado qué combinaciones de sumas de recíprocos de múltiplos de $p$ podría llevar a una fracción en la que el primo $p$ no aparece en el denominador.Ya que $7\cdot11>52$ No combiné múltiplos de diferentes primos mayores que $7$ .

Por ejemplo, para $p=11$ sólo hay $\frac{1}{11}+\frac{1}{22}+\frac{1}{33}=\frac{1}{6}$ .

para $p=13$ sólo hay $\frac{1}{26}+\frac{1}{39}+\frac{1}{52}=\frac{1}{12}$ ,

y para $p=7$ hay $9$ sumas, como $\frac{1}{7}+\frac{1}{42}=\frac{1}{6}$ o $ \frac{1}{7}+\frac{1}{21}+\frac{1}{28}+\frac{1}{42}=\frac{1}{4}. $

Los números restantes, una vez que se quitan los múltiplos de todos los primos mayores o iguales a $7$ , sólo son $24$ : $$ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50 $$

Así, para cada posible elección de una suma para el primo $7$ , uno para prime $11$ y uno para prime $13$ (entre las que se encuentra la suma de vacíos) seleccioné todas las combinaciones posibles del $24$ números anteriores para tener un total de $26$ números, y comprobé las sumas.

Por ejemplo, si selecciono para $13$ nada, pues $11$ la única suma posible ( $3$ términos) y para $7$ la suma mostrada con $4$ términos, tengo que comprobar $${24\choose26-3-4}={24\choose19}=657800 $$ combinaciones. En total las combinaciones a comprobar eran 6287724, así que en lugar de un programa en C utilicé un pequeño programa en Mathematica, que es mucho más lento pero puede construir directamente todos los subconjuntos de un conjunto dado.

Las soluciones primera y última, lexicográficamente, son $$ 2, 4, 7, 9, 10, 11, 12, 14, 15, 16, 18, 21, 22, 24, 26, 28, 30, 33, 35, 36, 39, 40, 42, 45, 48, 52 $$ y $$ 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 18, 20, 21, 22, 24, 26, 28, 30, 33, 36, 39, 42, 45, 48, 52 $$

5voto

user5713492 Puntos 61

No iba a responder, pero acabo de adquirir un nuevo compilador y también quería mostrar al autor original de la pregunta cómo podía utilizar arrays para facilitarle la vida.

La teoría elemental de los números, tal y como se ha comentado aquí y en el hilo complementario, nos permite eliminar el conjunto $E=\{13,17,19,23,25,27,29,31,32,34,37,38,41,43,44,46,47,49,50,51\}$ y también dicta que los conjuntos $C_{11}=\{11,22,33\}$ , $C_{13}=\{26,39,52\}$ y $C_{16}=\{16,48\}$ están todos en el conjunto de tarjetas en un ensayo exitoso o todos ausentes.

Esto deja el conjunto $F=\{1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45\}$ de $24$ libre, o al menos con menos restricciones. Tenemos que incluir al menos uno de los conjuntos restringidos, $C_{11}$ , $C_{12}$ o $C_{16}$ porque no hay suficientes cartas en $F$ . Las sumas de los recíprocos de los elementos de $F$ , $C_{11}$ , $C_{12}$ y $C_{16}$ son $\frac{85}{24}$ , $\frac16$ , $\frac1{12}$ y $\frac1{12}$ respectivamente.

$F\cup C_{16}$ es lo suficientemente grande, pero la suma es $\frac{87}{24}$ demasiado grande. También $F\cup C_{11}$ y $F\cup C_{13}$ suma a $\frac{89}{24}$ y $\frac{87}{24}$ , por lo que incluso si se quita la tarjeta $1$ para llegar a $26$ tarjetas la suma será demasiado grande.

$F\cup C_{11}\cup C_{16}$ sumas a $\frac{91}{24}$ , por lo que tendríamos que eliminar $3$ artículos de $F$ con valor total $\frac{43}{24}$ . Desde $\frac12+\frac13+\frac14=\frac{13}{12}<\frac{43}{24}$ , tarjeta $1$ debe ser eliminado. Además, como $\frac11+\frac13+\frac14=\frac{19}{12}<\frac{43}{24}$ , también tarjeta $2$ debe ser eliminado, pero ahora estamos en $\frac7{24}$ con una sola carta.

$F\cup C_{13}\cup C_{16}$ se elimina de la consideración de manera similar.

$F\cup C_{11}\cup C_{13}$ sumas a $\frac{91}{24}$ también, pero ahora tenemos $4$ tarjetas para trabajar. Una vez más, las consideraciones de magnitud dictan que las tarjetas $1$ y $2$ están destinados a ser eliminados, pero ahora después de hacerlo nos encontramos con que tenemos que llegar a $\frac{91}{24}-2-\frac11-\frac12=\frac7{24}$ en dos tarjetas. Como el denominador es divisible por $8$ una de las otras cartas retiradas debe ser $8$ , $24$ o $40$ . Encontramos que $\frac18+\frac16=\frac1{24}+\frac14=\frac1{40}+\frac4{15}=\frac7{24}$ Así que tenemos dos soluciones:

$\{3,4,5,7,9,10,11,12,14,15,18,20,21,22,24,26,28,30,33,35,36,39,40,42,45,52\}$

y

$\{3,5,6,7,8,9,10,11,12,14,15,18,20,21,22,26,28,30,33,35,36,39,40,42,45,52\}$

Eso deja el conjunto $F\cup C_{11}\cup C_{13}\cup C_{16}$ . Una vez más, las consideraciones de magnitud eliminan la tarjeta $1$ de la consideración por lo que tenemos que encontrar $5$ más tarjetas de $F$ que suman $\frac{31}{8}-2-\frac11=\frac78$ . Ahora bien, la paciencia y la teoría elemental de los números podrían limpiar esto en una hora más o menos a mano, pero eso sería un largo post. En su lugar, ofrezco un programa de fuerza bruta que busca el espacio restante de ${23\choose 5} = 33649$ posibilidades.

Creo matrices para los conjuntos $F$ , $C_{11}$ , $C_{13}$ y $C_{16}$ y luego mantener los recíprocos de las cartas en $F$ . Entonces calculo la suma de los recíprocos de $F\cup C_{11}\cup C_{13}\cup C_{16}-\{1\}$ y restar $2$ para saber cuál es mi objetivo para el próximo $5$ tarjetas que hay que eliminar es. Haz un bucle con todas las posibilidades, contando e imprimiendo todas las soluciones. Como el error de redondeo va a ser menor que $50$ ulps y el mayor error real es $\frac1{2^3\cdot3^2\cdot5\cdot7}=\frac1{2520}$ cortando las posibles soluciones en $100$ ulps separa definitivamente las soluciones verdaderas de las espurias.

El programa imprime $30$ soluciones, por lo que junto con el $2$ obtenido a mano, esto es consistente con los resultados de @Giovanni Resta.

program cards26
   implicit none
   integer, parameter :: dp = kind([double precision::])
   integer i1,i2,i3,i4,i5
   integer, parameter :: cards(24) = [1,2,3,4,5,6,7,8,9,10,12,14, &
      15,18,20,21,24,28,30,35,36,40,42,45]
   integer, parameter :: c11(3) = [11,22,33]
   integer, parameter :: c13(3) = [26,39,52]
   integer, parameter :: c16(2) = [16,48]
!   integer, parameter :: exclude(20) = [13,17,19,23,25,27,29,31, &
!      32,34,37,38,41,43,44,46,47,49,50,51]
   real(dp),parameter :: reciprocals(size(cards)) = 1.0_dp/cards
   real(dp) x0,x1,x2,x3,x4,x5
   integer N

   x0 = sum(1.0_dp/cards)+sum(1.0_dp/c11)+sum(1.0_dp/c13)+ &
      sum(1.0_dp/c16)-2-1
   write(*,*) 'Target = ', x0
   N = 0
   do i1 = 2,size(cards)-4
      x1 = reciprocals(i1)
      do i2 = i1+1,size(cards)-3
         x2 = x1+reciprocals(i2)
         do i3 = i2+1,size(cards)-2
            x3 = x2+reciprocals(i3)
            do i4 = i3+1,size(cards)-1
               x4 = x3+reciprocals(i4)
               do i5 = i4+1,size(cards)
                  x5 = x4+reciprocals(i5)
                  if(abs(x5-x0) < 100*epsilon(1.0_dp)) then
                     N = N+1
                     write(*,'(i4,1x,26(i2,1x),f19.17)') N, &
                        pack(cards,[(all(cards(N)/=cards([1,i1,i2,i3, &
                           i4,i5])),N=1,size(cards))]),c11,c13,c16,x5
                  end if
               end do
            end do
         end do
      end do
   end do
end program cards26

0voto

David Puntos 388

Bueno hasta ahora todo lo que tengo es el $26$ bucles anidados configurados como si fueran a iterar todos los $496$ combinaciones de tarjetas de trillones pero luego cuando excluyo el $20$ tarjetas, me dice $906,192$ combinaciones de cartas. Esto es simplemente $52-20 \choose 26$ . El tiempo que se tarda en recorrer los bucles vacíos es de aproximadamente $6.5$ minutos por lo que es razonable. Así que mi siguiente paso será insertar el código para comprobar si la suma es exactamente igual a $2$ y contarlos para ver si consigo $32$ .

Además, si excluyo $1$ como la carta con el número más bajo, obtengo $169,911$ manos en $2$ min $40$ sec.

He probado a ejecutar mi programa comprobando la suma de $2$ pero no conseguí $32$ así que tengo que averiguar por qué.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X