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) é
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:
Soma 0:
(0,0): não há jogadas →
G(0,0)=0.
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.
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.
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.
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)
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.
Cálculo - Kenneth Rosen - Matemática Discreta e suas Aplicações - 6ª Edição - Capítulo 10.2 - Ex. 32