----- Original Message -----
From: <[EMAIL PROTECTED]> To: "Carlos Shine" <[EMAIL PROTECTED]>; "Celso" <[EMAIL PROTECTED]>; "Edmilson" <[EMAIL PROTECTED]>; "JP" <[EMAIL PROTECTED]>; "Lista de Discussao" <[EMAIL PROTECTED]>; "Ralph" <[EMAIL PROTECTED]>; "Nicolau" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> 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 é <[EMAIL PROTECTED]> =========================================================================