Quiz (sort of) with Answers
Pigeonhole Principle
CS 280 - Spring 2002
Some of these problems are from Mathematical Circles (Russian Experience)
by Dmitri Fomin, Sergey Genkin, and Ilia Itenberg.
- There are 20 points within a 3-meter square. Show that some set of three
of these points can be covered by a 1-meter square.
Divide the 3-meter square into 9 one-meter squares (like a Tic-Tac-Toe
board). If each of these 9 square holds just two (or fewer) points
then there are at most 18 points. But since we know there are 20, at
least one of the 9 one-meter squares must hold 3 or more points.
- Prove there exist two powers of 2 that differ by a multiple of 7777.
Consider these powers of 2: 20, 21, 23,
..., 27777 and consider their remainders (mod 7777). The
list consists of 7778 items, but there are just 7777 possible
remainders. Thus, by the Pigeonhole Principle, there must be two
powers of 2 in the list that have the same remainder (mod 7777). Their
difference will be congruent to 0 (mod 7777) and thus is divisible by 7777.
- Prove there is a number consisting entirely of ones that is divisible by
7777.
Consider the following list of number made up entirely of ones: 1, 11,
111, 1111,..., "1 repeated 7778 times" and consider their
remainders (mod 7777). The list consists of 7778 items, but there are
just 7777 possible remainders. Thus, by the Pigeonhole Principle,
there must be two items in the list that have the same remainder (mod
7777). Their difference will be congruent to 0 (mod 7777) and thus
divisible by 7777. Note that the difference looks like several ones
followed by several zeros. Now consider what happens when we divide by
10. This removes one zero from the end of the number, but does not
change the fact that 7777 divides the number. This is because 7777
contains no factors of 2 or 5. We can continue removing zeros in this
way to get a final number, consisting entirely of ones, that is divisible by
7777.
- 15 students take a quiz. Their scores sum to 100. Prove that there are two
students that have the same score.
Suppose the scores are all different. Then we can arrange them in
order s1< s2< ...< s15.
Observe that the smallest possible values here would be s1=0, s2=1,
s3=2, ..., s15=14. If we add these scores, we
get (14)(15)/2 = 105. This is a contradiction since the scores are
supposed to sum to 100. Thus, the scores cannot be all different.
- A 10 by 10 table is filled in with positive integers so that adjacent
integers (i.e., integers are adjacent if their squares share a side) differ
by 5 or less. Show that the table must contain two identical integers.
Consider the smallest number in the table and the largest number in the
table. Wherever these are in the table, there is a path from lowest to
highest moving from square to adjacent square of length at most 19.
The value in a square can jump by at most 5 when you move from square to
adjacent square. Thus, moving from lowest to highest, the value jumps
by at most 19*5 = 95. Since there are 100 squares and at most 96
values, by the Pigeonhole Principle, there must be some value that appears
in more than one square.
- Show that among 5 people at a dinner table, there are two that have an
identical number of friends among those at the table.
There seem to be 5 people and 5 categories (0 friends, 1 friend, 2
friends, 3 friends, and 4 friends), so it's hard to see how to use the
Pigeonhole Principle. Observe though that if there is a person with 4
friends then there can be no one with zero friends. Thus, there are
two cases: (1) either no one has 4 friends (in which case there are 5 people
and 4 categories and the Pigeonhole Principle applies) or (2) someone has 4
friends (in which case there are 5 people and 4 categories --- because zero
is not used --- and the Pigeonhole Principle applies).
- Given 8 different positive integers, all < 15, show there are at least
3 pairs that have the same positive difference.
There are C(8, 2) = 28 possible pairs of numbers and there are 14
possible differences (1, 2, ..., 14), so the Pigeonhole Principle doesn't
seem to work. Observe though that there is only one way to make the
difference 14 (the only choice is 15-1); thus the pigeonhole labeled 14 can
have at most one item. This leaves 27 (or 28, if (1, 15) isn't a valid
pair) items to place into 13 pigeonholes. By the Pigeonhole Principle,
there must be a pigeonhole containing 3 pairs.
- Among 6 people, suppose each pair of people are either friends or enemies.
Show that there are 3 people in the group that are either all friends or all
enemies.
This problem appears as an example in the text on page 248.