Intenta no quedarte con la última pieza, ¡pero con una vuelta de tuerca! [Teoría de Juegos]

Question

Esta pregunta me ha estado molestando por un tiempo, y he tratado de dar pasos donde divido el n # de sushi en pares e Impares, pero todavía no puedo averiguar un algoritmo común para satisfacer estos casos.

Las reglas son las siguientes: se han pedido piezas de sashimi de atún, y cada uno de los tres participantes se turna para comer 1, 3 o 5 piezas de sashimi. La persona que coma la última pieza de sashimi debe pagar la comida. Describa un algoritmo para determinar cuántas piezas de sushi debe comer en cada turno para evitar tener que pagar la cuenta. Suponga que si hay dos jugadas diferentes que pueden hacer que el jugador anterior pierda o que el siguiente pierda. jugador anterior pierda o el siguiente pierda, se prefiere la jugada que hace perder al siguiente jugador.

Answer 1

Suponiendo un juego perfecto para todos los jugadores A, B y C, obtenemos lo siguiente (suponiendo que es el turno de A, seguido de B y luego de C):

Queda 1 pieza: A pierde

2 izquierda: comer 1: B pierde

3 izquierda: comer 1: C pierde

4 a la izquierda: comer 3, B pierde

5: 1 ó 3: C

6: 5: B

7: 1 ó 3 ó 5: C

8: A pierde pase lo que pase

9: 1: B

10: 1: C

11: 3: B

12: 1 ó 3: C

13: 5: B

14: 1 ó 3 ó 5: C

15: 1 ó 3 ó 5: A

y ahora vemos que el patrón se repite cada 7.

Por lo tanto, el juego perfecto indica que si el resto de $n$ dividido por $7$ es:

1: Pierdes pase lo que pase

2: Coma 1 ... B perderá

3: Coma 1 ... C perderá

4: Come 3 ... B perderá

5: Coma 1 o 3 ... C perderá

6: Coma 5 ... B perderá

7: C perderá pase lo que pase

Así que, si empiezas, tienes una posibilidad entre 7 de perder.