Re: [obm-l] violencia

["Rogerio Fajardo" <rogeriofajardo@xxxxxxxxxxx>]

É 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>
>=========================================================================


s

_________________________________________________________________
Join the world’s largest e-mail service with MSN Hotmail. 
http://www.hotmail.com

=========================================================================
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>
=========================================================================