Re: [obm-l] violencia

["Rogerio Fajardo" <rogeriofajardo@xxxxxxxxxxx>]

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




_________________________________________________________________
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 é <nicolau@mat.puc-rio.br>
=========================================================================