All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Mutually friendly (Posted on 2002-07-01)
Prove that any group of six people contains either 3 mutual friends or 3 mutual strangers.

(For the purpose of this problem any pair of people must be either friends or strangers.)

 See The Solution Submitted by levik Rating: 3.0000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 10 of 11 |

Without loss of generality, we can assume that one of the six individuals N (say) has at least three friends, or N has at least three strangers.

If N has at least three strangers (say 1,2,3), then precisely one of the following will hold true:

(i) 1,2 and 3 are mutually friends.

(ii) 1,2 and 3 are mutually strangers.

(iii) At least two amongst 1,2 and 3 are mutual strangers.

We observe that for each of (i) and (ii), the conditions of the problem are trivially satisfied.

For (iii), the two mutual strangers (in relation to N) together with N constitute three mutual stangers and thus satisfy the given conditions.

It can be similarly proved that all the conditions of the problem will be satisfied if N has at least three friends.

 Posted by K Sengupta on 2008-09-05 06:36:10

 Search: Search body:
Forums (5)