quinta-feira, 23 de agosto de 2012

Um pouco sobre jogos

Aproveitando esse post do João, eu decidi escrever essa postagem em que apresentarei alguns jogos e algumas formas de descobrir uma estratéga vencedora para o primeiro ou o segundo jogador.

Inicialmente, temos os pseudo-jogos, que são jogos em que um jogador sempre ganha não importando o que aconteça durante o jogo.

P-1: Estão escritos num papel, em ordem, todos os inteiros de 1 a 20 (inclusive). Dois jogadores se revezam colocando sinais de [;+;] ou de - entre dois números. Ao final, quando todos os espaços forem preenchidos calcula-se a expressão obtida. Se o resultado for par, o primeiro jogador a jogar vence. Caso contrário, vence o segundo. Há alguma estratégia que garanta a vitória a um dos jogadores?

Resposta: Vamos inicialmente supor que os números estão escritos assim:
[;1+;][;2+ 3+ 4 +5+;][; 6+ 7+ 8+ 9+ 10+ 11;][;+;][; 12+ 13+ 14+ 15+ 16+ 17+ 18+ 19+ 20;]

E supor que cada jogada passa a ser alterar um dos sinais que estão pré-escritos para - ou simplesmente manter como +. (Sendo que se for mantido, o sinal não poderá ser alterado futuramente)

Observe que essa soma é par. Observe também que se a soma é par, se antes de um número par o sinal de + for alterado para um sinal de -, o resultado da expressão continua par. E o mesmo ocorre para números ímpares, assim, não importando o que seja feito, o resultado final será par e o primeiro jogador sempre ganha.


P-2:
Dois jogadores se revezam colocando torres num tabuleiro de xadrez de forma que elas não possam se atacar.O jogador que não conseguir colocar uma torre perde o jogo. Quem vence o jogo?

Resposta: Observe que colocar uma torre reduz em 1 o número de linhas e colunas que pode se colocar uma torre. Assim, só haverá 8 jogadas e o segundo jogador fará a ultima jogada possível.

O.B.S.: De modo geral, num tabuleiro [;n;] x [;n;], se n é par o segundo jogador sempre ganha, caso contrário, o primeiro sempre ganhará.

P-3: Há 2 montes de pedras, 1 com 5 e outro com 10. Dois jogadores se alternam em jogadas que consistem em escolher um dos montes e dividi-los em 2 montes menores. Perde o jogador que não conseguir realizar uma jogada. Qual dos jogadores ganha?

Resposta: O jogo acaba quando tiver 15 montes, cada 1 com 1 pedra. Cada jogada aumenta o número de montes em 1, logo, são realizadas 13 jogadas e o jogador 1 fará a ultima jogada possível.


Observe os problemas abaixo:

P-4: Dois jogadores se revezam colocando moedas de mesmo tamanho numa mesa redonda sem empilha-las, perde o jogador que não puder mais colocar uma moeda na mesa. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

P-5: Dois jogadores se revezam colocando bispos em um tabuleiro de xadrez de forma que eles não ataquem. Perde o jogador que não puder mais colocar bistos no tabuleiro. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

P-6: Há 2 montes de pedra, cada um com 10 pedras. Dois jogadores se revezam efetuando jogadas que consistem em retirar quantas pedras quiser de um dos montes. Perde o jogador que não puder mais realizar uma jogada. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

P-7: Há 2 montes de pedra, um com 10 e outro com 20. Dois jogadores se revezam efetuando jogadas que consistem em retirar quantas pedras quiser de um dos montes (para sua jogada cada jogador tem que tirar pelo menos 1 pedra de 1 dos montes) . Perde o jogador que não puder mais realizar uma jogada. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

Todas são resolvidas usando uma estratégia conhecida como simetria. Após resolver cada uma ficará claro no que consiste a estratégia simétrica.

Resposta da 4: Sim. O primeiro jogador pode ganhar sempre não importando o tamanho da mesa. Para isso, ele deve botar a primeira moeda de forma que o centro da moeda coincida com o centro da circunferência. Feito isso, onde o segundo jogador colocar uma moeda o primeiro coloca no seu simétrico em relação ao centro da circunferência. Fica fácil ver que como ele age sempre simétricamente toda vez que o segundo jogador puder realizar uma jogada o primeiro pode realizar sua jogada. Logo, alguma hora o segundo jogador não poderá jogar.

