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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 29.02.04 14:36, Nicolau C. Saldanha at nicolau@mat.puc-rio.br wrote:

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

Quanto a esta generalizacao, jah sabemos que:
N(3,3;2) = N(2 x 3;2) <= 6
N(3,3,3;2) = N(3 x 3;2) <= 17
(de fato, nestes dois casos vale a igualdade)

Por um raciocinio analogo, concluimos que:
N((r-1) x 3;2) <= M  ==>  N(r x 3;2) <= r*(M-1) + 2

Demonstracao:
Suponhamos que existam r*(M-1) + 2 matematicos e que cada um deles se
corresponde com cada um dos outros sobre um dentre r temas distintos.

Fixando um matematico (A), eh facil ver que ele se corresponde sobre um dado
tema (digamos, tema 1) com pelo menos M outros matematicos. Se ele se
correspondesse com M-1 ou menos matematicos sobre cada tema, teriamos no
maximo r*(M-1) outros correspondentes, para um total de r*(M-1) + 1 outros
matematicos. Ou seja, A nao se corresponderia com pelo menos um matematico,
contrariamente a hipotese.

Chame os M de B_1, B_2, ..., B_M. Se existem i e j (1 <= i < j <= M) tais
que B_i se corresponde com B_j sobre o tema 1, entao acabou: A, B_i e B_j se
correspondem sobre o tema 1.

Caso contrario, use o fato de que N((r-1) x 3;2) <= M para concluir que
existem i, j e k (1 <= i < j < k <= M) tais que B_i, B_j e B_k se
correspondem sobre um mesmo tema (que pode ser o tema 2, tema 3, ..., ou
tema r).

Adicione 4 gemas de ovo, 1 tablete de manteiga e acucar a gosto -
ingredientes adicionados soh pra ver se alguem leu esta mensagem ateh aqui.

Agora, sabemos que N(3 x 3;2) <= 17. Logo, em virtude do que acabamos de
provar, podemos concluir que N(4 x 3;2) <= 4*(17-1) + 2 = 66, o resultado
"trivial" mencionado por Richard Kramer.

Continuando, obtemos uma sequencia de cotas superiores para N(r x 3;2):
N(5 x 3;2) <= 327;
N(6 x 3;2) <= 1952;
...

> 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.
> 
Serah que ela usou o metodo probabilistico pra obter esta cota inferior?

Um abraco,
Claudio.


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