Homework IV

Due Oct. 14th


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. To remind you again, it is the following simple theorem:

 

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 just by using a proof using contradiction, i.e. assume the conclusion is false and get a contradiction.

 

 

  1. Prove that for any set of five points in the interior of a square of side length one, there is at least one pair of points whose distance is less than (√2)/2.
  2. Given any subset of the set {1, 2, …, 99} with at least ten elements, show that there are two disjoint nonempty subsets of the set with equal sum of their elements. (Hint: Consider how many different subsets this set has and then what are the possible values for sum of elements of any such subset. Use this to find just two subsets with the described property and then use them to find two disjoint one.)
  3. Let X be a real number, prove that among the numbers X, 2X, …, (n-1)X, there is one that differs from an integer by at most 1/n.
  4. Given five lattice points in the plane, any point whose coordinates are both integers, show that the mid point of one of the segments joining two of these points is a lattice point too. (Hint: Consider different cases for parity of coordinates of the points.)
  5. In a party, twenty five men and twenty five women are seated around a round table. Show that there must be at least one person at the table who is seated between two men.
  6. An arrangement of squares as shown is called a trimino. Given an 8×8 checkerboard, what is the maximum number of squares that you can color green such that it makes no trimino all green? (Hint: Here there are two parts, first that you should show a coloring of the board without any colored trimino and then you should be able to show that in any such coloring the number of colored squares cannot be more than the one you have described. To get some idea, divide the checkerboard into 16 disjoint 2×2 squares and see what you can say.)

   

  1. A 6×6 checkerboard with 36 squares is covered by 18 dominos. Prove that every such tiling can be cut between some pair of adjacent rows or columns without cutting any domino.