[obm-l] Re: [obm-l] Re: [obm-l] RESSACA NEURÓBICA!

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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
=========================================================================