[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] IMO 2007



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.

 

 


-----owner-obm-l@mat.puc-rio.br escreveu: -----

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 .


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