Cada um com seu par
11 views
Skip to first unread message
Sergio Alvarez
Oct 20, 2009, 12:12:23 AM10/20/09
to matematic...@googlegroups.com
Em uma festa, toda mulher dança com algum homem e nenhum homem dança com todas as mulheres. Demonstre que existem homens H0 e H1 e mulheres M0 e M1 tais que H0 dança com M0, H1 dança com M1, H1 não dança com M0, H0 não dança com M1.
Este foi o Problema 1 da 13a Olimpíada Brasileira de Matemática. Um jeito muito agradável de se começar uma prova, né? A garotada deve ter se divertido.
Você pode encontrar provas e gabaritos das olimpíadas brasileiras de matemática (de 1997 a 2009) no endereço
http://www.obm.org.br/opencms/provas_gabaritos/
Estão lá inclusive as provas do nível universitário, várias com gabarito.
Aproveite para passear no site da obm, tem muita coisa legal por lá...
Este foi o Problema 1 da 13a Olimpíada Brasileira de Matemática. Um jeito muito agradável de se começar uma prova, né? A garotada deve ter se divertido.
Você pode encontrar provas e gabaritos das olimpíadas brasileiras de matemática (de 1997 a 2009) no endereço
http://www.obm.org.br/opencms/provas_gabaritos/
Estão lá inclusive as provas do nível universitário, várias com gabarito.
Aproveite para passear no site da obm, tem muita coisa legal por lá...
Cristiano Santos Benjamin
Oct 20, 2009, 8:40:03 PM10/20/09
to Matemática Radical
Vamos tentar construir uma situação em que não ocorre o caso dado pelo
problema e conluir que não tem como um número finito de mulheres
satisfazer a não ocorrencia do evento. A priore vamos supor a
existencia de uma mulher M0. Designaremos que H dança com M como sendo
H~M e H não dança com M como sendo H^M.
Vamos começar com M0. Ela tem que dançar com pelo o menos 1 homem e
definiremos ele com sendo H0. Logo M0~H0. Como H0 não pode dançar com
todas as mulheres acrescentaremos M1 tal que M1^H0. M1 tem que dançar
com algum homem e este não pode ser H0. Logo deverá existir H1 tal que
M1~H1. Logo temos que M0~H0, H0^M1, M1~H1. Para que o evento do
problema não ocorra iremos dizer também que H1~M0. Mas aí H1 terá
dançado com todas as mulheres. Teremos que acrescentar mais uma mulher
que iremos chamar de M2, tal que M2^H1. M2 tem que dançar com alguém e
vamos dizer que seja com H0. Então temo M2~H0 H0^M1 M1~H1 e
H1^M2.teremos que o evento ocorre e para que não ocorra teremos que,
por exemplo supor que H0~M1 e aí ele terá dançado com todas as
mulheres. Teremos agora que acrescentar mais uma mulher e aí
ficaríamos acrescentando mulheres para sempre para que o evento não
ocorra e nunca teria fim.
Isso tá longe de ser um demonstração mas nos leva pelo o menos a
entender o problema. Tentarei pensar em uma demonstração.
problema e conluir que não tem como um número finito de mulheres
satisfazer a não ocorrencia do evento. A priore vamos supor a
existencia de uma mulher M0. Designaremos que H dança com M como sendo
H~M e H não dança com M como sendo H^M.
Vamos começar com M0. Ela tem que dançar com pelo o menos 1 homem e
definiremos ele com sendo H0. Logo M0~H0. Como H0 não pode dançar com
todas as mulheres acrescentaremos M1 tal que M1^H0. M1 tem que dançar
com algum homem e este não pode ser H0. Logo deverá existir H1 tal que
M1~H1. Logo temos que M0~H0, H0^M1, M1~H1. Para que o evento do
problema não ocorra iremos dizer também que H1~M0. Mas aí H1 terá
dançado com todas as mulheres. Teremos que acrescentar mais uma mulher
que iremos chamar de M2, tal que M2^H1. M2 tem que dançar com alguém e
vamos dizer que seja com H0. Então temo M2~H0 H0^M1 M1~H1 e
H1^M2.teremos que o evento ocorre e para que não ocorra teremos que,
por exemplo supor que H0~M1 e aí ele terá dançado com todas as
mulheres. Teremos agora que acrescentar mais uma mulher e aí
ficaríamos acrescentando mulheres para sempre para que o evento não
ocorra e nunca teria fim.
Isso tá longe de ser um demonstração mas nos leva pelo o menos a
entender o problema. Tentarei pensar em uma demonstração.
Sergio Alvarez
Oct 20, 2009, 10:04:23 PM10/20/09
to matematic...@googlegroups.com
Massa, Cris! Muito bom... uma parte da solução que eu conheço para esse problema está contida no seu texto!
Uma sugestão para entender o que o Cris escreveu: representem os homens e as mulheres através de pontinhos com os nomes H0, H1, M0, M1,... e ligue os pontos correspondentes a duas pessoas quando elas dançam.
Eu mesmo fiz isso e me ajudou bastante, hehe!
Quanto à solução...
Tem uma idéia importante escapando. Estou pensando se já dou uma dica.
Hmm...
Quer saber? A coisa está indo bem.
Deixa a dica para amanhã!
Uma sugestão para entender o que o Cris escreveu: representem os homens e as mulheres através de pontinhos com os nomes H0, H1, M0, M1,... e ligue os pontos correspondentes a duas pessoas quando elas dançam.
Eu mesmo fiz isso e me ajudou bastante, hehe!
Quanto à solução...
Tem uma idéia importante escapando. Estou pensando se já dou uma dica.
Hmm...
Quer saber? A coisa está indo bem.
Deixa a dica para amanhã!
2009/10/20 Cristiano Santos Benjamin <csbenja...@hotmail.com>
Sergio Alvarez
Oct 21, 2009, 9:04:00 PM10/21/09
to matematic...@googlegroups.com
Dica. A idéia é tentar construir os dois pares (H0,M0) e (H1,M1).
Primeira tentantiva (baseado no raciocínio descrito pelo Cris):
Escolha uma mulher M0 qualquer. Ela dança com algum homem. Escolha um dos homens com que M0 dança e chame-o de H0. Esse homem não dança com todas as mulheres. Escolha uma mulher M1 tal que H0 não dança com M1. Sabemos que M1 dança com algum homem. Deveríamos escolher um homem que dança com M1 para ser H1.
O problema é garantir que H1 não dança com M0.
Mas o que a gente ainda pode usar?
Parece que chegamos num beco sem saída. Precisamos de um novo ponto de partida.
Então, vamos para a grande sacada: comece escolhendo o homem H0 como sendo o homem que dançou com mais mulheres na festa.
Ai, que emoção! Quem será M0? Será que H1 encontrará M1? E se eles trocarem de par só para fazer ciúmes?
Não percam o próximo capítulo de "Cada um com seu par".
Primeira tentantiva (baseado no raciocínio descrito pelo Cris):
Escolha uma mulher M0 qualquer. Ela dança com algum homem. Escolha um dos homens com que M0 dança e chame-o de H0. Esse homem não dança com todas as mulheres. Escolha uma mulher M1 tal que H0 não dança com M1. Sabemos que M1 dança com algum homem. Deveríamos escolher um homem que dança com M1 para ser H1.
O problema é garantir que H1 não dança com M0.
Mas o que a gente ainda pode usar?
Parece que chegamos num beco sem saída. Precisamos de um novo ponto de partida.
Então, vamos para a grande sacada: comece escolhendo o homem H0 como sendo o homem que dançou com mais mulheres na festa.
Ai, que emoção! Quem será M0? Será que H1 encontrará M1? E se eles trocarem de par só para fazer ciúmes?
Não percam o próximo capítulo de "Cada um com seu par".
2009/10/20 Sergio Alvarez <sergi...@gmail.com>
Cristiano Santos Benjamin
Oct 21, 2009, 9:25:46 PM10/21/09
to Matemática Radical
Seja H0 o homem que dançou com mais mulheres na festa e seja M1 a
mulher que não dançou com H0. Sabemos que M1 dançou com pelo o menos
um homem. Vamos chama-lo de H1. Partindo do princípio que H0 foi o
homem que dançou com mais mulheres e chamando esse número de mulheres
de k então temos que H1 dançou com no máximo k mulheres. Temos que H1
dançou com uma mulher M1 que não dançou com H0 então sobram no máximo
k-1 mulheres além de M1 que pode ter dançado com H1. Sendo assim
concluímos que existe pelo o menos uma mulher M0 que dançou com H0 e
que não dançou com H1. cqd
On Oct 21, 10:04 pm, Sergio Alvarez <sergio1...@gmail.com> wrote:
> Dica. A idéia é tentar construir os dois pares (H0,M0) e (H1,M1).
>
> Primeira tentantiva (baseado no raciocínio descrito pelo Cris):
>
> Escolha uma mulher M0 qualquer. Ela dança com algum homem. Escolha um dos
> homens com que M0 dança e chame-o de H0. Esse homem não dança com todas as
> mulheres. Escolha uma mulher M1 tal que H0 não dança com M1. Sabemos que M1
> dança com algum homem. Deveríamos escolher um homem que dança com M1 para
> ser H1.
>
> O problema é garantir que H1 não dança com M0.
>
> Mas o que a gente ainda pode usar?
>
> Parece que chegamos num beco sem saída. Precisamos de um novo ponto de
> partida.
>
> Então, vamos para a grande sacada: comece escolhendo o homem H0 como sendo o
> homem que dançou com mais mulheres na festa.
>
> Ai, que emoção! Quem será M0? Será que H1 encontrará M1? E se eles trocarem
> de par só para fazer ciúmes?
>
> Não percam o próximo capítulo de "Cada um com seu par".
>
> 2009/10/20 Sergio Alvarez <sergio1...@gmail.com>
> >> > Aproveite para passear no site da obm, tem muita coisa legal por lá...- Hide quoted text -
>
> - Show quoted text -
mulher que não dançou com H0. Sabemos que M1 dançou com pelo o menos
um homem. Vamos chama-lo de H1. Partindo do princípio que H0 foi o
homem que dançou com mais mulheres e chamando esse número de mulheres
de k então temos que H1 dançou com no máximo k mulheres. Temos que H1
dançou com uma mulher M1 que não dançou com H0 então sobram no máximo
k-1 mulheres além de M1 que pode ter dançado com H1. Sendo assim
concluímos que existe pelo o menos uma mulher M0 que dançou com H0 e
que não dançou com H1. cqd
On Oct 21, 10:04 pm, Sergio Alvarez <sergio1...@gmail.com> wrote:
> Dica. A idéia é tentar construir os dois pares (H0,M0) e (H1,M1).
>
> Primeira tentantiva (baseado no raciocínio descrito pelo Cris):
>
> Escolha uma mulher M0 qualquer. Ela dança com algum homem. Escolha um dos
> homens com que M0 dança e chame-o de H0. Esse homem não dança com todas as
> mulheres. Escolha uma mulher M1 tal que H0 não dança com M1. Sabemos que M1
> dança com algum homem. Deveríamos escolher um homem que dança com M1 para
> ser H1.
>
> O problema é garantir que H1 não dança com M0.
>
> Mas o que a gente ainda pode usar?
>
> Parece que chegamos num beco sem saída. Precisamos de um novo ponto de
> partida.
>
> Então, vamos para a grande sacada: comece escolhendo o homem H0 como sendo o
> homem que dançou com mais mulheres na festa.
>
> Ai, que emoção! Quem será M0? Será que H1 encontrará M1? E se eles trocarem
> de par só para fazer ciúmes?
>
> Não percam o próximo capítulo de "Cada um com seu par".
>
>
>
>
> > Massa, Cris! Muito bom... uma parte da solução que eu conheço para esse
> > problema está contida no seu texto!
>
> > Uma sugestão para entender o que o Cris escreveu: representem os homens e
> > as mulheres através de pontinhos com os nomes H0, H1, M0, M1,... e ligue os
> > pontos correspondentes a duas pessoas quando elas dançam.
>
> > Eu mesmo fiz isso e me ajudou bastante, hehe!
>
> > Quanto à solução...
>
> > Tem uma idéia importante escapando. Estou pensando se já dou uma dica.
>
> > Hmm...
>
> > Quer saber? A coisa está indo bem.
>
> > Deixa a dica para amanhã!
>
> > 2009/10/20 Cristiano Santos Benjamin <csbenjamin.m...@hotmail.com>
>
>
> > Massa, Cris! Muito bom... uma parte da solução que eu conheço para esse
> > problema está contida no seu texto!
>
> > Uma sugestão para entender o que o Cris escreveu: representem os homens e
> > as mulheres através de pontinhos com os nomes H0, H1, M0, M1,... e ligue os
> > pontos correspondentes a duas pessoas quando elas dançam.
>
> > Eu mesmo fiz isso e me ajudou bastante, hehe!
>
> > Quanto à solução...
>
> > Tem uma idéia importante escapando. Estou pensando se já dou uma dica.
>
> > Hmm...
>
> > Quer saber? A coisa está indo bem.
>
> > Deixa a dica para amanhã!
>
>
> - Show quoted text -
Sergio Alvarez
Oct 22, 2009, 8:51:35 AM10/22/09
to matematic...@googlegroups.com
Uau! Já?! Mandou bem! Esse problema é legal, né? E essa idéia é para guardar no coração: quando fazer a escolha ao acaso não funcionar muito bem, tente escolher um extremo (máximo ou mínimo).
"Essa estratégia de escolher o extremo é... extremamente útil. Foi assim que eu resolvi morar no último andar do World Trade Center." Dr. Maximus, em 10/09/2001
"Essa estratégia de escolher o extremo é... extremamente útil. Foi assim que eu resolvi morar no último andar do World Trade Center." Dr. Maximus, em 10/09/2001
2009/10/21 Cristiano Santos Benjamin <csbenja...@hotmail.com>
Carlos José Pereira
Oct 22, 2009, 8:54:10 AM10/22/09
to matematic...@googlegroups.com
> Uau! Já?! Mandou bem! Esse problema é legal, né? E essa idéia é para guardar
> no coração: quando fazer a escolha ao acaso não funcionar muito bem, tente
> escolher um extremo (máximo ou mínimo).
>
> "Essa estratégia de escolher o extremo é... extremamente útil. Foi assim que
> eu resolvi morar no último andar do World Trade Center." Dr. Maximus, em
> 10/09/2001
> no coração: quando fazer a escolha ao acaso não funcionar muito bem, tente
> escolher um extremo (máximo ou mínimo).
>
> "Essa estratégia de escolher o extremo é... extremamente útil. Foi assim que
> eu resolvi morar no último andar do World Trade Center." Dr. Maximus, em
> 10/09/2001
Não deixa de ser uma idéia legal.... se ele tivesse escolhido o outro
extremo (o primeiro andar), estava tudo ok....
RISOS!!
Abraços a todos!
Carlão
=====================================
Carlos José de Almeida Pereira
BLOG: http://starfightercarlao.blogspot.com
Ausência
Por muito tempo achei que a ausência é falta.
E lastimava, ignorante, a falta.
Hoje não a lastimo.
Não há falta na ausência.
A ausência é um estar em mim.
E sinto-a, branca, tão pegada, aconchegada nos meus braços,
que rio e danço e invento exclamações alegres,
porque a ausência, essa ausência assimilada,
ninguém a rouba mais de mim.
Carlos Drummond de Andrade
Elivaldo Lozer
Oct 22, 2009, 5:22:30 PM10/22/09
to Matemática Radical
Nossa... cheguei no meio da "novela" mais depois que li tudo quase
chorei de tanta emoção!
Que sacada mais mais inteligente!
Muito bom mesmo
Abraços
chorei de tanta emoção!
Que sacada mais mais inteligente!
Muito bom mesmo
Abraços
Reply all
Reply to author
Forward
0 new messages