IME / ITA ⇒ EFOMM - 2017 - Combinatória Tópico resolvido

[JohnnyEN]

Em uma festa, sabe-se que cada pessoa tem três amigos, mas que não há três pessoas que sejam amigas duas a duas. Qual é, então, a menor quantidade possível de pessoas na festa?
A) 9
B) 8
C) 7
D) 6
E) 4

Resposta

---

GAB:D

[petras]

JohnnyEN,


Vamos considerar as pessoas como vértices de um polígono e a relação de amizade
como lados ou diagonais.
Cada pessoa tem três amigos, então vértice está ligado com três outros. Mas não há três
pessoas que sejam amigas duas a duas, então não pode haver formação de triângulos.
Como cada pessoa têm três amigos, o menor número de pessoas que devemos
considerar é 4. Sejam 4 pessoas A, B, C e D. Vamos supor que a pessoa A seja amiga
das pessoas B, C e D. Analisando a pessoa B, observamos que deve mais dois amigos
além de A. Entretanto se B for amigo de C, forma-se um triângulo ABC, o que não é
permitido. Portanto, não é possível atender às condições propostas com 4 pessoas.



Acrescentando uma quinta pessoa E, teremos o mesmo problema, pois a pessoa B será
amiga de A e E, mas terá que ser amida de C ou D, formando assim um triângulo com
A. Portanto, não é possível atender às condições propostas com 4 pessoas.
Vamos considerar agora a configuração com seis pessoas A, B, C, D, E, F, podemos
construir a seguinte configuração que atende todas as condições.

Portanto, a menor quantidade possível de pessoas na festa é 6. (Resolução Prof. Renato)

[lbdmk]

Tive um raciocínio objetivo... se em um grupo de três pessoas não existe a amizade duas a duas, ou seja, quando ha tres pessoas, como João Pedro e Lucas, se tomarmos os amigos de Lucas, Pedro e João nao serão um desses amigos, pela condição que foi dada no enunciado, ou seja, os três amigos de Lucas estarão fora deste subconjunto tomado(Pedro Lucas e João) , então ha de ter, no mínimo, mais três pessoas fora os três ja tomados, que são os amigos de Lucas, assim serão seis ao todo.