Re: [obm-l] violencia e axioma da escolha

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

Não sei se entendi direito, mas, ao meu ver, não teríamos conjuntos dois a
dois disjuntos e tal propriedade é necessária para aplicar o axioma da
escolha (ou não?).

De qualquer forma, não poderíamos mapear os bandidos nos números inteiros?
Assim teríamos uma função de escolha que pegaria em C o bandido mapeado no
menor inteiro tal que satisfaça aquelas condições para entrar em R. Se temos
uma função de escolha então podemos escolhê-los independentemente do axioma
da escolha.

Agradeço esclarecimentos

Vinicius Fortuna

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


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