The tutor attempts to strip the pigeonhole principle to bare wires with a simple problem.

I discussed the pigeonhole principle in my May 23/14 and Oct 29/14 posts. The concept is that, with n+1 pigeons going to n pigeonholes, one hole must host at least two pigeons. Apparently simple, the concept can be used to solve some surprising problems.

Example:

Imagine selecting a set of seven numbers from the Naturals {1,2,…,10}. Prove that, among those chosen, one of the numbers must exceed another by exactly 3.

Proof:

Consider the numbers chosen:

1 ≤ x₁ < x₂ < x₃ < …< x₇ ≤ 10

Next, add three to each of the numbers chosen:

x₁ +3 < x₂+3 < x₃+3 <….< x₇+3 ≤ 13

Both are sets of distinct numbers. If the second set and the first are disjoint (have no common members), then the sets together total 14 distinct numbers. These are the pigeons.

However, neither set of numbers can have values outside {1,2,…,13}. These possible values are the pigeonholes.

With 14 numbers, but only 13 possible values, one of the numbers from the second set must share the same value as one in the first. Therefore, x_i+3=x_m for some i, m. By the pigeonhole principle, one of the original set’s members, with three added, equals another of its members.

Source:

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-
  Wesley, 1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.