Re: [obm-l] PROBLEMINHA LIGHT!

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 31.03.04 18:40, jorgeluis@edu.unifor.br at jorgeluis@edu.unifor.br wrote:

> Ok! Carlos Gustavo e demais colegas! Grato pela resolução do problema do
> jornaleiro. Segue abaixo um divertido probleminha que admite duas respostas:
> 
> 
> Num reino distante quaisquer dois cavaleiros ou são amigos ou inimigos e cada
> cavaleiro tem exatamente três inimigos. Nesse reino vigora a seguinte lei
> entre 
> os cavaleiros: um inimigo do meu amigo é meu inimigo. Quantas possibilidades
> há 
> para o número de cavaleiros desse reino?      (RPM/IME/USP)
> 
> 

Uma solucao eh mais ou menos imediata:
4 cavaleiros, todos inimigos entre si.

Suponhamos, agora, que "a" seja amigo de "b".

A lei implica que se o conjunto de amigos de "a" eh {b} uniao M, entao o
conjunto dos amigos de "b" serah {a} uniao M.
Isso significa que "a" e "b" tem os mesmos 3 inimigos. Vamos chama-los de
"x", "y" e "z".

Se "x" for inimigo de "y", entao os 3 inimigos de "x" serao "a", "b" e "y" e
os 3 inimigos de "y" serao "a", "b", e "x".
Logo, "x" e "y" serao necessariamente amigos de "z".
Mas se "x" eh inimigo de "y" e "y" eh amigo de "z" entao, pela lei, "x"
terah que ser inimigo de "z" ==>
contradicao ==>
"x" eh amigo de "y".
De forma analoga, concluimos que "x" e "y" sao amigos de "z".

Mas "x", "y" e "z" ainda tem um terceiro inimigo. Vamos chama-lo de "c".
Como os inimigos de "a" e "b" sao "x", "y" e "z", concluimos que "c" serah
amigo de "a" e de "b".

Com isso, achamos a segunda solucao:
6 cavaleiros: a, b, c, x, y, z tais que:
a, b, c sao amigos entre si;
x, y, z sao amigos entre si;
a, b, c sao inimigos de x, y, z.

Suponhamos que haja um setimo cavaleiro. Vamos chama-lo de "h".
Eh claro que "h" soh pode ser amigo de "a", "b", "c", "x", "y" e "z", pois
cada um desses jah tem 3 inimigos.
Mas "a" eh inimigo de "x". Como "x" eh amigo de "h", a lei implica que "a"
eh inimigo de "h" ==>
contradicao ==>
"h" tem que ser inimigo de "x" ==>
contradicao ==>
nao pode haver um setimo cavaleiro.

Logo, temos apenas as duas solucoes descritas acima.

[]s,
Claudio.


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