The Pigeonhole Principle

  1. Lerma

    Prove that every convex polyhedron has at least two faces with the same number of edges.
  2. Cut-the-Knot

    There are 20092009 committees, each with 4545 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.
  3. MIT

    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.
  4. Lerma

    Consider the set S={1,2,,2n}S = \{1,2,\dotsc, 2n\}. Prove that any (n+1)(n+1)-element subset of SS contains two members that are relatively prime.
  5. Lerma

    Consider the set S={1,2,,2n}S = \{1,2,\dotsc, 2n\}. Prove that any (n+1)(n+1)-element subset of SS contains two members such that one is a multiple of the other.
  6. St. Petersburg City Math Olympiad 2001 (P&B)

    In each square of a 10×1010\times 10 checkerboard, a positive integer from the set {2,3,,11}\{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 11. Prove that some number appears at least 1717 times.
  7. MIT

    Let GG be a graph with nn vertices and kk edges, such that the edges are labelled 1,,k1,\dotsc, k in some fashion. Prove that there must exist a path in GG (with repeated vertices allowed) of length at least 2k/n2k/n for which the labels of edges in the path occur in increasing order.
  8. Lerma

    Prove that among any seven real numbers x1,x2,,x7x_1, x_2,\dotsc,x_7, there must be two, xix_i and xjx_j, such that 0    xixj1+xixj    13 0 \;\leq\; \frac{x_i-x_j}{1+x_ix_j} \;\leq\; \frac{1}{\sqrt{3}}
  9. Putnam 2010 A1

    Given a positive integer n,n, what is the largest kk such that the numbers 1,2,,n1,2,\dotsc,n can be put into kk boxes so that the sum of the numbers in each box is the same? [When n=8,n=8, the example {1,2,3,6},{4,8},{5,7}\{1,2,3,6\},\{4,8\},\{5,7\} shows that the largest kk is at least 3.3.]
  10. Putnam 2000 B1

    Let aj,a_j, bj,b_j, cjc_j be integers for 1jN.1 \leq j \leq N. Assume for each j,j, at least one of aj,a_j, bj,b_j, cjc_j is odd. Show that there exist integers r,r, s,s, tt such that raj+sbj+tcjra_j +sb_j +tc_j is odd for at least 4N/74N/7 values of j,j, 1jN.1 \leq j \leq N.
  11. Putnam 2006 B2

    Prove that for every set X={x1,x2,,xn}X = \{x_1,x_2,\dotsc,x_n\} of nn real numbers, there exists a non-empty subset SS of XX and an integer mm such that m+sSs        1n+1. \left|m + \sum_{s \in S}s\right| \;\;\leq\;\;\frac{1}{n+1}\,.
  12. Putnam 2010 B3

    There are 20102010 boxes labeled B1,B2,,B2010B_1, B_2, \dotsc, B_{2010}. For some positive integer nn, a total of 2010n2010n 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 ii and move exactly ii balls from box BiB_i to another box of your choice. For which values of nn is it possible, through a sequence of these moves, to reach the distribution with exactly nn balls in each box regardless of the initial distribution of balls?