Re: [obm-l] violencia

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

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