on 29.02.04 14:36, Nicolau C. Saldanha at [EMAIL PROTECTED] 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 =========================================================================
