The Pigeonhole Principle

Take any two points and consider the unique great circle that passes through them. This great circle divides the sphere into two hemispheres. Each of the remaining three points must be in at least one of these two hemispheres, so by the pigeonhole principle one hemisphere contains two of these points. Along with the original two points along the great circle, this constitutes four points in a closed hemisphere.

Note that there are thirty-four numbers in the arithmetic progression \(1,4,7,\dotsc,100.\) Also note that the numbers \(1\) and \(52\) cannot be added to another member of the progression to sum to \(104\). The remaining thirty-two numbers can though.

Let our pigeons be the eighteen elements of \(A\) that are certainly not \(1\) or \(52\), and let our holes be the pairs of numbers \[ \{4,100\} \quad \{7,97\} \quad \dotsb \quad \{49,55\} \] from the progression that sum to \(104\). There are sixteen such pairs that sum to \(104\), so by the pigeonhole principle \(A\) must contain both members of at least one of these pairs.

What are the pigeons? What are the holes? Since we’re assigning each subset a sum, and hoping two subsets collide on the same sum, we should think of the subsets as our pigeons and the possible sums as our holes. Let’s count our pigeons and holes.

First, there are \(2^{10}\) subsets of the set with ten elements. We should ignore the empty set and the set itself, so that’s \(2^{10} - 2 = 1022\) subsets (pigeons). Next, the largest possible sum we could get is \(99 + 98 + \dotsb + 91 + 90 = 945\), so there are at most \(945\) possible sums (holes). By the pigeonhole principle, there must be two subsets that share the same sum, and we can remove any elements common to those two subsets to get disjoint subsets with the same sum.

Any single person could have \[ 0\quad\text{or}\quad 1\quad\text{or}\quad 2\quad\text{or}\quad \dots\quad\text{or}\quad n\!-\!1 \] friends in the group; there are \(n\) possibilities. Notice though, that if a person has \(0\) friends in the group, there cannot be someone else with \(n-1\) friends in the group because they would have to be friends with the first person, contradicting the assumption that the first person had \(0\) friends. Similarly, if someone in the group has \(n-1\) friends, there cannot be someone in the group with \(0\) friends. Therefore there are really only \(n-1\) possibilities for the number of friends each person can have in the group. These \(n-1\) possibilities are our holes, and the \(n\) people are actually pigeons. By the pigeonhole principle, two of the people must have the same number of friends in the group.

Select one person at the party and consider their relationship to the other five. By the pigeonhole principle this person must either be good friends or total strangers with at least three of those other five people. Without loss of generality, suppose they are good friends with at least three others.

If any two of those three others are friends with each other, we have a trio of mutually good friends. Otherwise those three others are all mutually total strangers. In either case we’ve shown what we must.

The points are your pigeons, but you must design the holes yourself. Maybe the fact that \(17\) is one more than a square is a hint?

Partition the \(1"\times 1"\) square into sixteen \(\frac{1}{4}"\times\frac{1}{4}"\) squares in the natural “checkerboard” fashion, and notice that the diagonal of one of these squares, i.e. the longest distance between any two points inside one of these squares, is exactly \(\sqrt{2}/4\). These sixteen squares are our holes. Since there are \(17\) points, one square must contain at least two points, and so they must be within \(\sqrt{2}/4\) of each other.