Considere la situación de este vídeo. Las tarjetas de un funcionamiento normal de la cubierta se reparten de una en una, mientras que el jugador que adivine cuál es el número de la tarjeta es no (traje es ignorado). Para ser claros, el jugador quiere ir a través de toda la cubierta, nunca tener su suposición coincide con el de la tarjeta. ¿Cuáles son las probabilidades de que el jugador va a lograr esto, suponiendo que poseen una memoria perfecta y el uso de una estrategia perfecta? Hay cierto debate en los foros.
Respuestas
¿Demasiados anuncios?
La probabilidad es $$\frac{47058584898515020667750825872}{174165229296062536531664039375} \approx 27.0195\%$$ lo que coincide con el varias simulaciones en su vinculados mensajes en el foro y en Paxinum la respuesta aquí.
En primer lugar, voy a esbozar una prueba de que la estrategia óptima es cada vez supongo que de cualquier rango (1 a 13), que se ha visto el mayor número de veces hasta el momento. Si esto es obvio para usted, usted puede saltar a la siguiente sección.
La estrategia óptima
Vamos a llamar a cada supongo que usted tiene que hacer una "ronda". Por lo que el juego tiene más de 52 rondas.
Reivindicación 1. La estrategia óptima es adivinar, en cada ronda, un rango que maximiza la probabilidad de ganar la ronda.
Prueba. Esencialmente, supongo que en cualquier ronda no limitar el futuro conjeturas. Lo que, supongo, se determina sólo si el juego termina inmediatamente, y no el estado futuro que se determina por lo que las cartas en la baraja y no por lo que supongo. Formalmente, supongamos que usted tiene cualquier estrategia de $S$, lo que en algunos ronda adivina un rango que no es óptimo para esa ronda. A continuación, se puede reemplazar con una estrategia que en esa ronda adivina el mejor rango, y en futuras rondas que hace exactamente lo mismo que $S$. (Para esta prueba al trabajo, puede modificar el juego para que podamos seguir para realizar estimaciones para todos los 52 rondas, y sólo al final decidir que hemos perdido el juego si alguna vez nos imaginamos un de la tarjeta correctamente. Obviamente, esto no afecta al juego.) Esta estrategia tiene un estricto mayor probabilidad de ganar de $S$; por lo tanto $S$ no es óptimo.
Reivindicación 2. En cada ronda, la mejor conjetura es un rango que se ha visto el mayor número de veces.
Prueba. Supongamos que el rango $r$ ha sido visto $s_r$ veces hasta ahora, y que todavía hay $D$ cartas de la baraja. Así que hay $(4-s_r)$ tarjetas de rango $r$ todavía en la cubierta. Si adivina $r$, la probabilidad de perder en la ronda, es decir, la probabilidad de que la siguiente carta que vueltas tiene rango $r$$\frac{4-s_r}{D}$, lo que se minimiza al $4-s_r$ es mínimo, es decir, $s_r$ es máxima.
Ponerlos juntos,
Corolario. La estrategia óptima es adivinar, en cada ronda, un rango que se ha visto el mayor número de veces.
Tenga en cuenta que si usted ha visto varias filas con el mismo número de veces ($s_{r_1} = s_{r_2}$), no importa que uno adivina. Así que vamos a asumir wlog que supongo que (dicen) el más pequeño de tal rango.
Cálculo
Ahora que nos hemos fijado la estrategia, ¿cómo podemos calcular la probabilidad de que se gana el juego? En principio, se podría tratar de todas las permutaciones de la cubierta y ver cuántas funciona. En la práctica, que nos deja con $52! > 10^{67}$ permutaciones, de los cuales usted puede en la mayoría de probar unas cuantas y comprobar (como la otra respuesta y las simulaciones que se han hecho), pero no es posible enumerar todos ellos. Incluso si usted nota que usted no se preocupan por el traje, usted todavía tiene $52!/4!^{13} > 10^{49}$ órdenes, e incluso si usted observa que los rangos son simétricas usted todavía tiene $52!/(4!^{13} \times 13!) > 10^{40}$ órdenes de comprobar.
Para algo mejor, observe que el estado de la partida en cualquier punto es capturado por el número de veces que se ha visto cada rango (a lo largo de la $s_r$s arriba); el orden en que aparecieron originalmente es irrelevante ahora y en el futuro. Así se puede describir el estado de la pantalla de juego, especificando $s_r$ por cada $1 \le r \le 13$, y como $0 \le s_r \le 4$, esto le da a $5^{13} = 1220703125$, mucho más manejable. Por algo aún mejor, tenga en cuenta que como no se preocupan por el real categorías, sino sólo su número, usted puede simplemente mantener cómo muchas de las cartas que se han visto 0 veces, cuántas se han visto 1 vez, etc. Es decir, que $n_k$ denotar el número de $r$ que $s_r = k$. Luego de que el estado es $(n_0, n_1, n_2, n_3, n_4)$, e $\sum_{k=0}^{4} n_k = 13$. De hecho, para cualquier estado en que $n_4 > 0$ puede determinar la probabilidad de ganar de ese estado inmediatamente (es $1$, como va a seguir adivinando cualquier $r$ que $s_r = 4$, y nunca estar equivocado), por lo que sólo necesita preocuparse por los estados en los que $n_4 = 0$. El número de estados es el número de número entero no negativo soluciones a$n_0 + n_1 + n_2 + n_3 = 13$$\binom{16}{3} = 560$, un número suficientemente pequeño como para que con la paciencia suficiente incluso se podría manejar con la mano.
Deje $p_n$ la probabilidad de ganar de estado $n$, donde la tupla $n = (n_0, n_1, n_2, n_3, n_4)$ es como el anterior. El número de tarjetas visto hasta ahora es $\sum_{k=0}^4 {kn_k}$. El número de cartas en la baraja, $D$, es de 52 menos de este número. Si $n_4 > 0$,$p_n = 1$. Otra cosa, vamos a $g$ ser el más grande de $k$ que $n_k > 0$. Usted va a adivinar un rango contado en $n_g$. El número de filas con cada uno de los cargos, de la que, supongo, es $$n'_k = \begin{cases}n_k & \text{if $k\neq g$,} \cr n_k - 1 & \text{if $k=g$.}\end{cases}$$ Para un determinado $k$, para cada rango se cuentan en $n_k$, la probabilidad de que la siguiente carta que aparece es la de que el rango de es $\frac{4-k}{D}$, por lo que la probabilidad de que algunos de tarjeta de cualquier rango (distinta de la que suponemos) se convierte es $\frac{n'_k(4-k)}{D}$. Una vez que la tarjeta se enciende, el estado tiene un menor rango en $n_k$ más uno en $n_{k+1}$. Que es, al nuevo estado $m = m(k)$, $$m_j = \begin{cases}n_j - 1 & \text{if $j = k$,} \cr n_j + 1 & \text{if $j=k+1$} \cr n_j &\text{otherwise.} \end{cases}$$
Por lo que la probabilidad de ganar de estado $n$ (si $n_4 = 0$) es $$p_n = \sum_{k=0}^{3} \frac{n'_k(4-k)}{D}p_{m(k)}.$$
(El código, si alguien está interesado, es el final de la segunda revisión de esta respuesta).)
Edit: buscando en Google por la respuesta obtenida anteriormente, he encontrado este artículo:
- Kevin Liwack, Oleg Pikhurko, Suporn Pongnumkul (2008), Cómo Juegan Dundee. arXiv 0803.0156
Ellos consideran que este problema y obtener exactamente la misma respuesta. Ellos también dicen que "parece que no hay ningún general cerrado fórmula" y encontrar la respuesta por ordenador; parecen estar utilizando el algoritmo que he mencionado en el paso de arriba, que para este mazo estándar considera $5^{13}$ estados. También el estudio de la variante, donde el jugador tiene que especificar toda la secuencia de conjeturas por adelantado. Por alguna razón tienen una relativamente larga prueba de que la codicia de la estrategia anterior es óptima, pero no puedo encontrar ningún error en mi prueba anterior.
John Kramlich
Puntos
286
Ok, segundo intento:
Es evidente, que tan pronto como hemos visto 4 del mismo valor, estamos seguros. También, si la primera carta es, por ejemplo, 1, entonces la probabilidad de que la próxima carta también es 1, es sólo 3/4 de la probabilidad de que la segunda carta es de 2,3 o cualquier otro número. Por lo tanto, uno podría adivinar el número 1, en la segunda tarjeta.
Sin embargo, no podemos seguir adivinando 1, dado que por un segundo te aparecen con el tiempo.
Mi estrategia sería la siguiente: Si no hay duplicados entre las tarjetas que hemos visto, al azar supongo que en uno de estos números, ya que hay menos de los números que quedan en la baraja. En cualquier otro caso, elegir al azar una tarjeta entre los hemos visto, con la mayor multiplicidad. Ejemplo: si hemos visto 1,2,3,4,4,5,5,5,6,6,6 una suposición 5 con 50% de probabilidad y 6 con 50% de probabilidad.
Voy a correr algunas pruebas en Mathematica poco... EDIT: Este código se da cuenta de que la posibilidad de "fracaso" adivinar correctamente, (con mi estrategia) es aproximadamente un 28%. Tratar de batir.
DoGuess[] := Module[{RandomGuess, deck, seen, g, top},
deck = RandomSample@Flatten[Table[{n, n, n, n}, {n, 1, 14}]];
seen = {};
RandomGuess[s_] := Module[{tally, maxMult, guess},
If[Length@s == 0, Return[1]];
tally = Tally[seen];
maxMult = Max[Last /@ tally];
guess = First /@ Select[tally, Last@# == maxMult &];
Return[First@guess];
];
Return@Catch[
Do[
g = RandomGuess[seen];
If[top == g, Throw@0];
AppendTo[seen, top];
, {top, deck}];
1];
];
n = 15000;
N[Total[Table[DoGuess[], {n}]]/n]
John Kramlich
Puntos
286
