On Sat, Sep 07, 2002 at 11:45:37PM +0000, Fernanda Medeiros wrote: > > > 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. > 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?
Sei que um monte de gente já respondeu mas gostei da questão e quero dar a minha solução. Antes de mais nada devemos entender que no enunciado estão implicitamente excluídos os bandidos suicidas (inimigos deles próprios)... (a) Se existe algum bandido x que é odiado por uma infinidade de outros bandidos, escolhemos todos os bandidos que odeiam x. Supomos a partir de agora que qualquer bandido é odiado apenas por um número finito de outros bandidos: assim a presença de um bandido na reunião só exclui um número finito de outros (o que ele odeia e os que o odeiam). É bem fácil montar um conjunto infinito: pegue um bandido qualquer, um que não tenha sido excluido pelo primeiro, um que não tenha sido excluido pelos dois primeiros,... A qualquer momento apenas um número finito de bandidos foi excluido logo podemos continuar. (b) Se os bandidos se chamam 0, 1, 2, 3, ..., n, ... e cada bandido odeia todos os que têm um número menor do que o dele é impossível reunir sequer dois bandidos. Mas o item que me parece mais interessante é: (c) se cada bandido odeia k outros bandidos (k fixo), ainda é possível reunir uma infinidade de bandidos? A resposta ainda é sim e provamos isso por indução em k. Imagine que cada bandido ordena seus inimigos de 1 a k. Por indução, podemos formar um subconjunto em que ninguém odeia ninguém nas (k-1) primeiras posições (mas talvez odeie na posição k). Acabamos de reduzir o problema ao item (a)... []s, N. ========================================================================= 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]> =========================================================================