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.
