Quarta, 11 Abril 2018 19:57

QUESTÕES PUC-RIO - PROBLEMINHA LIGHT

Escrito por

Segue abaixo um divertido probleminha que admite duas respostas

Problema

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 solução é 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" é {b} união M, então o conjunto dos amigos de "b" será {a} união M.

Isso significa que "a" e "b" têm os mesmos 3 inimigos. Vamos chamá-los de "x", "y" e "z".

Se "x" for inimigo de "y", então os 3 inimigos de "x" serão "a", "b" e "y" e os 3 inimigos de "y" serão "a", "b", e "x".

Logo, "x" e "y" serão necessariamente amigos de "z".

Mas se "x" é inimigo de "y" e "y" é amigo de "z" então, pela lei, "x" terá que ser inimigo de "z" ==>contradição ==>"x" é amigo de "y".

De forma análoga, concluímos que "x" e "y" são amigos de "z".

Mas "x", "y" e "z" ainda tem um terceiro inimigo. Vamos chamá-lo de "c".

Como os inimigos de "a" e "b" são "x", "y" e "z", concluímos que "c" será amigo de "a" e de "b".

Com isso, achamos a segunda solução:

6 cavaleiros: a, b, c, x, y, z tais que:

a, b, c são amigos entre si;

x, y, z são amigos entre si;

a, b, c são inimigos de x, y, z.

Suponhamos que haja um sétimo cavaleiro. Vamos chamá-lo de "h".

É claro que "h" só pode ser amigo de "a", "b", "c", "x", "y" e "z", pois cada um desses já tem 3 inimigos.

Mas "a" é inimigo de "x". Como "x" é amigo de "h", a lei implica que "a" é inimigo de "h" ==> contradição ==>"h" tem que ser inimigo de "x" ==>contradição ==> não pode haver um sétimo cavaleiro.

Logo, temos apenas as duas soluções descritas acima.

Confira essa discussão em: http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200403/msg01240.html

Ler 36 vezes Última modificação em Quinta, 12 Abril 2018 19:08
Antonio Claudio Lage Buffara

Me descrevo com um engenheiro, empresário e investidor mas com alma de matemático.

O blog é direcionado especialmente aos professores e estudantes de matemática. Tratará não só da matemática em si mas também do ensino da matemática, desde a escola (ensino fundamental) até a universidade.

Deixe um comentário

Certifique-se de preencher os campos indicados com (*). Não é permitido código HTML.