Resposta da 5: Sim. O segundo jogador pode ganhar sempre. A ideia é bastante parecida com a ideia acima, para isso, ele deve usar como eixo de simetria a reta entre a quarta e a quinta linha do tabuleiro. Observe que como ela divide o tabuleiro ao meio, todas as casas terão uma casa simétrica a reta escolhida. Para garantir sua vitória o segundo jogador deve colocar seu bispo sempre na casa simétria a casa que o primeiro jogador escolheu. Note que essa casa será de cor diferente a casa escolhida pelo primeiro jogador e por isso os bispos não irão se atacar. Assim, o segundo jogador garante que se o primeiro puder jogar, então ele também pode, o que garante a vitória.

Reposta da 6: Sim. O segundo jogador pode sempre vencer. Para isso, se o primeiro jogador tirar X pedras do monte A, então o segundo deve tirar X pedras do monte B. Assim, ele garante que ao final de sua jogada os dois montes tenham a mesma quantidade de pedras. Logo, quando o primeiro jogador acabar as pedras de um dos montes, o segundo acaba com as pedras do outro e o primeiro perde.

Resposta da 7: Sim. O primeiro jogador pode vencer sempre. A estratégia é bastante parecida com a do problema acima. Na primeira jogada do primeiro jogador deve retirar 10 pedras do monte que tem 20 pedras. observe então que ele passa a ser o segundo jogador do problema anterior e por isso deve após a sua primeira jogada seguir a estratégia seguida pelo segundo jogador do problema acima.

Para explicar o próximo método, vamos observar os problemas abaixo.

P-8: Numa caixa há 153 fósforos. Dois jogadores se revezam realizando jogadas que consistem em retirar 1, 2, 3, 4 ou 5 fósforos. Perde o jogador que não puder realizar sua jogada. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

Resposta: Sim, o primeiro jogador pode sempre vencer. Para isso, observe que um jogador ganha se ao final de sua última jogada não tiver nenhum fósforo na caixa. A estratéga então consiste em retirar na primeira jogada 3 palitos da caixa. Então, sobraram 150 palitos e 150 é um múltiplo de 6. Feito isso, se o segundo jogador retirar k palitos, então o primeiro retira [;6-k;] palitos. Assim, ele garante que ao final de todas as suas jogadas e somente ao final de todas as suas jogadas, o número de fósforos na caixa é múltiplo de 6. Como 0 é um múltplo de 6, ele garante a sua vitória sempre.

P-9:
Num tabuleiro de xadrez uma torre está na casa [;a1;]. Dois jogadores se revezam realizando jogadas que coincistem em mover a torre quantas casas quiser na horizontal pra direita ou quantas casas quiser na vertical para cima. Vence o primero jogador que ao final da sua última jogada colocar a torre em [;h8;]. Existe uma estratégia vencedora que garanta a vitória ao primeiro ou segundo jogador? Em caso afirmativo, explicite-a e explique sua eficacia.

Resposta: Sim, o segundo jogador sempre vence. Para isso, se o primeiro jogador mover a torre em X vezes na horizontal pra direita, o segundo deve mover X vezes na vertical pra cima. Se o primeiro mover a torre em X vezes na vertical pra cima, o segundo deve mover em X vezes na horizontal pra direita. Essa estratégia funciona por que o segundo jogador garante que a torre fica na diagonal formada pelas casas [;a1;] e [;h8;] . Como [;h8;] está nessa diagonal, o segundo jogador pode de fato sempre ganhar.


As estratégias usadas nos dois problemas acima consistem em encontrar as chamadas posições vencedoras. Que seriam as posições em que quem se encontrar nelas pode ganhar sempre. Observe algumas coisas importantes sobre posições vencedoras.

1) A posição final é uma posição vencedora. De fato 0 e h8 são as posições finais.


2) Nunca é possível mover de uma posi
ção vencedora para outra posição vencedora. De fato, no problema 8, se subtrairmos 1, 2, 3, 4 ou 5 de um múltiplo de 6 o resultado não será um múltiplo de 6. E no segundo jogo, como não é possível andar na diagonal, sempre que a torre é colocada na diagonal, na rodada seguinte ela é obrigada a sair.

3) Sempre pode-se mover de uma posição não-vencedora para uma posição vencedora. Verifique que isso ocorre nos dois jogos.

Ao obter-se posições vencedoras, e uma estratégia para manter-se sempre nelas, é suficiente afirmar: "como ao final de suas jogadas o jogador A sempre está numa posição vencedora, ele garante sua vitória." e o problema então passaria a ser mostrar que essas posições são de fato posições vencedoras.


Por hoje é só! Não se esqueçam de avaliar a postagem logo abaixo. Se você gostou do blog, recomende aos seus amigos nas redes sociais e se inscreva (por e-mail ou no blog) para receber nossas atualizações.

Até mais!

Nenhum comentário:

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...