[obm-l] Re: IMO 2007 (agora vai)

[Rogerio Ponce <rogerioponce-obm@xxxxxxxxxxxx>]

Ola' Joao,
nao foi pouco caso: ja' e' a 4a vez que mando esta mensagem, e, ate' agora, neca de pitibiriba - parece que o servidor da lista encruou...

Mas, voltando 'a vaca fria, quero assinalar que tentar resolver certos problemas usando analogias pode ser ingrato porque frequentemente voce acaba destruindo (estabelecendo) vinculos e/ou mecanismos  (nao) existentes no problema original.

Veja que com a historia do barro, voce deixou escapar que os pedacos "retalhados", quando estao na mesma sala, NAO permanecem inertes e "retalhados". Este e' o comportamento do barro, mas nao e' o que acontece com os cliques, que se reagrupam automaticamente.

Assim, por mais sem graca que pareca, experimente usar uma vezinha so' os numeros que estou sugerindo, e verifique o que acontece em cada passo.

Consideremos a seguinte situacao:

Competidores 1,2,3,4,5,6,7,8,9,10,11,12,13

Cliques existentes:
1,2,3,4
5, 6, 7
8, 9, 10
11, 12,
 13
5, 7, 9
5, 7, 11
5, 8, 9
5, 8, 11
5, 9, 12
6, 7, 10
7, 9, 10
7, 11, 13

Agora, vamos seguir o seu proprio raciocinio, usando as salas A e B:

- separar  o clique maximo integralmente: {1,2,3,4}

- dividi-lo ao meio: {1,2}->A e  {3,4}->B

-dividir montes menores em 2 partes proximas da metade (vamos percorrer a lista de cliques, obtendo o seguinte):

{5,6,7}:  {5,6}->A  e  {7}->B

{8,9,10}:  {8,9}->A  e  {10}->B

{11, 12, 13}:  {11,12}->A  e  {13}->B


Opa! neste ponto aparece um problema: o que fazer com o clique {5,7,9}?

Ele faz parte do grupo "cliques existentes", e voce recomenda uma acao de divisao sobre este clique...so' que voce ja' havia dado destino a cada um dos elementos. E entao, como fica o algoritmo? Vou supor que ele termine aqui.

Mas ha' um outro problema pior, pois as salas A e B estao com
 a seguinte distribuicao de competidores:
 A={1,2,5,6,8,9,11,12}  e  B={3,4,7,10,13}

Repare que o clique {1,2,3,4} deu lugar a 2 cliques com tamanho 2 ({1,2} e {3,4}), mas voce reagrupou dois cliques (5,8,9 por exemplo) com tamanho 3 em A, enquanto em B, nenhum clique tem mais que 2 elementos.

Assim, por enquanto, esta forma de dividir esta' mostrando o contrario do que queremos provar.

E a pergunta principal e' : como e' que voce garante que nao vai haver algum reagrupamento maior que a metade do maior clique inicial?

Bem, ao final de tudo, qualquer que seja o algoritmo que voce encontre, ele tem que funcionar como prova (conforme o enunciado) e nao como algo que talvez funcione. Significa que, seguindo a logica que voce explicitar, deve ficar muito claro, em todas as transferencias de pessoas, o que aumenta e o que diminui, de forma a mostrar que e' sempre possivel fazer a divisao dos competidores em 2 salas com clique maximo
 de mesmo tamanho.

Vamos la', Joao !

[]'s
Rogerio Ponce

------------------------------------------
JoaoCarlos_Junior escreveu:

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.


------------------------------------------
Rogerio Ponce escreveu:

 
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


------------------------------------------
JoaoCarlos_Junior escreveu:

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.

Flickr agora em português. Você cria, todo mundo vê. Saiba mais.