Mostre que os códigos de Huffman são ótimos no sentido de que representam uma seqüência de símbolos que usa o mínimo de bits entre todos os códigos de prefixo binários.
33. Desenhe uma árvore de jogo para o nim se a posição inicial consiste em duas pilhas de duas e três pedras, respectivamente. Quando desenhar a árvore, represente pelo mesmo vértice posições simétricas que resultem de uma mesma jogada. Encontre os valores de cada vértice da árvore de jogo. Quem ganha o jogo se ambos os jogadores seguirem uma estratégia ótima?

Passo 1

O enunciado pede para construir a árvore de jogo do Nim com duas pilhas de tamanhos 2 e 3, fundindo vértices simétricos, atribuir a cada vértice o seu valor de Grundy (ou seja, o mex das posições que dele se obtêm) e, por fim, decidir quem ganha com estratégia ótima.

Passo 2

Em qualquer posição do Nim de duas pilhas nós representamos o estado por um par ordenado (a,b) com a\le b. O valor de Grundy G(a,b) é
G(a,b) \;=\; \mex\bigl\{G(a',b)\,,\,G(a,b')\bigr\},
onde a'<a varia sobre as jogadas na primeira pilha e b'<b sobre as jogadas na segunda. A posição terminal (0,0) tem G(0,0)=0. Se G(a,b)\ne0 dizemos que é posição N (quem se mexe ganha); se G(a,b)=0 é posição P (quem se mexe perde).

Passo 3

Vamos listar todas as posições que surgem ao longo da árvore, em ordem de soma de pedras, e calcular G:
  1. Soma 0:
  • (0,0): não há jogadas →
G(0,0)=0.
  1. Soma 1:
  • (0,1): só se pode ir a (0,0) com G=0
G(0,1)=\mex\{0\}=1.
  • (1,1): pode ir a (0,1) (duas vezes, simétrico) com G=1
G(1,1)=\mex\{1\}=0.
  1. Soma 2:
  • (0,2): vai a (0,1) com G=1 ou a (0,0) com G=0
G(0,2)=\mex\{1,0\}=2.
  • (1,2):
    • reduzindo a primeira pilha a 0\to (0,2) com G=2,
    • reduzindo a segunda pilha a 1\to (1,1) com G=0,
    • ou a 0\to (1,0)\equiv(0,1) com G=1.
G(1,2)=\mex\{2,0,1\}=3.
  • (2,2):
    • vai a (1,2) com G=3 ou a (0,2) com G=2 (simétrico) →
G(2,2)=\mex\{3,2\}=0.
  1. Soma 3:
  • (0,3): vai a (0,2) 2, (0,1) 1, (0,0) 0
G(0,3)=\mex\{2,1,0\}=3.
  • (1,3):
    • a (0,3) 3,
    • a (1,2) 3,
    • a (1,1) 0,
    • a (1,0)\equiv(0,1) 1
G(1,3)=\mex\{3,3,0,1\}=2.
  1. Soma 5 (posição inicial):
  • (2,3):
    • reduzindo a primeira pilha: a (1,3) 2 ou (0,3) 3,
    • reduzindo a segunda pilha: a (2,2) 0, (2,1)\equiv(1,2) 3, (2,0)\equiv(0,2) 2.
G(2,3) =\mex\{2,3,0,3,2\} =1.

Passo 4

Árvore de jogo (vertices (a,b)[G(a,b)]; arestas para cada jogada)
\begin{array}{c} \bigl(2,3\bigr)[1]\\\ \quad\bigl|\!\!\!\begin{array}{@{}l} \!\!\to(1,3)[2],\;(0,3)[3],\\\ \!\!\to(2,2)[0],\;(1,2)[3],\;(0,2)[2] \end{array} \end{array}
Cada um desses vértices se ramifica até as posições de soma menor, por exemplo (1,3)[2]\to\{(0,3)[3],(1,2)[3],(1,1)[0],(0,1)[1]\}, (0,3)[3]\to\{(0,2)[2],(0,1)[1],(0,0)[0]\} etc., até chegar em (0,0)[0].

Resposta

O valor de Grundy inicial é
G(2,3)=1\neq0,
logo (2,3) é posição N e o primeiro jogador ganha seguindo uma estratégia ótima.

Exercícios de Livros Relacionados