Lema: Vamos comecar com seis professores que se correspondem sobre dois assuntos, Fisica e Matematica. Provaremos que entre eles hah 3 que se correspondem sobre o mesmo assunto. Representando os professores por pontos, Matematica por azul e Fisica por vermelho, ligaremos dois ponto em azul quando os dois professores associados a esses pontos se correspondem sobre Matematica, e o mesmo para Fisica, em vermelho. O que queremos provar eh que existe um triangulo cromatico (isto eh, com os tres lados da mesma cor).
Considere o professor A. No grafico, saem dele 5 segmentos. Logo, como soh hah duas cores, no minimo 3 sao da mesma cor, digamos vermelho. Se algum dos segmentos ligando esses tres pontos eh vermelho, a afirmativa estah demonstrada. Caso contrario, todos sao azuis, e provamos a afirmativa.
Agora vamos ao famigerado caso dos 17. Como anteriormente, seja Matemativa azul e Fisica vermelho. Introduzimos Quimica preto. Considere o professor A. No diagrama saem dele 16 segmentos, vermelhos azuis ou pretos. Como soh hah 3 cores, pelo menos 6 devem ter a mesma cor, digamos preto. Se algum dos segmentos ligando esses 6 pontos for preto, provamos o famigerado. Caso contrario, serao todos azuis ou vermelhos, e caimos no lema acima.
Perguntinha: Qual o numero minimo de professores, correspondendo-se sobre quatro assuntos, para formar um triangulo cromatico????? Abracos, olavo.
From: Rogerio Ponce <rogerioponce-obm@xxxxxxxxxxxx>
Reply-To: obm-l@xxxxxxxxxxxxxx
To: obm-l@xxxxxxxxxxxxxx
Subject: [obm-l] 17 professores
Date: Mon, 17 Sep 2007 15:28:13 -0300 (ART)
Ola' pessoal,
numa escola, ha' um grupo de 17 professores que se correspondem de tal forma que quaisquer 2 professores deste grupo trocam ideias sobre exatamente um assunto fixo entre matematica, fisica ou quimica.
Prove que ha' pelo menos 3 professores que se correspondem sobre o mesmo assunto (isto e', a correspondencia entre A e B, B e C, assim como entre A e C sao sobre o mesmo assunto).
[]'s
Rogerio Ponce
PS: nao confundir com "prove que ha' 3 professores que enviam alguma correspondencia sobre um mesmo assunto", que se resolve trivialmente com o "principipo da casa de pombos" (e ja' seria verdadeira para um grupo de 5 professores).
Flickr agora em português. Você clica, todo mundo vê. Saiba mais.