Suponha que variemos o prêmio do jogador vencedor no jogo do Nim, de modo que o prêmio seja n dólares quando n for o número de jogadas legais feitas antes de uma posição final ser atingida. Encontre o prêmio do primeiro jogador se a posição inicial consistir em
três pilhas com uma, duas e três pedras, respectivamente.

Passo 1

O problema modifica o jogo do Nim, atribuindo ao vencedor um prêmio de n dólares, onde n é o número total de jogadas legais até esgotar todas as pedras. A posição inicial é três pilhas com 1, 2 e 3 pedras.
Para resolver, vamos tratar isso como um jogo de soma zero em que:
  1. Se uma posição tem nim-sum não nulo (posição N), o jogador a mover tem estratégia vencedora e, portanto, quer maximizar o número de jogadas até o fim.
  2. Se uma posição tem nim-sum zero (posição P), quem move está fadado a perder e, portanto, quer minimizar esse número.
    Chamaremos de V(\text{posição})çã o valor ótimo (número de jogadas) a partir dessa posição, contando até a posição terminal (0,0,0).

Passo 2

Definimos recursivamente:
V(0,0,0)=0.
Para qualquer posição X:
- Se X é N (nim-sum \neq0), então
V(X)=1+\max_{\text{moves }X\to Y}V(Y).
- Se X é P (nim-sum =0), então
V(X)=1+\min_{\text{moves }X\to Y}V(Y).
Isso reflete que o vencedor (posição N) prolonga o jogo, enquanto o perdedor (posição P) o encurta.

Passo 3

Vamos calcular V para todas as posições com poucos totais de pedras, em ordem crescente de \sum\text{pedras}:
\begin{aligned} &(0,0,0):\text{ terminal, }V=0.\\\ &(1,0,0):\text{ N, moves}\to(0,0,0)\;(P,V=0)\;\Rightarrow\;V=1+0=1.\\\ &(2,0,0):\text{ N, moves}\to \begin{cases}(1,0,0)\;(N,V=1),\\(0,0,0)\;(P,V=0)\end{cases} \;\Rightarrow\;V=1+\max(1,0)=2.\\\ &(1,1,0):\text{ P, moves}\to(1,0,0)\;(N,V=1)\text{ (duas vezes)}\;\Rightarrow\;V=1+1=2.\\\ &(3,0,0):\text{ N, moves}\to \begin{cases}(2,0,0)\;(N,V=2),\\(1,0,0)\;(N,V=1),\\(0,0,0)\;(P,V=0)\end{cases} \;\Rightarrow\;V=1+\max(2,1,0)=3.\\\ &(2,1,0):\text{ N, moves}\to \begin{cases}(1,1,0)\;(P,V=2),\\(0,1,0)=(1,0,0)\;(N,V=1),\\(2,0,0)\;(N,V=2)\end{cases} \;\Rightarrow\;V=1+\max(2,1,2)=3.\\\ &(1,1,1):\text{ N, moves}\to(0,1,1)=(1,1,0)\;(P,V=2)\;\Rightarrow\;V=1+2=3.\\\ &(2,2,0):\text{ P, moves}\to \begin{cases}(1,2,0)=(2,1,0)\;(N,V=3),\\(0,2,0)=(2,0,0)\;(N,V=2)\end{cases} \;\Rightarrow\;V=1+\min(3,2)=3.\\\ &(3,1,0):\text{ N, moves}\to \begin{cases}(2,1,0)\;(N,V=3),\\(1,1,0)\;(P,V=2),\\(0,1,0)\;(N,V=1),\\(3,0,0)\;(N,V=3)\end{cases} \;\Rightarrow\;V=1+\max(3,2,1,3)=4.\\\ &(2,1,1):\text{ N, moves}\to \begin{cases}(1,1,1)\;(N,V=3),\\(0,1,1)=(1,1,0)\;(P,V=2),\\(2,0,1)=(2,1,0)\;(N,V=3)\end{cases} \;\Rightarrow\;V=1+\max(3,2,3)=4. \end{aligned})

Passo 4

Agora as posições de total 5 que saem de (3,2,1):
\begin{aligned} &(3,2,0):\text{ N, filhos: }(2,2,0)\;(P,3),\,(2,1,0)\;(N,3),\,(2,0,0)\;(N,2),\\\ &\quad\quad(3,1,0)\;(N,4),\,(3,0,0)\;(N,3)\;\Rightarrow\;V=1+\max(3,3,2,4,3)=5.\\\ &(3,1,1):\text{ N, filhos: }(2,1,1)\;(N,4),\,(1,1,1)\;(N,3),\,(0,1,1)=(1,1,0)\;(P,2),\\\ &\quad\quad(3,0,1)=(3,1,0)\;(N,4)\;\Rightarrow\;V=1+\max(4,3,2,4)=5.\\\ &(2,2,1):\text{ N, filhos: }(1,2,1)=(2,1,1)\;(N,4),\,(0,2,1)=(2,1,0)\;(N,3),\\\ &\quad\quad(2,2,0)\;(P,3)\;\Rightarrow\;V=1+\max(4,3,3)=5.\\\ &(3,1,0)=4,\quad(2,1,1)=4,\quad(2,1,0)=3\text{ (já calculados).} \end{aligned}á

Passo 5

Na posição inicial (3,2,1) (que é P), há seis movimentos para as posições acima, cujos valores V são
5,\;5,\;4,\;5,\;4,\;3.
Como P minimiza,
V(3,2,1)=1+\min(5,5,4,5,4,3)=1+3=4.

Resposta

O prêmio de quem começa em (1,2,3) é de 4 dólares.

Exercícios de Livros Relacionados