Alguém, por gentileza, comente o surto abaixo. Ponce, preliminarmente, creio que está correto. Vou olhar com maior atenção.
O surto:
Vamos busca modelar (como se modela argila) esse conjunto competição.
Não estou brincando não, falo sério.
Cada conjunto clique desse é um monte de argila. Existe um conjunto maior com 2n elementos.
Esses conjuntos de barro podem estar unidos. Essas uniões são as amizades que ligam os conjuntos clique sem transformá-los num conjunto clique maior. Também podem existir montes sem ligação com nenhum outro.
Ora, sempre é possível dividir todo o conjunto competição, de forma que o maior conjunto clique com 2n participantes seja divido ao meio e os demais também ao meio (se par) ou em dois números inteiros e consecutivos (se ímpares) e, sem tanta preocupação com as amizades inter-cliques, pois elas não aumentam o tamanho de cada conjunto. Assim, sempre será possível se ter aí o que se deseja provar.
Falta precisão, claro, mais essa pode ser simples a partir da idéia acima, creio.
Fraternalmente, João.
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.