Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another.
Hint: Use the pigeonhole principle.
I don't see how this applies to the pigeonhole principle because I keep imagining a group of 4 strangers, and then 2 friends. This would be 6 total but against what the proof is asking. Maybe I don't understand the proof in question...
Consider $6$ people represented by dots in a circle. Let every dot be connected to every other dot by a line and let the lines be the color red if the two people know each other and blue if they do not know each other. Consider any of the $6$ dots, say dot $x$. We can see that $x$ is connected to $5$ other dots by a line and by the pigeonhole principle $3$ of these lines are the same color, say red (the proof is analogous if we choose blue instead of red) . Now examine the $3$ dots connected to $x$. If any of those $3$ people are connected by a red line, then we have found a red triangle which represents $3$ people who know each other. If the $3$ people are not connected by any red lines, then all $3$ of them are connected by blue lines forming a blue triangle which represents $3$ people not knowing each other. Thus in a group of $6$ people there will always be $3$ people who know each other or $3$ people who do not know each other.
The pigeonhole principle applies because every person is related to every other person in two ways, (either they know the person or they do not). So when we consider any of the $6$ people we know that they know $3$ people or they don't know $3$ people.
See Theorem on friends and strangers. The proof section gives precisely what you want and explains how the pigeonhole principle is used here.
This can be seen as the Ramsey number $R(3,3)$ , and we know that $R(3,3)=6$. The Ramsey number $R(s,t)$ can be seen as the least number R so that a $K_r$ graph painted of 2 colors ; say colors A and B, contains either a $K_s$ of color A, or a $K_t$ subgraph of color B .
To illustrate the situation, draw a $K_6$ graph, i.e., a complete graph on $6$ vertices (a graph on 6 vertices where any two vertices are joined by an edge), and join any two vertices with, say, a red edge if two people know each other, and join them with/by a blue vertex otherwise. Fix a given vertex x. Then there are , by the pigeonhole principle, at least $3$ blue ( can also be red) incident with x....Can you continue from here?
