Re: [obm-l] violencia

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

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