Re: [obm-l] Algumas da Iberoamericana.SEGUNDO PROBLEMA PARA A LISTA

["Eduardo Azevedo" <eduardo_az@xxxxxxxxxxxxx>]

----- Original Message -----



From: <peterdirichlet@zipmail.com.br>
To: "Carlos Shine" <cyshine@yahoo.com>; "Celso"
<peterdirichlet@zipmail.com.br>; "Edmilson" <edmilson@abeunet.com.br>; "JP"
<jpqc@uninet.com.br>; "Lista de Discussao" <obm-l@mat.puc-rio.br>; "Ralph"
<ralph@fgv.br>; "Nicolau" <nicolau@mat.puc-rio.br>; <tengan@sailormoon.com>
Sent: Tuesday, April 30, 2002 5:07 PM
Subject: [obm-l] Algumas da Iberoamericana.SEGUNDO PROBLEMA PARA A LISTA


> Ah.turma,to com a prova da Iberoamericana aquoi na mao,e tenho problemas
> serios neles.Ai vai!!!
> 1.Temos 98 pontos sobre uma circunferencia.Maria e Jose fazem um jogo
assim:cada
> um deles traça uma corda ligando dois dos pontos dados que nao tenham sido
> ligados entre si antes.O jogo acaba quandoos 98 pontos forem usados como
> extremos de segmentos pelo menos 1 vez.Quem fizer o ultimo traço
ganha.Defina
> uma estrategia vencedora se ela existir.

O primeiro jogador, jogando certo, sempre vence. Isso vale para qualquer n =
2 (mod 4)

Seja k o número de pontos não ligados a ninguém, j o número de jogadas ja
feitas e n=98 o número de pontos.

Em cada jogada pode-se ligar dois pontos livres, fazendo k diminuir 2, ligar
um livre e um marcado, fazendo k baixar 1, ou ligar dois pontos marcados,
mantendo o mesmo k. Chamemos isso de enrolada. Seja "e" o número de opções
de enrolada num dado cenário

É fácil ver que em qualquer momento do jogo

e = (n-k)(n-k-1)/2 - j

Numa dada jogada, o jogador com "e" ímpar está em vantagem, pois pode
enrolar o quanto quiser, até o jogador com "e" par ficar sem opções de
enrolação, e ser forcado a jogar.

Agora,
(n-k)(n-k-1)/2 é par se e somente se (n-k)(n-k-1) = 0 ou seja:

(n-k)(n-k-1)/2 é par se e somente se k = n (mod 4) ou k = n+1 (mod 4)

Ja j é par para o jogador A e ímpar para o jogador B.

Logo, para o jogador B, temos:
e par quando k= n ou n+1 (mod 4)

Para A:
e par quando k= n+2 ou n+3 (mod 4)

Isso mostra que  a paridade de e depende apenas de k, e é alternada para
cada jogador. Ou seja, a abilidade de um jogador de forcar uma jogada
depende apenas de k.

Agora vejamos algumas situações de vitória:

Se k = 1 ou k = 2, quem tiver a vez ganha.

Se k=3, comer mais uma peca significa a derrota, pois leva o adversário ao
cenário acima. Assim, quando k é igual a 3 é necessário enrolar.
Mas como 3 = 99 = n+1 (mod 4), o jogador A tem "e" ímpar em 3, e B tem "e"
par. Portanto, A sempre pode enrolar, enquanto B será eventualmente forçado
a jogar. Logo se k=3, o jogador A sempre ganha.

Portanto A precisa apenas garantir que o jogo caia em k =3 e ganhará sempre.

Se fosse n=3 (mod 4), A continuaria podendo ganhar sempre.
Se fosse n=+-1(mod4), B poderia ganhar sempre, exceto se n=5, onde A pode
ganhar sempre.

Esse jogo não parece muito justo .....


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================