Let T be the set {3, 4, 5, 6, 7, 8, 9, 10} and suppose five integers are chosen from T. Must two of these integers have the property that the difference of the larger minus the smaller equals 2? Why or why not? Write an answer that would convince a good but skeptical fellow student who has learned the statement of the pigeonhole principle but not seen an application like this one. Either describe the pigeons, the pigeonholes, and how the pigeons get to the pigeonholes, or describe a function by giving its domain, co-domain, and how elements of the domain are related to elements of the co-domain.

Question

What will be an ideal response?

Answer 1

Yes.
Solution 1 : Yes. Partition the set T into the following six subsets:
{3, 5}, {4, 6}, {7, 9}, {8, 10}.
These subsets have three important properties: (1) within each subset, the larger number minus the smaller number equals 2, (2) every number in T is in one of the subsets, and (3) no number in T is in more than one subset. Think of the five chosen numbers as the pigeons and the four subsets as the pigeonholes, and imagine that each pigeon (number) flies into the pigeonhole (subset) that contains that number. By the pigeonhole principle, two pigeons (numbers) must fly into the same pigeonhole. But that means that two of the five numbers are in the same subset, which means that the difference of the larger number minus the smaller one is 2.
Solution 2 : Yes. Partition the set T into the following four subsets:
{3, 5}, {4, 6}, {7, 9}, {8, 10}.
These subsets have three important properties: (1) within each subset, the larger number minus the smaller number equals 2, (2) every number in T is in one of the subsets, and (3) no number in T is in more than one subset. Define a function f from the set of the five chosen numbers to the four subsets of the partition by the rule: to each number x associate the subset containing that number. By the pigeonhole principle, f is not one-to-one, so two numbers belong to the same subset. But within each subset, the difference of the larger number minus the smaller one is 2.So at least two numbers out of the five have the property that the larger minus the smaller is 2.