Problem Set 4 : Pigeonhole Principle

Due 02/24/04




   As usual, think about all problems, and come up with some ideas about how to solve them. If you want you can write them. Then choose two of the problems and write up a careful solution. Your solution should be convincing for a skeptical classmate.

  All of the problems are related to the Pigeonhole Principle, discussed in class. A stronger version of the same principle can be formulated in the following way:

   Theorem: If kn+1 objects (k>0) are distributed among n boxes, one of the boxes will contain at least k+1 objects.

   For most of the problems, without referring directly to this theorem, you can argue a proof using contradiction, i.e. assume the conclusion is false and get a contradiction.
  1.   A point (x,y) in the plane in called a lattice point if both coordinates x and y are integers (positive, negative, or 0). Suppose that we have 5 non-collinear lattice points ( there are no three points on the same line) and we connect them two by two by straight line segments. Prove that one of the resulting line segment must contain another lattice point. (Hint : Look at the midpoints of these segments.)


  2.  A certain dorm has 25 people in it.
    (a)  You are told that each person in the dorm has at least one friend in the dorm. If no one is regarded as being their own friend, show that in this dorm there are two people who have the an identical number of friends in the dorm.
    (b)  There are four kitchens in the dorm, and each person is randomly assigned to a kitchen . Show that there is a group of 7 people who are assigned to the same kitchen.               


  3.   Fifty-one trees are planted inside a square field with sides of length 100 feet. Show that some set of 3 of these trees must be contained in a square with sides of length 20 feet.


  4.   Given any ten integers, show that there is a pair of these integers whose difference is divisible by 9.


  5.   Given any set of 11 natural numbers between 1 and 20 ( inclusive), show that at least one of the members of the set must divide another member of the set.
    (Hint : Note that each natural number can be written as a power of 2 times an odd number; for example , 8=23x1, 12=22x3, and 15=20x15. Apply this fact on each of the given 11 numbers.)


  6.   A six by six checkerboard with 3 squares can be cover exactly by 18 dominoes consisting of two squares each. Prove that there you can cut the board between some pair of adjacent rows or adjacent columns without cutting any dominoes.