on 24.02.04 21:28, Nicolau C. Saldanha at [EMAIL PROTECTED] wrote: > On Tue, Feb 24, 2004 at 09:01:41PM -0300, [EMAIL PROTECTED] 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. > > O problema que você propôs é parecido só que maior, se você entende > o que eu quero dizer. > > []s, N. > 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. 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 =========================================================================