Reunião na mesa redonda
123 views
Skip to first unread message
Sergio Alvarez
Oct 14, 2009, 10:54:07 AM10/14/09
to matematic...@googlegroups.com
25 garotos e 25 garotas sentam-se em torno de uma mesa. Prove que é sempre possível encontrar uma pessoa cujos vizinhos são ambos garotas.
Parece muito fácil? Tente a escrever a solução! Vale a pena.
Esse aqui eu tirei de um dos livros do Titu:
102 Combinatorial Problems
Parece muito fácil? Tente a escrever a solução! Vale a pena.
Esse aqui eu tirei de um dos livros do Titu:
102 Combinatorial Problems
Sergio Alvarez
Oct 15, 2009, 8:42:09 AM10/15/09
to matematic...@googlegroups.com
Dica: A disposição cíclica das pessoas em torno da mesa e o fato de o número 25 ser ímpar têm um papel fundamental neste problema.
2009/10/14 Sergio Alvarez <sergi...@gmail.com>
Sergio Alvarez
Oct 16, 2009, 12:40:24 PM10/16/09
to matematic...@googlegroups.com
Falha nossa!
Não é o fato do número 25 ser ímpar que importa nesse problema, mas o fato de que o número de garotas é igual ao número de garotos.
Então, a dica seria:
A disposição cíclica das pessoas em torno da mesa e o fato de o número de garotos ser igual ao número de garotas têm um papel fundamental neste problema.
Agora, sim!
Não é o fato do número 25 ser ímpar que importa nesse problema, mas o fato de que o número de garotas é igual ao número de garotos.
Então, a dica seria:
A disposição cíclica das pessoas em torno da mesa e o fato de o número de garotos ser igual ao número de garotas têm um papel fundamental neste problema.
Agora, sim!
2009/10/15 Sergio Alvarez <sergi...@gmail.com>
Sergio Alvarez
Oct 16, 2009, 1:02:28 PM10/16/09
to matematic...@googlegroups.com
Hmm... tudo bem, vamos incrementar um pouco a dica. Há várias maneiras de se resolver esse problema. No livro do Titu "102 Combinatorial Problems", há duas soluções.
Eu ainda fiz uma terceira solução que é linda! Vou começar dando uma pista de como ela é: defina a "popularidade" de cada pessoa ao redor da mesa como sendo o número de vizinhos dessa pessoa que são garotas.
Então, popularidade = 0 significa que ambos os vizinhos da pessoa são garotos, popularidade = 1 significa que um dos vizinhos é um garoto e o outro é uma garota, e popularidade = 2 (adivinha!) significa que ambos os vizinhos são garotas.
E o que você faz com isso? Experimente examinar a soma das popularidades...
Eu ainda fiz uma terceira solução que é linda! Vou começar dando uma pista de como ela é: defina a "popularidade" de cada pessoa ao redor da mesa como sendo o número de vizinhos dessa pessoa que são garotas.
Então, popularidade = 0 significa que ambos os vizinhos da pessoa são garotos, popularidade = 1 significa que um dos vizinhos é um garoto e o outro é uma garota, e popularidade = 2 (adivinha!) significa que ambos os vizinhos são garotas.
E o que você faz com isso? Experimente examinar a soma das popularidades...
2009/10/16 Sergio Alvarez <sergi...@gmail.com>
Message has been deleted
Sergio Alvarez
Oct 17, 2009, 2:13:18 PM10/17/09
to matematic...@googlegroups.com
Galera, eu fiz uma pequena confusão. O fato de o número 25 ser ímpar é realmente importante neste problema. Por exemplo, é possível dispor 4 garotas e 4 garotos em torno de uma mesa sem que ninguém tenha ambos os vizinhos sendo garotas: basta alternar pares de garotos com pares de garotas.
Naturalmente, isso funciona não só com o número 4, mas com qualquer número par.
Naturalmente, isso funciona não só com o número 4, mas com qualquer número par.
2009/10/16 Sergio Alvarez <sergi...@gmail.com>
Sergio Alvarez
Oct 17, 2009, 5:35:32 PM10/17/09
to matematic...@googlegroups.com
Vamos começar a escrever a solução.
Defina a popularidade de cada indivíduo em torno da mesa como explicado na dica.
A soma das popularidades é o dobro do número de garotas.
Por quê? Um argumento simples de contagem dupla.
Faça uma tabela com as linhas indexadas pelas pessoas em torno da mesa e com as colunas indexadas pelas garotas. Marque a célula (i,j) da tabela se o indivíduo i é vizinho da garota j.
O número de células marcadas em cada linha é a popularidade do indivíduo correspondente àquela linha. Então, a soma das popularidades é o número total de células marcadas.
Por outro lado, em cada coluna há exatamente duas células marcadas, pois cada garota tem exatamente dois vizinhos (uma vez que as pessoas estão dispostas ciclicamente em torno da mesa). Então, o número de células marcadas na tabela é o dobro do número de colunas, ou seja, o dobro do número de garotas.
Portanto, contando o número de células marcadas na tabela de dois modos, concluímos que a soma das popularidades é o dobro do número de garotas.
Como há 25 garotas, a soma das popularidades vale 50.
Certo, e daí?
Queremos mostrar que, independentemente da disposição das pessoas em torno da mesa, se há 25 garotas e 25 garotos, então alguém está rodeado de garotas (popularidade = 2).
Roteiro para completar a solução:
Suponha que isso não aconteça, isto é, que cada indivíduo seja vizinho de no máximo uma garota.
Conclua que cada pessoa tem um vizinho que é uma garota e outro que é um garoto.
Separe os garotos em duas classes: A e B.
Um garoto está na classe A, se o seu vizinho da esquerda é um garoto.
Um garoto está na classe B, se o seu vizinho da direita é um garoto.
Mostre que as classes A e B têm o mesmo número n de elementos.
Conclua que 2n = 25.
Observe que isso é impossível e conclua que alguém é vizinho de duas garotas.
2009/10/17 Sergio Alvarez <sergi...@gmail.com>
Defina a popularidade de cada indivíduo em torno da mesa como explicado na dica.
A soma das popularidades é o dobro do número de garotas.
Por quê? Um argumento simples de contagem dupla.
Faça uma tabela com as linhas indexadas pelas pessoas em torno da mesa e com as colunas indexadas pelas garotas. Marque a célula (i,j) da tabela se o indivíduo i é vizinho da garota j.
O número de células marcadas em cada linha é a popularidade do indivíduo correspondente àquela linha. Então, a soma das popularidades é o número total de células marcadas.
Por outro lado, em cada coluna há exatamente duas células marcadas, pois cada garota tem exatamente dois vizinhos (uma vez que as pessoas estão dispostas ciclicamente em torno da mesa). Então, o número de células marcadas na tabela é o dobro do número de colunas, ou seja, o dobro do número de garotas.
Portanto, contando o número de células marcadas na tabela de dois modos, concluímos que a soma das popularidades é o dobro do número de garotas.
Como há 25 garotas, a soma das popularidades vale 50.
Certo, e daí?
Queremos mostrar que, independentemente da disposição das pessoas em torno da mesa, se há 25 garotas e 25 garotos, então alguém está rodeado de garotas (popularidade = 2).
Roteiro para completar a solução:
Suponha que isso não aconteça, isto é, que cada indivíduo seja vizinho de no máximo uma garota.
Conclua que cada pessoa tem um vizinho que é uma garota e outro que é um garoto.
Separe os garotos em duas classes: A e B.
Um garoto está na classe A, se o seu vizinho da esquerda é um garoto.
Um garoto está na classe B, se o seu vizinho da direita é um garoto.
Mostre que as classes A e B têm o mesmo número n de elementos.
Conclua que 2n = 25.
Observe que isso é impossível e conclua que alguém é vizinho de duas garotas.
2009/10/17 Sergio Alvarez <sergi...@gmail.com>
Cristiano Santos Benjamin
Oct 18, 2009, 8:31:56 PM10/18/09
to Matemática Radical
Bom pessoal. Não tive coragem de tentar arrumar um prova diferente da
que Sergio trouxe pra nós. Mas pensei aqui como seria a melhor
arrumação para que e evento onde temos uma pessoa com duas vizinhas
ocorresse o menor número possível de vezes.
Vamos tentar fazer a arrumação de modo em que não haja uma pessoa cujo
os dois vizinhos sejam garotas. Quando eu me referir a uma pessoa cujo
os dois vizinhos sejam garotas falarei apenas uma “cadeira com duas
vizinhas”.
Vamos enumerar as cadeiras no sentido horário de 1 a 50 e vamos
colocar uma garota sentada na cadeira 1. Vamos colocar uma garota
sentada na cadeira 2(I). A cadeira 3 terá que ser ocupada por um
garoto, pois se não a cadeira dois teria duas vizinhas. A cadeira 4
pelo mesmo motivo anterior terá que ser ocupada por um garoto. Até o
momento temos 23 garotos e 23 garotas em pé. Poderíamos ocupar as
próximas 23 cadeiras de garotos que não teríamos problemas. Mas aí
teríamos outras 23 cadeiras ocupada por garotas e isso não serve pra
nós. O mais interessante seria ocupar a cadeira 5 por uma garota e
repetir o ciclo(II) das 4 primeiras cadeira. Então teríamos a cadeira
4n ocupada por um garoto e teríamos 25-2n garotos e 25-2n garotas em
pé. O número máximo para n é 12 e nesse caso teríamos duas cadeiras
vizinhas para ser ocupadas. A cadeira 50 tem que ser ocupada por um
garoto, pois se não a pessoa da cadeira 1 teria duas vizinhas e só
restaria a cadeira 49 para ser ocupada por uma garota e a cadeira 50
teria duas vizinhas.
(I) Observe que se ocupássemos a cadeira 2 por um garoto teríamos a
mesma arrumação só que rotacionada de uma unidade no sentido anti-
horário.
Generalizando o problema:
Vamos considerar o caso geral onde temos x garotos e y garotas e uma
mesa redonda com k=x+y cadeiras. É interessante observar que se y>x
não há como não ter uma cadeira com duas vizinhas. Se x>y sempre terá
como arrumar de modo que nenhuma cadeira tenha duas vizinhas. Se
x=y=t, a arrumação acima será a melhor arrumação de modo que o número
de cadeiras j que tem duas vizinhas seja o menor possível. Se t for
par j=0 e se t for ímpar j=1. Note que se t for par então k vai ser
divisível por 4 e teremos k /4 ciclos(II) na nossa arrumação. Se t for
ímpar teremos k=4p+2 e aí teríamos p ciclos e sobraria 2 cadeiras pra
ser ocupadas por um garoto e uma garota onde haveria uma cadeira com
duas vizinhas.
Me corrijam se eu me equivoquei em alguma parte
> 2009/10/17 Sergio Alvarez <sergio1...@gmail.com>
>
> - Show quoted text -
que Sergio trouxe pra nós. Mas pensei aqui como seria a melhor
arrumação para que e evento onde temos uma pessoa com duas vizinhas
ocorresse o menor número possível de vezes.
Vamos tentar fazer a arrumação de modo em que não haja uma pessoa cujo
os dois vizinhos sejam garotas. Quando eu me referir a uma pessoa cujo
os dois vizinhos sejam garotas falarei apenas uma “cadeira com duas
vizinhas”.
Vamos enumerar as cadeiras no sentido horário de 1 a 50 e vamos
colocar uma garota sentada na cadeira 1. Vamos colocar uma garota
sentada na cadeira 2(I). A cadeira 3 terá que ser ocupada por um
garoto, pois se não a cadeira dois teria duas vizinhas. A cadeira 4
pelo mesmo motivo anterior terá que ser ocupada por um garoto. Até o
momento temos 23 garotos e 23 garotas em pé. Poderíamos ocupar as
próximas 23 cadeiras de garotos que não teríamos problemas. Mas aí
teríamos outras 23 cadeiras ocupada por garotas e isso não serve pra
nós. O mais interessante seria ocupar a cadeira 5 por uma garota e
repetir o ciclo(II) das 4 primeiras cadeira. Então teríamos a cadeira
4n ocupada por um garoto e teríamos 25-2n garotos e 25-2n garotas em
pé. O número máximo para n é 12 e nesse caso teríamos duas cadeiras
vizinhas para ser ocupadas. A cadeira 50 tem que ser ocupada por um
garoto, pois se não a pessoa da cadeira 1 teria duas vizinhas e só
restaria a cadeira 49 para ser ocupada por uma garota e a cadeira 50
teria duas vizinhas.
(I) Observe que se ocupássemos a cadeira 2 por um garoto teríamos a
mesma arrumação só que rotacionada de uma unidade no sentido anti-
horário.
Generalizando o problema:
Vamos considerar o caso geral onde temos x garotos e y garotas e uma
mesa redonda com k=x+y cadeiras. É interessante observar que se y>x
não há como não ter uma cadeira com duas vizinhas. Se x>y sempre terá
como arrumar de modo que nenhuma cadeira tenha duas vizinhas. Se
x=y=t, a arrumação acima será a melhor arrumação de modo que o número
de cadeiras j que tem duas vizinhas seja o menor possível. Se t for
par j=0 e se t for ímpar j=1. Note que se t for par então k vai ser
divisível por 4 e teremos k /4 ciclos(II) na nossa arrumação. Se t for
ímpar teremos k=4p+2 e aí teríamos p ciclos e sobraria 2 cadeiras pra
ser ocupadas por um garoto e uma garota onde haveria uma cadeira com
duas vizinhas.
Me corrijam se eu me equivoquei em alguma parte
>
>
>
> > Galera, eu fiz uma pequena confusão. O fato de o número 25 ser ímpar é
> > realmente importante neste problema. Por exemplo, é possível dispor 4
> > garotas e 4 garotos em torno de uma mesa sem que ninguém tenha ambos os
> > vizinhos sendo garotas: basta alternar pares de garotos com pares de
> > garotas.
>
> > Naturalmente, isso funciona não só com o número 4, mas com qualquer número
> > par.
>
> > 2009/10/16 Sergio Alvarez <sergio1...@gmail.com>
>
>
> > Galera, eu fiz uma pequena confusão. O fato de o número 25 ser ímpar é
> > realmente importante neste problema. Por exemplo, é possível dispor 4
> > garotas e 4 garotos em torno de uma mesa sem que ninguém tenha ambos os
> > vizinhos sendo garotas: basta alternar pares de garotos com pares de
> > garotas.
>
> > Naturalmente, isso funciona não só com o número 4, mas com qualquer número
> > par.
>
>
> >> Hmm... tudo bem, vamos incrementar um pouco a dica. Há várias maneiras de
> >> se resolver esse problema. No livro do Titu "102 Combinatorial Problems", há
> >> duas soluções.
>
> >> Eu ainda fiz uma terceira solução que é linda! Vou começar dando uma pista
> >> de como ela é: defina a "popularidade" de cada pessoa ao redor da mesa como
> >> sendo o número de vizinhos dessa pessoa que são garotas.
>
> >> Então, popularidade = 0 significa que ambos os vizinhos da pessoa são
> >> garotos, popularidade = 1 significa que um dos vizinhos é um garoto e o
> >> outro é uma garota, e popularidade = 2 (adivinha!) significa que ambos os
> >> vizinhos são garotas.
>
> >> E o que você faz com isso? Experimente examinar a soma das
> >> popularidades...
>
> >> 2009/10/16 Sergio Alvarez <sergio1...@gmail.com>
> >> Hmm... tudo bem, vamos incrementar um pouco a dica. Há várias maneiras de
> >> se resolver esse problema. No livro do Titu "102 Combinatorial Problems", há
> >> duas soluções.
>
> >> Eu ainda fiz uma terceira solução que é linda! Vou começar dando uma pista
> >> de como ela é: defina a "popularidade" de cada pessoa ao redor da mesa como
> >> sendo o número de vizinhos dessa pessoa que são garotas.
>
> >> Então, popularidade = 0 significa que ambos os vizinhos da pessoa são
> >> garotos, popularidade = 1 significa que um dos vizinhos é um garoto e o
> >> outro é uma garota, e popularidade = 2 (adivinha!) significa que ambos os
> >> vizinhos são garotas.
>
> >> E o que você faz com isso? Experimente examinar a soma das
> >> popularidades...
>
>
> >> Falha nossa!
>
> >>> Não é o fato do número 25 ser ímpar que importa nesse problema, mas o
> >>> fato de que o número de garotas é igual ao número de garotos.
>
> >>> Então, a dica seria:
>
> >>> A disposição cíclica das pessoas em torno da mesa e o fato de o número de
> >>> garotos ser igual ao número de garotas têm um papel fundamental neste
> >>> problema.
>
> >>> Agora, sim!
>
> >>> 2009/10/15 Sergio Alvarez <sergio1...@gmail.com>
> >> Falha nossa!
>
> >>> Não é o fato do número 25 ser ímpar que importa nesse problema, mas o
> >>> fato de que o número de garotas é igual ao número de garotos.
>
> >>> Então, a dica seria:
>
> >>> A disposição cíclica das pessoas em torno da mesa e o fato de o número de
> >>> garotos ser igual ao número de garotas têm um papel fundamental neste
> >>> problema.
>
> >>> Agora, sim!
>
>
> >>> Dica: A disposição cíclica das pessoas em torno da mesa e o fato de o
> >>>> número 25 ser ímpar têm um papel fundamental neste problema.
>
> >>>> 2009/10/14 Sergio Alvarez <sergio1...@gmail.com>
> >>> Dica: A disposição cíclica das pessoas em torno da mesa e o fato de o
> >>>> número 25 ser ímpar têm um papel fundamental neste problema.
>
>
> >>>> 25 garotos e 25 garotas sentam-se em torno de uma mesa. Prove que é
> >>>>> sempre possível encontrar uma pessoa cujos vizinhos são ambos garotas.
>
> >>>>> Parece muito fácil? Tente a escrever a solução! Vale a pena.
>
> >>>>> Esse aqui eu tirei de um dos livros do Titu:
> >>>>> 102 Combinatorial Problems- Hide quoted text -
> >>>> 25 garotos e 25 garotas sentam-se em torno de uma mesa. Prove que é
> >>>>> sempre possível encontrar uma pessoa cujos vizinhos são ambos garotas.
>
> >>>>> Parece muito fácil? Tente a escrever a solução! Vale a pena.
>
> >>>>> Esse aqui eu tirei de um dos livros do Titu:
>
> - Show quoted text -
Cristiano Santos Benjamin
Oct 18, 2009, 8:37:55 PM10/18/09
to Matemática Radical
Ops! reenviando, pois tinha falta de pontuação em uma certa parte do
texto
Bom pessoal. Não tive coragem de tentar arrumar um prova diferente da
que Sergio trouxe pra nós. Mas pensei aqui como seria a melhor
arrumação para que e evento onde temos uma pessoa com duas vizinhas
ocorresse o menor número possível de vezes.
Vamos tentar fazer a arrumação de modo em que não haja uma pessoa
cujo
os dois vizinhos sejam garotas. Quando eu me referir a uma pessoa
cujo
os dois vizinhos sejam garotas falarei apenas uma “cadeira com duas
vizinhas”.
Vamos enumerar as cadeiras no sentido horário de 1 a 50 e vamos
colocar uma garota sentada na cadeira 1. Vamos colocar uma garota
sentada na cadeira 2(I). A cadeira 3 terá que ser ocupada por um
garoto, pois se não a cadeira dois teria duas vizinhas. A cadeira 4
pelo mesmo motivo anterior terá que ser ocupada por um garoto. Até o
momento temos 23 garotos e 23 garotas em pé. Poderíamos ocupar as
próximas 23 cadeiras de garotos que não teríamos problemas. Mas aí
teríamos outras 23 cadeiras ocupada por garotas e isso não serve pra
nós. O mais interessante seria ocupar a cadeira 5 por uma garota e
repetir o ciclo(II) das 4 primeiras cadeira. Então teríamos a cadeira
4n ocupada por um garoto e teríamos 25-2n garotos e 25-2n garotas em
pé. O número máximo para n é 12 e nesse caso teríamos duas cadeiras
vizinhas para ser ocupadas. A cadeira 50 tem que ser ocupada por um
garoto, pois se não a pessoa da cadeira 1 teria duas vizinhas. Só
resta a cadeira 49 para ser ocupada por uma garota e a cadeira 50
terá duas vizinhas.
(I) Observe que se ocupássemos a cadeira 2 por um garoto teríamos a
mesma arrumação só que rotacionada de uma unidade no sentido anti-
horário.
Generalizando o problema:
Vamos considerar o caso geral onde temos x garotos e y garotas e uma
mesa redonda com k=x+y cadeiras. É interessante observar que se y>x
não há como não ter uma cadeira com duas vizinhas. Se x>y sempre terá
como arrumar de modo que nenhuma cadeira tenha duas vizinhas. Se
x=y=t, a arrumação acima será a melhor arrumação de modo que o número
de cadeiras j que tem duas vizinhas seja o menor possível. Se t for
par j=0 e se t for ímpar j=1. Note que se t for par então k vai ser
divisível por 4 e teremos k /4 ciclos(II) na nossa arrumação. Se t
for
ímpar teremos k=4p+2 e aí teríamos p ciclos e sobraria 2 cadeiras pra
ser ocupadas por um garoto e uma garota onde haveria uma cadeira com
duas vizinhas.
Me corrijam se eu me equivoquei em alguma parte
On Oct 18, 10:31 pm, Cristiano Santos Benjamin
> > - Show quoted text -- Hide quoted text -
texto
Bom pessoal. Não tive coragem de tentar arrumar um prova diferente da
que Sergio trouxe pra nós. Mas pensei aqui como seria a melhor
arrumação para que e evento onde temos uma pessoa com duas vizinhas
ocorresse o menor número possível de vezes.
Vamos tentar fazer a arrumação de modo em que não haja uma pessoa
cujo
os dois vizinhos sejam garotas. Quando eu me referir a uma pessoa
cujo
os dois vizinhos sejam garotas falarei apenas uma “cadeira com duas
vizinhas”.
Vamos enumerar as cadeiras no sentido horário de 1 a 50 e vamos
colocar uma garota sentada na cadeira 1. Vamos colocar uma garota
sentada na cadeira 2(I). A cadeira 3 terá que ser ocupada por um
garoto, pois se não a cadeira dois teria duas vizinhas. A cadeira 4
pelo mesmo motivo anterior terá que ser ocupada por um garoto. Até o
momento temos 23 garotos e 23 garotas em pé. Poderíamos ocupar as
próximas 23 cadeiras de garotos que não teríamos problemas. Mas aí
teríamos outras 23 cadeiras ocupada por garotas e isso não serve pra
nós. O mais interessante seria ocupar a cadeira 5 por uma garota e
repetir o ciclo(II) das 4 primeiras cadeira. Então teríamos a cadeira
4n ocupada por um garoto e teríamos 25-2n garotos e 25-2n garotas em
pé. O número máximo para n é 12 e nesse caso teríamos duas cadeiras
vizinhas para ser ocupadas. A cadeira 50 tem que ser ocupada por um
resta a cadeira 49 para ser ocupada por uma garota e a cadeira 50
terá duas vizinhas.
(I) Observe que se ocupássemos a cadeira 2 por um garoto teríamos a
mesma arrumação só que rotacionada de uma unidade no sentido anti-
horário.
Generalizando o problema:
Vamos considerar o caso geral onde temos x garotos e y garotas e uma
mesa redonda com k=x+y cadeiras. É interessante observar que se y>x
não há como não ter uma cadeira com duas vizinhas. Se x>y sempre terá
como arrumar de modo que nenhuma cadeira tenha duas vizinhas. Se
x=y=t, a arrumação acima será a melhor arrumação de modo que o número
de cadeiras j que tem duas vizinhas seja o menor possível. Se t for
par j=0 e se t for ímpar j=1. Note que se t for par então k vai ser
divisível por 4 e teremos k /4 ciclos(II) na nossa arrumação. Se t
for
ímpar teremos k=4p+2 e aí teríamos p ciclos e sobraria 2 cadeiras pra
ser ocupadas por um garoto e uma garota onde haveria uma cadeira com
duas vizinhas.
Me corrijam se eu me equivoquei em alguma parte
Sergio Alvarez
Oct 18, 2009, 11:24:53 PM10/18/09
to matematic...@googlegroups.com
Valeu, Cris! A idéia é essa mesmo. Antes de partir para a solução é bom sentir o problema, entender como ele funciona.
Acho que esse é jeito natural de começar pensar sobre esse problema mas a solução exige um caminho diferente porque a disposição das pessoas em torno da mesa não está restrita a nenhum método específico - como o que você descreveu.
Agora que você já entendeu bem o problema, tenta terminar a solução!
Acho que esse é jeito natural de começar pensar sobre esse problema mas a solução exige um caminho diferente porque a disposição das pessoas em torno da mesa não está restrita a nenhum método específico - como o que você descreveu.
Agora que você já entendeu bem o problema, tenta terminar a solução!
2009/10/18 Cristiano Santos Benjamin <csbenja...@hotmail.com>
Sergio Alvarez
Oct 19, 2009, 11:45:33 PM10/19/09
to matematic...@googlegroups.com
E finalmente, o momento tão esperado...
Vamos terminar de escrever a SO-LU-ÇÃO!!!
Já sabemos que a soma das popularidades vale 50.
Agora, vamos seguir o roteiro para o resto da solução.
Suponha que cada indivíduo seja vizinho de no máximo uma garota. Ou seja, a popularidade de cada pessoa (garoto ou garota) é no máximo 1.
Disso e do fato de que a soma das popularidades vale 50, resulta que a popularidade de cada pessoa vale exatamente 1.
Ou seja, cada pessoa tem um vizinho que é uma garota e outro que é um garoto.
Agora, separe os garotos em duas classes: A e B.
Um garoto está na classe A, se o seu vizinho da esquerda é um garoto.
Um garoto está na classe B, se o seu vizinho da direita é um garoto.
As classes A e B têm o mesmo número de elementos.
Hmm... você quer saber por quê, né? Tudo bem.
Para cada garoto a da classe A, defina f(a) como sendo o garoto que é vizinho de a. Isso define uma função f:A->B. Veja: como a é um membro da classe A, o garoto f(a) é o vizinho da esquerda de a. Então, a é o vizinho da direita de f(a). Logo, o vizinho da direita de f(a) é um garoto. Portanto, f(a) é um membro da classe B.
Como cada pessoa tem apenas um vizinho que é um garoto, a função f é injetiva. De fato, se f(a1) = f(a2) = b, então b é um garoto que é vizinho de dois outros garotos: a1 e a2, o que não pode ocorrer.
E a função f também é sobrejetiva, afinal dado um garoto b da classe B, o seu vizinho da direita é um garoto a da classe A tal que f(a) = b.
Resulta que f:A->B é uma bijeção. Portanto, A e B têm o mesmo número de elementos. Seja n esse número.
Claramente, as classes A e B são disjuntas e sua reunião é o conjunto de todos os garotos. Então:
número de garotos = número de membros da classe A + número de membros da classe B
Ou seja, 25 = n + n. Percebeu?
25 = 2n
Isso é absurdo, afinal 25 é um número ímpar.
Essa conclusão absurda foi consequência de termos assumido que cada indivíduo é vizinho de no máximo uma garota.
Resulta que alguém é vizinho de duas garotas.
Vamos terminar de escrever a SO-LU-ÇÃO!!!
Já sabemos que a soma das popularidades vale 50.
Agora, vamos seguir o roteiro para o resto da solução.
Suponha que cada indivíduo seja vizinho de no máximo uma garota. Ou seja, a popularidade de cada pessoa (garoto ou garota) é no máximo 1.
Disso e do fato de que a soma das popularidades vale 50, resulta que a popularidade de cada pessoa vale exatamente 1.
Ou seja, cada pessoa tem um vizinho que é uma garota e outro que é um garoto.
Agora, separe os garotos em duas classes: A e B.
Um garoto está na classe A, se o seu vizinho da esquerda é um garoto.
Um garoto está na classe B, se o seu vizinho da direita é um garoto.
Hmm... você quer saber por quê, né? Tudo bem.
Para cada garoto a da classe A, defina f(a) como sendo o garoto que é vizinho de a. Isso define uma função f:A->B. Veja: como a é um membro da classe A, o garoto f(a) é o vizinho da esquerda de a. Então, a é o vizinho da direita de f(a). Logo, o vizinho da direita de f(a) é um garoto. Portanto, f(a) é um membro da classe B.
Como cada pessoa tem apenas um vizinho que é um garoto, a função f é injetiva. De fato, se f(a1) = f(a2) = b, então b é um garoto que é vizinho de dois outros garotos: a1 e a2, o que não pode ocorrer.
E a função f também é sobrejetiva, afinal dado um garoto b da classe B, o seu vizinho da direita é um garoto a da classe A tal que f(a) = b.
Resulta que f:A->B é uma bijeção. Portanto, A e B têm o mesmo número de elementos. Seja n esse número.
Claramente, as classes A e B são disjuntas e sua reunião é o conjunto de todos os garotos. Então:
número de garotos = número de membros da classe A + número de membros da classe B
Ou seja, 25 = n + n. Percebeu?
25 = 2n
Isso é absurdo, afinal 25 é um número ímpar.
Essa conclusão absurda foi consequência de termos assumido que cada indivíduo é vizinho de no máximo uma garota.
Resulta que alguém é vizinho de duas garotas.
2009/10/19 Sergio Alvarez <sergi...@gmail.com>
Reply all
Reply to author
Forward
0 new messages