EDITAR: No me di cuenta de que esta era una pregunta de Programación Dinámica, y como tal, mi respuesta en realidad no puede responder la pregunta. No obstante, lo dejaré, en caso de que ayude a alguien. [/editar]
Me gustaría asumir la respuesta del Islam y completarla con una prueba.
Veamos qué sucede en un pequeño conjunto de situaciones:
Si [matemáticas] n = 1 [/ matemáticas], puedo tomar 1 piedra y dejar al oponente sin piedra para tomar, por lo tanto, el oponente pierde. Esta es una posición ganadora.
Si [matemáticas] n = 2 [/ matemáticas], puedo tomar 2 piedras y dejar al oponente sin piedra para tomar, por lo que el oponente pierde. Esta es una posición ganadora.
Si [matemáticas] n = 3 [/ matemáticas], puedo tomar 1 piedra o 2 piedras. En ambos casos, el oponente se enfrentará a una posición ganadora. Así pierdo.
- ¿Cuáles son los algoritmos necesarios para resolver todos los problemas (usando C ++) en cualquier concurso de codificación competitivo?
- ¿Cuál es la probabilidad de que un determinado número binario de 6 bits divida perfectamente un binario aleatorio de 15 bits?
- ¿Es necesario pensar en una solución recursiva primero antes de proceder a resolver un problema de DP?
- ¿Qué es una explicación intuitiva de MapReduce?
- ¿Qué es segmentar segmentado?
Entonces propongamos un lema y demostrémoslo:
Lema : Para cualquier [matemática] k [/ matemática], [matemática] n = 3k + 1 [/ matemática] es una posición ganadora, [matemática] n = 3k + 2 [/ matemática] es una posición ganadora, y [matemática ] n = 3k + 3 [/ math] es una posición perdedora. (En otras palabras, [matemática] n \ equiv 1 [/ matemática] y [matemática] n \ equiv 2 [/ matemática] son posiciones ganadoras; [matemática] n \ equiv 0 [/ matemática] es una posición perdedora).
Por inducción, demostramos que es cierto para cualquier [math] k \ ge 0 [/ math]. El lema es verdadero para [matemáticas] k = 0 [/ matemáticas] (como se vio anteriormente), así que supongamos que es verdadero al menos algún valor [matemáticas] k_0 [/ matemáticas].
Veamos qué sucede en el caso [math] k_0 + 1 [/ math].
Si [math] n = 3 (k_0 + 1) + 1 = 3k_0 + 4 [/ math], entonces [math] n \ equiv 1 [/ math] y puedo tomar 1 piedra o 3 piedras (de las reglas que usted dio). Si tomo 1 piedra, el oponente queda en la posición [matemáticas] n = 3k_0 + 3 [/ matemáticas], que, según nuestra hipótesis de inducción, es una posición perdedora. Por lo tanto, esta es una posición ganadora.
Si [matemáticas] n = 3 (k_0 + 1) + 2 = 3k_0 + 5 [/ matemáticas], entonces [matemáticas] n \ equiv 2 [/ matemáticas] y puedo tomar 1 piedra, 2 piedras o 3 piedras (de las reglas que le diste) Si tomo 2 piedras, el oponente queda en la posición [matemáticas] n = 3k_0 + 3 [/ matemáticas], que, según nuestra hipótesis de inducción, es una posición perdedora. Por lo tanto, esta es una posición ganadora.
Si [matemática] n = 3 (k_0 + 1) + 3 = 3k_0 + 6 [/ matemática], entonces [matemática] n \ equiv 3 [/ matemática] y puedo tomar 1 piedra o 2 piedras (de las reglas que usted dio). Si tomo 1 piedra, el oponente queda en la posición [matemáticas] n = 3k_0 + 5 [/ matemáticas], que es una posición ganadora; si tomo 2 piedras, el opoonente queda en la posición [matemáticas] n = 3k_0 + 4 [/ matemáticas], que también es una posición ganadora. Por lo tanto, no importa lo que elija, el oponente gana. Por lo tanto, esta es una posición perdedora.
¡Esto concluye nuestra prueba y el lema es cierto!
