MO640 - Exercícios - Sobre a aula de 2007-03-28

Considere um jogo como o descrito no artigo de Pevzner envolvendo Alice e Bob, mas com a seguinte diferença: o jogador que mover o rei para o quadrado final perde o jogo. Elabore uma estratégia ótima de jogo para esta versão.
Considere o grafo abaixo onde pode-se jogar um jogo parecido com o citado por Pevzner. De cada casa o rei pode tomar qualquer seta saindo dela e ir para a casa destino da seta. O jogo começa com o rei na casa mais embaixo à direita, e termina quando o vencedor chega à casa mais acima à esquerda. Os jogadores alternam-se nas jogadas. Preencha com V e P cada casa, indicando se a casa é Vencedora ou Perdedora, de acordo com o seguinte critério. Uma casa Vencedora é uma casa a partir da qual há uma estratégia vencedora. Ou seja, se um jogador estiver na sua vez e o rei estiver na casa em questão, é possível vencer contra quaisquer jogadas do adversário. Uma casa Perdedora é o contrário, ou seja, não importa como se jogue, um bom adversário sempre acabará ganhando. Sugestão: preencha do fim para o começo colocando P na casa superior esquerda.
Considere um jogo no mesmo grafo, só que quem chega na casa mais acima à esquerda perde. Determine as casas V e P nesta nova versão. O resultado é o mesmo ao trocar V por P na outra versão? Porque?