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.

  1. 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.
     
  2. 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.
     
  3. 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.
     
  4. 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.
     
  5. 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.
     
  6. 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).
     
  7. 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.
     
  8. 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.