Re:[obm-l] lutas...

["Pedro Cardoso" <pedrolazera@xxxxxxxxxxx>]

Bem, eu acho que ficou assim...

Uma coisa que ajuda: o número mínimo de lutas ocorre quando um dado 
competidor não perde nenhuma disputa e todos os outros perdem duas. Seriam 0 
+ 2.199 = 398 derrotas = 398 disputas. O número mínimo de disputas então é 
398. Se todos os competidores já tiverem uma derrota, necessariamente 
teremos mais do que 398 lutas, necessariamente teremos 399 lutas.

Se entre duas lutas consecutivas de um mesmo competidor devem ocorrer lutas 
envolvendo outros dois competidores, ainda podemos ter as primeiras 200 
lutas. As lutas poderiam ser arranjadas assim:

(vencedor x perdedor)

001 002
003 004
005 006
... ...
199 200
------- (agora os pares ganham)
002 003
004 005
... ...
198 199
200 001

Bem, todos já têm uma derrota. Seria impossível termos 398 lutas, o que 
tornaria obrigatório termos 399 lutas. A questão é que, se um competidor não 
pode disputar duas lutas seguidas, não teremos um vencedor.

Suponha que a_n, a_p e a_k sobrem, cada um com uma derrota (essa 
configuração é obrigatória para que haja 399 lutas). Quaisquer que sejam os 
dois escolhidos para lutar, o vencedor dessa penúltima luta não poderá lutar 
novamente, porque entre as duas lutas dele deve ocorrer ao menos uma luta 
envolvendo ao menos outros dois compeditores. Não temos outros dois 
competidores.

a_n vence a_k. Sobram a_n e a_p, mas a_n não pode lutar duas vezes seguidas. 
Ficam os dois, cada um com uma derrota, impedidos de lutar.

_________________________________________________________________
Chegou o Windows Live Spaces com rede social. Confira 
http://spaces.live.com/

=========================================================================
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
=========================================================================