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

Home > Logic
Mutually friendly (Posted on 2002-07-01) Difficulty: 2 of 5
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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information