On Sat, Feb 28, 2004 at 07:51:31PM -0300, Claudio Buffara wrote: > >> 17 matemáticos de todo o mundo trocam correspondência sobre 3 temas. Cada > >> dupla de matemáticos se corresponde sobre um e apenas um tema. Mostre que > >> existem pelo menos 3 matemáticos que se correspondem sobre o mesmo tema. > > > > Este é um clássico. Eu sugiro que você comece com o caso mais fácil: > > > > 6 matemáticos de todo o mundo trocam correspondência sobre 2 temas. Cada > > dupla de matemáticos se corresponde sobre um e apenas um tema. Mostre que > > existem pelo menos 3 matemáticos que se correspondem sobre o mesmo tema. > > > Fixe um matematico (digamos A). Dentre os 16 restantes, existem 6 > (chamemo-los de B1, B2, B3, B4, B5 e B6) que se correspondem com A sobre um > mesmo tema (digamos, tema 1), igual para os 6 (isso eh facil de ver - > aplicacao elementar das casas de pombos). > > Se existirem i e j (1 <= i < j <= 6) tais que Bi e Bj se correspondem sobre > o tema 1, entao acabou: A, Bi e Bj serao tres matematicos que se > correspondem sobre um mesmo tema. > > Caso contrario, use o resultado que o Nicolau mencionou sobre 6 matematicos > (os Bi's) e 2 temas (temas 2 e 3) e conclua que existem i, j e k (1 <= i < j > < k <= 6) tais que Bi, Bj e Bk se correspondem sobre um mesmo tema. > > *** > > Mais dificil eh mostrar que com apenas 16 matematicos, isso (3 matematicos > se correspondendo sobre um mesmo tema) pode nao ocorrer.
O difícil mesmo é o seguinte: N matemáticos de todo o mundo trocam correspondência sobre 4 temas. Cada dupla de matemáticos se corresponde sobre um e apenas um tema. Encontre o menor valor de N para o qual podemos garantir que existam pelo menos 3 matemáticos que se correspondem sobre o mesmo tema. Isto se chama calcular N(3,3,3,3;2) (cada um dos quatro 3s indica que queremos formar uma tripla de matemáticos que se correspondam sobre um dos quatro assuntos; o 2 indica que os matemáticos se correspondem 2 a 2). O Claudio mostrou acima que N(3,3,3;2) <= 17 e propos como problema provar que N(3,3,3;2) = 17. O problema que eu propus é provar que N(3,3;2) <= 6 e não é difícil provar que N(3,3;2) = 6. Aqui http://www.public.iastate.edu/~ricardo/ramsey/monoram.pdf tem um trabalho de 109 páginas de Richard Kramer que prova (ou pelo menos diz que prova, eu não tentei ler) que N(3,3,3,3;2) <= 62. O autor diz na página 2 que é "trivial" provar que N(3,3,3,3;2) <= 66, que é o que nós obtemos generalizando a prova do Claudio. Em 1974, Folkman publicou no Journal of Combinatorial Theory um trabalho em que ele prova que N(3,3,3,3;2) <= 65. A melhor estimativa pelo outro lado parece ser N(3,3,3,3;2) >= 51, de Chung. []s, N. ========================================================================= 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 =========================================================================
