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

 Mutually friendly 3 (Posted on 2012-08-05)
Prove that if any two people are either friends or strangers, then any group of 18 people contains either 4 mutual friends or 4 mutual strangers.

 Submitted by Math Man Rating: 5.0000 (1 votes) Solution: (Hide) Take any person X. They are either friends with at least 9 people or strangers with at least 9 people. Suppose X is friends with at least 9 people. Let S be a set of 9 of these people. Take any person A in S. If A has less than 3 friends in S, then there are at least 6 people in S that are strangers with A. By Mutually friendly, these 6 people contain either 3 mutual friends or 3 mutual strangers. If they contain 3 mutual friends, then these 3 and X are 4 mutual friends. If they contain 3 mutual strangers, then these 3 and A are 4 mutual strangers. If A has at least 4 friends in S, then there are 4 people that are friends with both X and A. If any two of these people are friends, then these two, X, and A are 4 mutual friends. If they are all strangers, then they are 4 mutual strangers. Therefore, to avoid 4 mutual friends or 4 mutual strangers, A has to have exactly 3 friends in S. There are 9 people in S, and each person has 3 friends in S. Therefore, there are 27 friendships in S. However, friendships are symmetric, so there must be an even number of friendships. That is a contradiction, so if X is friends with at least 9 people, then there are either 4 mutual friends or 4 mutual strangers. A similar argument works if X is strangers with at least 9 people. Therefore, any group of 18 people contains either 4 mutual friends or 4 mutual strangers.

 Subject Author Date re: I think I have it now! Chris, PhD 2012-08-09 22:54:13 I think I have it now! Caleb 2012-08-07 13:08:15 5 mutual friends or 5 mutual strangers Steve Herman 2012-08-07 12:59:13 re(4): No Subject Caleb 2012-08-07 12:33:13 re(3): No Subject Chris, PhD 2012-08-07 11:36:30 re(2): No Subject Caleb 2012-08-07 10:58:20 re: No Subject Math Man 2012-08-07 09:25:32 Hint Math Man 2012-08-07 09:14:37 Confirmed: 18 is the minimum Steve Herman 2012-08-07 09:03:44 No Subject Chris, PhD 2012-08-07 06:46:43 "Solution"....but only for a total of 20 people Caleb 2012-08-07 04:07:58

 Search: Search body:
Forums (0)