Conhecidos no jogo de futebol
0 views
Skip to first unread message
Sergio Alvarez
Nov 3, 2009, 8:24:51 PM11/3/09
to matematic...@googlegroups.com
O estádio do Macarenã está lotaaado! 1436973 torcedores indo ao delírio na arquibancada. Na arquibancada, todo mundo é torcedor. Mostre que existem dois torcedores que conhecem o mesmo número de pessoas na arquibancada.
Estou torcendo para você resolver esse!
Estou torcendo para você resolver esse!
Sergio Alvarez
Nov 4, 2009, 8:53:06 PM11/4/09
to matematic...@googlegroups.com
Dica. Você já ouviu falar no Princípio da Casa dos Pombos?
O quê? Não soa familiar? Dê uma olhada nos seguintes problemas:
Divisor de 111...11
Cinco pontos em um quadrado
O quê? Não soa familiar? Dê uma olhada nos seguintes problemas:
Divisor de 111...11
Cinco pontos em um quadrado
2009/11/3 Sergio Alvarez <sergi...@gmail.com>
Sergio Alvarez
Nov 5, 2009, 9:32:39 PM11/5/09
to matematic...@googlegroups.com
Solução. Você já deve ter desconfiado que o número de pessoas no estádio não é realmente importante. Vamos chamar esse número de n (o valor 1436973 não é particularmente útil para a resolução do problema).
A idéia aqui é aplicar o Princípio da Casa dos Pombos. Para isso, imagine n casas de pombo, rotuladas com os números de 0 a n-1. Os torcedores seriam os pombos. Um pombo (digo, um torcedor) vai para a casa k, se ele conhece exatamente k pessoas.
Então, temos n pombos para n casas de pombo. Logo, pelo Princípio da Casa dos Pombos... ops! O número de pombos é igual ao número de casas de pombo. E agora? Não dá para aplicar o princípio da casa dos pombos assim!
Calma, ainda temos uma carta na manga.
Se existir alguém que não conhece ninguém, então não pode existir alguém que conheça todo mundo (sim, assumimos que a relação "A conhece B" seja simétrica). E, reciprocamente, se existir alguém que conhece todo mundo, então não pode existir alguém que não conheça ninguém.
Em outras palavras, a casa 0 e a casa n-1 não podem estar ambas ocupadas. Portanto, apenas n-1 casas são efetivamente utilizadas.
Agora, sim! Temos n pombos para n-1 casas de pombo. Portanto, há dois pombos na mesma casa. Ou seja, há dois torcedores que conhecem o mesmo número de pessoas na arquibancada.
E pensar que isso acontece em todo jogo de futebol...
A idéia aqui é aplicar o Princípio da Casa dos Pombos. Para isso, imagine n casas de pombo, rotuladas com os números de 0 a n-1. Os torcedores seriam os pombos. Um pombo (digo, um torcedor) vai para a casa k, se ele conhece exatamente k pessoas.
Então, temos n pombos para n casas de pombo. Logo, pelo Princípio da Casa dos Pombos... ops! O número de pombos é igual ao número de casas de pombo. E agora? Não dá para aplicar o princípio da casa dos pombos assim!
Calma, ainda temos uma carta na manga.
Se existir alguém que não conhece ninguém, então não pode existir alguém que conheça todo mundo (sim, assumimos que a relação "A conhece B" seja simétrica). E, reciprocamente, se existir alguém que conhece todo mundo, então não pode existir alguém que não conheça ninguém.
Em outras palavras, a casa 0 e a casa n-1 não podem estar ambas ocupadas. Portanto, apenas n-1 casas são efetivamente utilizadas.
Agora, sim! Temos n pombos para n-1 casas de pombo. Portanto, há dois pombos na mesma casa. Ou seja, há dois torcedores que conhecem o mesmo número de pessoas na arquibancada.
E pensar que isso acontece em todo jogo de futebol...
2009/11/4 Sergio Alvarez <sergi...@gmail.com>
Cristiano Santos Benjamin
Nov 4, 2009, 12:42:49 AM11/4/09
to Matemática Radical
Não importa o número de pessoas que está no estádio. Sempre haverá
duas pessoas que conhecem o mesmo número de pessoas.
Suponhamos que existam n pessoas. Escolhendo uma pessoa qualquer
podemos ver que há n possibilidades para o número de conhecidos dessa
pessoa, ou seja, ela pode não conhecer ninguém(E1), pode conhecer
apenas uma pessoa(E2), ..., ou pode conhecer n-1 pessoas(En). A
princípio podemos pensar: eu tenho n possibilidades para o número de
conhecidos e tenho n pessoas, então há como cada uma delas conhecerem
um número diferente de pessoas. Mas observe que não há como ocorrer E1
e En ao mesmo tempo. E1 é quando a pessoa não conhece ninguém e En é
quando a pessoa conhece todo mundo. Se E1 acontece com uma pessoa p
então significa que p não conhece ninguém. Então não haverá ninguém
que conhece p, logo ninguém conhecerá todo mundo e o evento En não
ocorrerá. Ou seja, apesar de termos n eventos distintos descobrimos
que não pode ocorrer os n eventos ao mesmo tempo. Logo poderá ocorrer
no máximo n-1 eventos para n pessoas e consequentemente haverá pelo o
menos duas pessoas com o mesmo envento, ou seja, conhece o mesmo
número de pessoas.
duas pessoas que conhecem o mesmo número de pessoas.
Suponhamos que existam n pessoas. Escolhendo uma pessoa qualquer
podemos ver que há n possibilidades para o número de conhecidos dessa
pessoa, ou seja, ela pode não conhecer ninguém(E1), pode conhecer
apenas uma pessoa(E2), ..., ou pode conhecer n-1 pessoas(En). A
princípio podemos pensar: eu tenho n possibilidades para o número de
conhecidos e tenho n pessoas, então há como cada uma delas conhecerem
um número diferente de pessoas. Mas observe que não há como ocorrer E1
e En ao mesmo tempo. E1 é quando a pessoa não conhece ninguém e En é
quando a pessoa conhece todo mundo. Se E1 acontece com uma pessoa p
então significa que p não conhece ninguém. Então não haverá ninguém
que conhece p, logo ninguém conhecerá todo mundo e o evento En não
ocorrerá. Ou seja, apesar de termos n eventos distintos descobrimos
que não pode ocorrer os n eventos ao mesmo tempo. Logo poderá ocorrer
no máximo n-1 eventos para n pessoas e consequentemente haverá pelo o
menos duas pessoas com o mesmo envento, ou seja, conhece o mesmo
número de pessoas.
Reply all
Reply to author
Forward
0 new messages