MHB Is There a Trio of Nations with the Same Relationship in This Math Challenge?

[Ackbach]

Here is this week's POTW:

-----

In a group of 17 nations, any two nations are either mutual friends, mutual enemies, or neutral to each other. Show that there is a subgroup of 3 or more nations such that any two nations in the subgroup share the same kind of relationship.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

No one answered this week's POTW. You can see my solution below.

Spoiler

Number the nations 1 through 17, and call the nations in relationship F if they are friendly, E if they are enemies, and N if they are neutral. Consider the relationships 1 has with the others. It's not too difficult to show that the worst-case scenario is when the relationships 1 has with the other nations are evenly distributed. Even so, there have to be a group of at least six nations that have the same relationship with 1. Without loss of generality (WLOG), we may suppose these six nations are F with 1. Also WLOG, we may suppose these are nations 2 through 7. Now consider the relationships 2 has with 3 through 7. If any of these relationships are F, then we have a group of three nations as the problem is asking us to show. So, suppose not: 3 through 7 are all related to 2 with either E or N. Well, there are five nations here in a relationship with 2, and again, the worst-case scenario is that there are evenly distributed between E and N. WLOG, suppose there is a group of three nations that are related to 2 via E, and suppose they are (WLOG) nations 3, 4, and 5. Now, among these three nations, there cannot be any F relationships, nor can there be any E relationships. Hence, they are all N amongst themselves, thus producing our group of three, as desired.

An interesting extension would be how many nations would you have to have in order to ensure that at least four nations have the same relationship amongst themselves?