文档介绍：(FALL, 2004)
PIGEONHOLE PROBLEMS
Note: Notation such as (78P) means a problem from the 1978 Putnam
Exam.
1. (78P) Let A be any set of 20 distinct integers chosen from the arith­
metic progression 1, 4, 7, . . . , 100. Prove that there must be two distinct
integers in A whose sum is 104. [Actually, 20 can be replaced by 19.]
2. Five points are situated inside an equilateral triangle whose side has
length one unit. Show that two of them may be chosen which are less
than one half unit apart. What if the equilateral triangle is replaced
by a square whose side has length of one unit?
3. (71P) Let there be given nine lattice points (points with integral co­
ordinates) in three dimensional Euclidean space. Show that there is
a lattice point on the interior of one of the line segments joining two
of these points. (Warning. It is easy to misread this problem. Take
time to make sure you understand what is being asked for.) [To test
your understanding, how many lattice points does one need in four
dimensions to reach the same conclusion?]
4. (72IMO) Prove that from a set of ten distinct two-digit numbers (in
the decimal system), it is possible to select two disjoint subsets whose
members have the same sum. [Though not stated in the problem, one
should assume that not both the subsets are empty, or even that neither
of the subsets is empty.]
5. (80P) Let A1, A2, . . . , A1066 be subsets of a finite set X such that Ai >
1 | |
X for 1 i 1066. Prove that there exist ten elements x1, . . . , x10
2 | |
of X such that every Ai contains at least one of x1, . . . , x10. (Here S
means the number of elements in the set S.) | |
6. Given any n+ 2 integers, show that there exist two of them whose sum,
or else whose difference, is divisible by 2n.
7. Given any n + 1 distinct integers between 1 and 2n, show that two
of them are relatively prime. Is this result best possible, ., is the
conclusio