Re: [obm-l] IMO 2007

[Rogerio Ponce <rogerioponce-obm@xxxxxxxxxxxx>]

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.