Se a amizade não existia no conjunto competição, então, ela não passará a existir nas salas.
Uma amizade é restabelecida se os recíprocos amigos forem inclusos na mesma sala, mesmo que em momentos distintos.
Sim de fato, a amizade somente ficará quebrada (cortada, como queira) somente se os amigos estiverem nas salas distintas.
Podemos continuar a escrever algo (que, a meu ver, está cada vez mais próximo de uma resposta integralmente satisfatória) na linguagem da própria pergunta, porém, devemos ser agradecidos com o êxtase - princípio do auxílio ? que nos conduziu ou quer nos conduzir à resposta, por analogia. Prefiro a segunda à primeira. Permita-me, assim, expressar-me. Passar da linguagem em analogia à do próprio problema me não parece difícil. Então:
1) Da massa de argila (toda a competição), podemos separar dela o conjunto clique máximo integralmente. Empós, dividimo-lo no meio, jogando cada metade em duas mesas distintas (as salas).
2) Os montes menores também devem ser divididos em duas partes, de forma que cada uma dessas partes cliques sejam de tamanho menor que as metades acima (no máximo, há uma igualdade, não é difícil verificar). Percebamos que se havia anteriormente amizade entre os elementos desses conjuntos menores entre eles próprios e deles para com os elementos do conjunto maior, as amizades ficarão restabelecidas entre os elementos que já eram previamente amigos, porém, agora, só para aqueles que estão na mesma sala. Esses restabelecimentos, no entanto, não aumentam os tamanhos dos conjuntos cliques cortados.
3) depois a massa que sobrou você pode cortá-la ou não (como queira), jogando-a integralmente em uma só sala, ou retalhá-la a gosto, lançando as partes em ambas as salas, sob qualquer critério.
Com sinceridade, sem o menor grau de sofisma: agrado tuas contraposições, Ponce, que me impeliram à frente nessa resolução. Se ainda houver alguma(s), por gentileza principalmente a mim, manifeste-a(s).
Desculpe-me não ter respondido logo. Obrigado.
Fraternalmente, João.
Para: obm-l@mat.puc-rio.br
De: Rogerio Ponce <rogerioponce-obm@yahoo.com.br>
Enviado por: owner-obm-l@mat.puc-rio.br
Data: 28/07/2007 4:09
Assunto: Re: [obm-l] IMO 2007
Ola' Joao,
suponha a competicao com os competidores numerados de 1 a 13, formando os seguintes cliques:
1, 2, 3, 4
5, 6, 7
8, 9, 10
11, 12, 13
5, 8, 9
5, 8, 11
5, 9, 12
6, 7, 10
7, 9, 10
7, 11, 13
Repare que nao da' para pensarmos em dividir cada conjunto ao meio (ou proximo do meio) de forma independente, pois eles nao sao obrigatoriamente disjuntos. Entao, quando voce faz a divisao de um clique, muitas vezes tambem estara separando (ou agrupando) outro clique.
Assim, embora o maior clique tenha inicialmente "2n" elementos , nao e' verdade que a sua forma de dividi-los va' produzir cliques com no maximo "n" elementos (embora essa seja a nossa primeira impressao).
Seguindo sua sugestao, poderiamos separar os competidores assim:
[1, 2] na sala "A" , [3, 4] na sala "B"
[5, 6] na sala "A" , [7] na sala "B"
[8, 9] na sala "A" , [10] na sala "B"
[11, 12] na sala "A" , [13] na sala "B"
Parariamos a divisao neste ponto, uma vez que ja' teriamos dado destino a todos os competidores.
Entretanto, na sala "A" existe um clique (5,8,11) com 3 competidores , enquanto os maiores cliques da sala "B" nao passam de 2 competidores.
Acho que este exemplo serve de partida para voce elaborar o que pode acontecer durante qualquer outra forma de divisao.
[]'s
Rogerio Ponce
------------------------------------------
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.
Alertas do Yahoo! Mail em seu celular. Saiba mais .