1. Redefinindo Jogos
1.1. NOVA DEFINIÇÃO. Um jogo G é um par ordenado GL jGR
jogos "previamente de…nidos".
onde GL e GR são conjuntos de
1.2. NEGATIVO E SOMA. Temos as seguintes de…nições recursivas
n
o
G =
GR j GL
n
o
G+H =
GL + H; G + H L j GR + H; G + H R
onde as operações são feitas para cada elemento dos conjuntos citados. Dois jogos G e H são ditos
equivalentes (ou mesmo iguais) quando G + ( H) = 0 (no sentido "quem começa perde").
1.3. JOGOS DIÁDICOS. Em particular, de…nimos:
0
1
2
=
=
fjg ; 1 = f0jg ; 2 = f1jg ; :::n + 1 = fnjg ; :::; 1 = fj0g ;
1
3
1
1
3
f0j1g ;
= f1j2g ; :::; = 0j
j1 ; ::
; =
2
4
2
4
2
2 = fj
1g ;
3 = fj
2g ; :::
ou seja, em geral
2p + 1
=
2n+1
2p 2p + 2
j
2n+1 2n+1
=
p p+1
j
2n 2n
1.4. A REGRA DA SIMPLICIDADE. Suponha que a < b são jogos que correspondem a
números reais. Então fajbg é o número mais "simples" que satisfaz a < x < b.
1.5. Exercícios. 1. Determine o valor do seguinte jogo de Hackenbush. Qual o "melhor" lance inicial de
cada jogador?
2. O jogo de Cutcake pode ser descrito assim: numa mesa, há vários pares ordenados de inteiros positivos
(isto é, bolos retangulares, representados na forma [x y]). Na sua vez L escolhe um dos pares [xi yi ]
presentes com yi
2 e o troca por [xi ci ] e [xi di ] onde ci e di são inteiros positivos com ci + di = yi
(isto é, L faz um corte vertical no bolo, trocando-o por dois menores). Analogamente, na sua vez, R pode
escolher um dos pares [xi yi ] com xi
2 e dividi-lo em dois pares [ai yi ] e [bi yi ] onde ai ; bi
1e
ai + bi = xi . Assim:
[1
1]
=
[1
2]
=
[2
2]
=
fjg = 0
f[1
f[2
1] + [1
1] + [2
1] jg = f0jg = 1
1] j [1
Monte uma tabela com os valores dos bolos [xi
valores encontrados?
2] + [1
yi ] para 0
2]g = f 2j2g = 0
xi ; yi
3. Considere o jogo = f0j0g
a) Calcule + . Pode-se dizer que = 0?
b) Dado n natural positivo, mostre que fnjng > k onde k = 0; 1; 2; :::; n
1
15. Você vê algum padrão nos
1: Conclua que fnjng = n + .