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.
I am kind of guessing that you will have to use pigeonhole principle but not quite know how to apply? Help will be appreciated.
The problem comes from Fermat II 2014, a math contest of the University of Tennessee for high school students.
You will indeed use the pigeonhole principle: if $n = km + 1$ objects are distributed among $m$ boxes, then the pigeonhole principle asserts that one of the box will contain at least $k + 1$ objects.
To expand a bit about my comment, you can even actually use the result for $6$ vertices an $2$ colors, to solve for $17$ vertices and $3$ colors.
The simpler case: $6$ vertices, $2$ colors
Draw an hexagon, and consider a vertex $A$, and all $5$ diagonals that go to the other vertices. Among these $5$ diagonals, $3$ are of the same color, say red (pigeonhole principle). They go to $B$, $C$ and $D$.
Now, if one of $BC$, $BD$ or $CD$ is red, then you have a monochrome triangle (complete with $A$).
Otherwise, they are all of the other color. But then $BCD$ is monochrome.
17 vertices, 3 colors
Same method.
Consider a vertex $A$, and the $16$ diagonals from it. Then at least $6$ have the same color: pigeonhole principle, again, with $3\times5+1$ objects (diagonals) in $3$ boxes (colors).
These $6$ diagonals, say red, go to $B,C,D,E,F,G$. Now if one of the edges of $BCDEFG$ if red, you complete the monochrome triangle with $A$.
Otherwise, they are all of the other two colors. But then this is an hexagon with two colors. Already solved above: there is a monochrome triangle in it.
I guess you can now solve the case of $66$ vertices and $4$ colors, and more generally, for $n$ colors, you may consider $u_n$ vertices, with
$$\begin{align} u_n &=n(u_{n-1}-1)+2 \\ u_1 &=3 \end{align}$$
Then, in a complete graph with $u_n$ vertices and $n$ colors, you can find a monochrome triangle. That does not necessarily mean $u_n$ is the least number of vertices to achieve this, but it's an upper bound. The minimal numbers of vertices are Ramsey numbers.
You get for successive $u_n$: $3, 6, 17, 66, 327, 1958, 13701, 109602, 986411, 9864102\dots$ For example, a complete graph with $9864102$ vertices and $10$ colors has a monochrome triangle.
This is sequence A073591 in OEIS.
You have also
$$u_n=1+\sum_{k=0}^n \frac{n!}{k!}$$
The proof is easy by induction with
$$u_n=1+\sum_{k=0}^{n-1} \frac{n(n-1)!}{k!}+1=n\left(\sum_{k=0}^{n-1} \frac{(n-1)!}{k!}+1-1\right)+2=n(u_{n-1}-1)+2$$ It's also equal to $\lceil n! e\rceil$, where $\lceil x \rceil$ denotes the ceiling function, and $e=2.718\dots$