in Interview Questions
2,045 views
1 vote
1 vote
Prove that in a group of 6 people, there are at least three mutual friends or three mutual strangers.
in Interview Questions
2.0k views

2 Answers

5 votes
5 votes
Best answer

Hi. i think pigeonhole principle will be applied here..

two possibilities=> i) Mutual Friend,ii)stranger  (let K be the number of possibilities K=2 here)

now 6 people is there so N=6.

ceil(N/K)=ceil(6/2)=3

atleast 3 of them will have to be either friend or stranger

This is the approach

selected by
2 votes
2 votes
Use pigeon hole principal :

There are 2 types of people either friends or strangers .  Therefore $\left \lceil N/2 \right \rceil$ = 3 .

Hence there would be either three mutual friends or 3 strangers .

Related questions