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 <[EMAIL PROTECTED]> 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.
