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