Olá, Vinicius Cada vez que voce "retira um elemento de C" e coloca em R, na verdade voce mudou o conjunto C. Ou seja, cada escolha que voce fez, no processo indutivo, foi sobre um conjunto diferente. É semelhante a demonstração de que todo conjunto infinto possui um subconjunto enumerável, em que, dado um conjunto V, construímos indutivamente um conjunto S colocando nele, a cada passo, um elemento de V que não está em S, usando o Axioma da Escolha
>From: Vinicius José Fortuna <[EMAIL PROTECTED]> >Reply-To: [EMAIL PROTECTED] >To: <[EMAIL PROTECTED]> >Subject: Re: [obm-l] violencia >Date: Sun, 8 Sep 2002 18:41:45 -0300 > >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" <[EMAIL PROTECTED]> >To: <[EMAIL PROTECTED]> >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 <[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]> >========================================================================= _________________________________________________________________ MSN Photos is the easiest way to share and print your photos: http://photos.msn.com/support/worldwide.aspx ========================================================================= 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]> =========================================================================
