MAE0515 _ Atividade 1 (2021/2)

Prévia do material em texto

MAE0515 - Introdução à Teoria dos Jogos
2º semestre de 2021
Prof. Renato Vicente
Atividade 01
João Pedro de Freitas Feliciano Moreira
nº USP: 8124097
1
Exerćıcio 1.1
No caso de Jogo NIM onde o ganhador é quem remove o último palito, temos:
4 filas: 9, 10, 11, 12. Em termos binários: 1001, 1010, 1011, 1100.
Somando, temos um número par de 1’s. Portanto o 2º jogados ganha:
i) vitória corresponde à soma zero;
ii) se a soma é zero, a próxima jogada com certeza resultará em soma não-zero;
iii) se a soma não é zero, a próxima jogada sempre pode torná-la igual a zero.
Exerćıcio 1.7
Esse jogo é parecido com o NIM, para ganhar o jogo é nescessário ser o último a mover
uma torre.
Temos 6×8 = 36 casas na pimeira jogada, número par de casas para se mover, dado que
cada casa representa 1, temos um número par de 1’s. Portanto o segundo jogador ganha:
i) vitória corresponde à soma zero;
ii) se a soma é zero, a próxima jogada com certeza resultará em soma não-zero;
iii) se a soma não é zero, a próxima jogada sempre pode torná-la igual a zero.
2
Exerćıcio 1.9
Teorema (1): Em qualquer jogo combinatório progressivamente limitado sem empates
um dos jogadores tem uma estratégia vencedora que só depende do estado do jogo.
Vamos demonstrar por absurdo que é o 1º jogador quem tem a estratégia vencedora.
i) Suponha que o 2º jogador tem uma estratégia vencedora. Vamos chamar de S;
ii) O 1º jogador escolhe um hexagono qualquer;
iii) 2º jogador faz sua jogada;
iv) 1º jogador joga aleatoriamente até que seja posśıvel gira o tabuleiro e assumir a
estratégia vencedora S do 2º jogador.
O 1º jogador teria assim vitória garantida também, contrariando o Teorema (1), a su-
posição é inexeqúıvel.
Portanto, o 1º jogador detem a estratégia vencedora.
3