Digamos que una persona con memoria perfecta es jugar la carta-juego de Concentración. Él/ella de forma aleatoria establece 2n tarjetas (es decir. n de la tarjeta de pares ordenados de forma aleatoria y repetida, por turnos, que consiste en voltear dos cartas, sin mirar la primera carta. Cuando las cartas de acuerdo, ellos se retiran del juego. Cuando las cartas no coinciden, se volvió más. El jugador gana cuando todos los pares se encuentran y todas las cartas se quitan.
Un perfecto juego es jugado en sólo n vueltas, pero incluso un jugador perfecto (uno con memoria perfecta) no podía esperanza de acercarse a un juego perfecto como todavía habría un montón de adivinanzas necesario.
Cómo calcular el número esperado de vueltas que se requieren para ganar para el jugador con memoria perfecta?
EDIT 2 -- aclaración de las normas
Ya que todos los principios de respuestas parecen a leer esta pregunta, puesto que NO puedes mirar la primera carta, estoy editando que en las reglas.
Originalmente yo estaba pensando que usted PUEDE mirar la primera carta (ya que es como yo había aprendido el juego y, a mi conocimiento, que es como se suele jugar.
Por esa regla de ajuste, he publicado una nueva pregunta aquí: ¿Cómo muchas vueltas, en promedio, se tarda para que un jugador perfecto para ganar Concentración (ajustado)?
EDICIÓN -- la Comprobación de las respuestas en contra de una simulación
La estrategia propuesta en AlgorithmsX la respuesta parece que tiene sentido para mí - es decir, el juego tiene lugar en dos etapas distintas.
Etapa 1: flip todas las cartas para saber dónde están, y...
Etapa 2: limpiar/perfectamente encontrar todos los partidos (ya que usted sabe donde están).
Lo que mejora en un $2n$ juego es pura casualidad, ¿cuántos partidos se encuentran en la Etapa 1?
Para comprobar una determinada respuesta, escribí el siguiente código para simular el problema. Simplemente al azar baraja una matriz con los pares de $0$ $n-1$y los cheques para los pares adyacentes que vendría en el barrido durante la Etapa 1 (un 0-1 par es una coincidencia, pero el 1-2 no es). Esto parece como una buena forma de comprobar las respuestas, porque (para mí, al menos) es más fácil razonar sobre la simulación de las matemáticas.
En la actualidad, AlgorithmsX la respuesta para $n=3$ resultados en $5.6$, pero yo esperaría a ser $5.4$ restricción de cualquier tipo de errores en la simulación.
Algunos resultados de la simulación (1 millón de ensayos)
n | 2 | 3 | 4 | 5 | 6 |
turns | 3.33 | 5.40 | 7.43 | 9.44 | 11.45 |
Código para simular la respuesta $n$
function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
var simulation = function(n, nTrials){
// make array from 0 to n-1 with pairs
var cards = Array.apply(null, {length: n}).map(Number.call, Number);
cards = cards.concat(cards);
var totalTurns = 0;
var trialsLeft = nTrials;
while(trialsLeft>0){
cards = shuffle(cards)
var matches = 0;
for(var i=0; i<n; i++){
if(cards[2*i]===cards[2*i+1]){
matches++
}
}
totalTurns += 2*n-matches;
trialsLeft--
}
return totalTurns/nTrials;
}
