If you stuff \(n\) pigeons into \(k\) holes
(as one often does), and if \(n \gt k\),
then one of the holes must contain more than one pigeon.
-
Prove that every convex polyhedron
has at least two faces with the same number of edges.
-
There are \(2009\) committees, each with \(45\) members,
any two of which have exactly one person in common.
Show that there is one person who is a member of all the committees.
-
Consider an equilateral triangle having side-lengths one inch,
and any set of five points on the interior of that triangle.
Show that two of those points must be within one-half inch of each other.
-
Recall that a regular icosahedron is a convex polyhedron
having 12 vertices and 20 faces;
the faces are congruent equilateral triangles.
On each face of a regular icosahedron is written a nonnegative integer
such that the sum of all 20 integers is 39. Show that there are
two faces that share a vertex and have the same integer written on them.
-
Consider the set \(S = \{1,2,\dotsc, 2n\}\).
-
Prove that any \((n+1)\)-element subset of \(S\)
contains two members that are relatively prime.
-
Prove that any \((n+1)\)-element subset of \(S\)
contains two members such that one is a multiple of the other.
-
St. Petersburg City Math Olympiad 2001 (P&B)
In each square of a \(10\times 10\) checkerboard,
a positive integer from the set \(\{2,3,\dotsc,11\}\) is written
in such a way that any two numbers that appear
in adjacent or diagonally adjacent squares of the board
don’t share a common factor greater than \(1\).
Prove that some number appears at least \(17\) times.
-
Let \(G\) be a graph with \(n\) vertices and \(k\) edges,
such that the edges are labelled \(1,\dotsc, k\) in some fashion.
Prove that there must exist a path in \(G\) (with repeated vertices allowed)
of length at least \(2k/n\) for which the labels of edges
in the path occur in increasing order.
-
Prove that among any seven real numbers \(x_1, x_2,\dotsc,x_7\),
there must be two, \(x_i\) and \(x_j\), such that
\[ 0 \;\leq\; \frac{x_i-x_j}{1+x_ix_j} \;\leq\; \frac{1}{\sqrt{3}} \]
-
Prove that for every set \(X = \{x_1,x_2,\dotsc,x_n\}\)
of \(n\) real numbers, there exists a non-empty subset \(S\) of \(X\)
and an integer \(m\) such that
\[ \left|m + \sum_{s \in S}s\right| \;\;\leq\;\;\frac{1}{n+1}\,. \]
-
There are \(2010\) boxes labeled \(B_1, B_2, \dotsc, B_{2010}\).
For some positive integer \(n\), a total of \(2010n\) balls
have been distributed among the boxes in some way.
You may redistribute the balls by a sequence of moves of this form:
choose an \(i\) and move exactly \(i\) balls
from box \(B_i\) to another box of your choice.
For which values of \(n\) is it possible,
through a sequence of these moves,
to reach the distribution with exactly \(n\) balls in each box
regardless of the initial distribution of balls?