Re: [obm-l] IMO 2007

[Rogerio Ponce <rogerioponce-obm@xxxxxxxxxxxx>]

Ola' Shine, Joao e colegas da lista,
acho que eu poderia melhorar a explicacao, mas vamos la' assim mesmo...

Sempre podemos dividir os competidores da seguinte forma:

Coloque o maior clique na sala "A" e todos os outros na sala "B".
Se na sala "B" tambem houver um clique com o tamanho da sala "A", a divisao esta' completa. Se nao, execute a etapa X.

Etapa X :

Passe um competidor da sala "A" para a sala "B".

Dessa forma, o clique em "A" diminui de 1 unidade, alguns cliques em "B" crescem de 1 unidade, e outros cliques em "B" nao se alteram.

Entao:
- Se o(s) maior(es) clique(s) em "B" ainda nao igualou o clique em "A", repita a etapa "X".

- Se o(s) maior(es) clique(s) em "B" igualou o clique em "A", a divisao esta' completa.

- E se o(s) maior(es) clique(s) em "B" ultrapassou o clique em "A" ?

Bem, em cada um desses cliques (o clique formado pelos migrados de "A" nao esta' entre estes cliques, pois o
 clique original em "A" era par), existe algum competidor que nao estava originalmente em "A" .

Passe esse competidor para "A" (faca isso em todos os cliques de "B" que ultrapassaram o valor em "A").

Agora a divisao esta'  completa.

OBS: Poderia acontecer de todos os jogadores transferidos para "A" formarem um clique independente, superior ao clique em "A" ?

Nao, caso contrario eles ja' estariam formando um clique na sala "B" igual ao clique em "A", antes da ultima passagem de alguem de "A" para "B", e o processo ja' teria terminado.

Note que o clique original em "A" e' par. Assim, todo o processo descrito termina no maximo quando metade dos competidores em "A" tiver sido transferida para "B".


[]'s
Rogerio Ponce



Carlos Yuzo Shine <cyshine@yahoo.com> escreveu:
> 3. Numa
>  competição de matemática, alguns competidores são amigos. Amizade é sempre mútua. Chame um grupo de competidores de clique se quaisquer dois entre eles são amigos. Em particular, qualquer grupo com menos de dois amigos é um clique. O número de membros de um clique é o seu tamanho.
>
> Dado que, nesta competição, o maior tamanho de um clique é par, prove que os competidores podem ser divididos em duas salas tais que o maior tamanho de um clique em uma sala é igual ao maior tamanho de um clique na outra sala.
>
> []'s
> Shine

Alertas do Yahoo! Mail em seu celular. Saiba mais.