Difference between revisions of "Pigeonhole Principle"
Etmetalakret (talk | contribs) (Added a few introductory problems) |
Etmetalakret (talk | contribs) m (Slight change in example 1 to aid a new reader) |
||
Line 18: | Line 18: | ||
'''Solution''': Intuitively, you might realize that after we select four socks of different colors (one red, one blue, one yellow, and one black), the Martian can't select a fifth sock without creating a pair. We may use this to prove the problem: | '''Solution''': Intuitively, you might realize that after we select four socks of different colors (one red, one blue, one yellow, and one black), the Martian can't select a fifth sock without creating a pair. We may use this to prove the problem: | ||
− | Note that the Martian may select <math>4</math> socks without a pair: one red, one blue, one yellow, and one black sock. However, if the Martian selects <math>5</math> socks from <math>4</math> colors, <math>2</math> socks must have the same color. Therefore, <math>5</math> | + | Note that the Martian may select <math>4</math> socks without a pair: one red, one blue, one yellow, and one black sock. However, if the Martian selects <math>5</math> socks from <math>4</math> colors, the pigeonhole principle guarantees that <math>2</math> socks must have the same color (where the <math>5</math> socks are "pigeons" and the <math>4</math> colors are "holes"). Therefore, <math>5</math> is the minimum number of socks they must draw to guarantee a pair. <math>\square</math> |
=== Example 2 === | === Example 2 === |
Revision as of 16:52, 20 January 2023
In combinatorics, the pigeonhole principle states that if or more pigeons are placed into
holes, one hole must contain two or more pigeons. This seemingly trivial statement may be used with remarkable creativity to generate striking counting arguments, especially in Olympiad settings.
In older texts, the principle may be referred to as the Dirichlet box principle. A common phrasing of the principle uses balls and boxes and is that if balls are to be placed in
boxes and
, then at least one box must contain more than one ball.
Contents
Proof
An intuitive proof of the pigeonhole principle is as follows: suppose for contradiction that there exists a way to place balls into
boxes where
such that all boxes contain at most one ball.
Let how many balls each box contains. Our condition that all boxes contain at most one ball implies that
for all
, so
However, we know that there are a total of
balls across all our boxes, so this sum must equal
:
Therefore,
. This contradicts our definition that
. Therefore, our assumption must be incorrect; at least one box must contain two or more balls.
In formal terms, the pigeonhole principle is a consequence of how one set is defined to be larger than another set.
Let be a set of
balls and
be a set of
boxes such that
. The definition that
(as in our problem) is that there exists a surjective mapping from
to
, but not an injection. In other words, there exists a way to map every ball of
to every box of
, but it does not hold that if the boxes of two balls are the same, then the balls must be the same. That is to say, there must be two or more balls in the same box—which is the pigeonhole principle.
Introductory Examples
Example 1
If a Martian has an infinite number of red, blue, yellow, and black socks in a drawer, what is the minimum number of socks that the Martian must pull out of the drawer to guarantee they have a pair?
Solution: Intuitively, you might realize that after we select four socks of different colors (one red, one blue, one yellow, and one black), the Martian can't select a fifth sock without creating a pair. We may use this to prove the problem:
Note that the Martian may select socks without a pair: one red, one blue, one yellow, and one black sock. However, if the Martian selects
socks from
colors, the pigeonhole principle guarantees that
socks must have the same color (where the
socks are "pigeons" and the
colors are "holes"). Therefore,
is the minimum number of socks they must draw to guarantee a pair.
Example 2
Suppose is a set of
integers. Prove that there exists distinct
in
such that
is a multiple of
.
Solution: Note that for any such and
,
We may rewrite this in modular arithmetic as
Therefore, we wish to show that there exist
and
with the same remainder modulo n. Note that there are
integers in
and
possible remainders (namely,
) modulo
. Then by the pigeonhole principle, there exist two integers with the same remainder modulo
. As shown earlier, this implies that their difference is a multiple of
, as required.
Intermediate Problems
- Show that in any group of
people, there are two who have an identical number of friends within the group. (Solution)
(Mathematical Circles) - Six distinct positive integers are randomly chosen between 1 and 2006, inclusive. What is the probability that some pair of these integers has a difference that is a multiple of 5? (Solution)
- Show that for any irrational
and positive integer
, there exists a rational number
with
such that
(Solution)
(the classical Rational Approximation Theorem)
Olympiad Problems
- Seven line segments, with lengths no greater than 10 inches, and no shorter than 1 inch, are given. Show that one can choose three of them to represent the sides of a triangle. (Solution) (Manhattan Mathematical Olympiad 2004)
- Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7. (Solution) (Manhattan Mathematical Olympiad 2005)
- Prove that from any set of one hundred whole numbers, one can choose either one number which is divisible by 100, or several numbers whose sum is divisible by 100. (Solution) (Manhattan Mathematical Olympiad 2003)
- Prove that among any ten points located inside a circle with diameter 5, there exist at least two at a distance less than 2 from each other. (Solution) (Japan 1997)
- Every point in a plane is either red, green, or blue. Prove that there exists a rectangle in the plane such that all of its vertices are the same color. (Solution) (USAMTS Year 18 - Round 1 - Problem 4)
- There are 51 senators in a senate. The senate needs to be divided into
committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does 'not' necessarily hate senator A.) Find the smallest
such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee. (Solution)
(Red MOP lecture 2006)