Re: [obm-l] violencia

[Vinicius José Fortuna <vinicius.fortuna@xxxxxxxxxxxxx>]

Oi Rogério
Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu
nem tinha infinitos conjuntos! Apenas conjuntos infinitos.

Até mais

Vinicius

----- Original Message -----
From: "Rogerio Fajardo" <rogeriofajardo@hotmail.com>
To: <obm-l@mat.puc-rio.br>
Sent: Sunday, September 08, 2002 2:17 PM
Subject: Re: [obm-l] violencia


> É bom notar que essa solução usa o axioma da escolha (de infinitos
conjuntos
> não-vazios, escolhemos um elemento de cada). É essencial o axioma da
escolha
> para resolvê-lo?
>
>
> >From: Vinicius José Fortuna <vinicius.fortuna@ic.unicamp.br>
> >Reply-To: obm-l@mat.puc-rio.br
> >To: <obm-l@mat.puc-rio.br>
> >Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300
> >
> >----- Original Message -----
> >From: "Fernanda Medeiros" <femedeiros2001@hotmail.com>
> >To: <obm-l@mat.puc-rio.br>
> >Sent: Saturday, September 07, 2002 8:45 PM
> >Subject: [obm-l] violencia
> >
> >
> > > Olá,
> > > alguém pode dar uma ajuda nestas questões?
> > > 1.a)uma "gang" tem infinitos bandidos e cada um dos meliantes tem um
> >único
> > > inimigo no interior da "gang",que ele quer matar.Prove q é possivel
> >reunir
> > > uma quantidade infinita de bandidos desta "gang", semq  haja  o risco
de
> >q
> > > um bandido mate outro durante a reunião.
> >
> >Pense no seguinte algoritmo:
> >Temos o conjunto C de candidatos à reunião que inicialmente contém todos
os
> >infinitos bandidos da gangue.
> >Temos o conjunto R de bandidos selecionados para a reunião que
inicialmente
> >está vazio.
> >
> >A cada passo do algoritmo procuramos em C alguém que não que matar
ninguém
> >de R e ninguém em R quer matá-lo.
> >Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar.
> >Como cada bandido de R só quer matar um, |M|<=|R|
> >Então, como R é finito, M será finito e V=C-M será infinito, pois C é
> >infinito.
> >V será o subconjunto de C dos bandidos que ninguém de R quer matar.
> >Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele
> >de
> >C, o inserimos em R e repete-se o processo.
> >
> >Se sempre for possível encontrar tal bandido, o processo se repetirá
> >indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos
> >na
> >reunião sem derramamento de sangue.
> >
> >Se em algum momento não for possível encontrar um bandido em V, é porque
> >todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V
quer
> >matar outro de V. Pegamos, então, V como o conjunto de bandidos para a
> >reunião. Como V é infinito, teremos infinitos participantes na reunião.
> >
> > > b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um
> >bandido
> > > pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim
> >por
> > > diante).Será sempre possivel promover uma reunião com infinitos
bandidos
> >sem
> > > risco de derramamento de sangue?
> >Não é possível. Existe um contra-exemplo:
> >Ordene os bandidos formando uma sequência. Imagine que cada bandido quer
> >matar todos que vêm antes dele na sequência. Nunca poderemos ter dois
> >bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes
de,
> >assim haverá um que vai querer matar o outro. Então só poderemos ter um
> >bandido na reunião.
> >
> >Até mais
> >
> >Vinicius Fortuna
> >IC-Unicamp


=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================