É 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 <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: <[EMAIL PROTECTED]> >Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 > >----- Original Message ----- >From: "Fernanda Medeiros" <[EMAIL PROTECTED]> >To: <[EMAIL PROTECTED]> >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 é <[EMAIL PROTECTED]> >========================================================================= 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 é <[EMAIL PROTECTED]> =========================================================================
