Strangers at a party
Alice had a party last night, but Bob wasn't invited. When Bob was told that people were at the party, he announced, "I know that there were three people at the party who were mutual acquaintances or mutual strangers."
Given that Bob is perfectly logical, what is the minimum possible value of ?
The answer is 6.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
A famous problem. I will prove that the minimum is k = 6 .
It is easy to construct a counterexample for k = 5 .
If k = 6 , then consider one person A and A 's relation to the other 5 people. We will prove the problem statement via contradiction.
By Pigeonhole Principle, at least three of the other 5 people are either friends or strangers to A . If at least three are friends, then these three (or more) people's relations to each other must all not be friends (if two of them were friends, they would form a mutual friend triangle with A . But then they are all mutual strangers, contradiction.
A similar logic can be applied if at least three relations of A are mutual strangers, so it follows that k = 6 is the minimum.