Pigeon Hole Problems [August, 2005]

1. Let u be an irrational real number. Let S be the set of all real numbers of the form a+bu, where a and b are integers. Show that S is dense in the real numbers, i.e., for any real number x, and any e > 0, there is any element y in S such that |x-y| < e. ( Hint: first try x=0.)
2. If F is a family of subsets of {1,2, …, n} such that the intersection of A and B is not empty for any A, B in F, then |F| £ 2^n-1. Find a family F of 2^n-1 subsets that satisfies the previous condition.
3. A lattice point in the plane is a point (x,y) such that both x and y are integers. Find the smallest number n such that given n lattice points in the plane, there exist two whose midpoint is also a lattice point.
4. The points of an infinite rectangular grid are colored with two colours. Show that there are two horizontal and two vertical lines with points at their intersection coloured with the same colour.
5. Prove that there exist integers a,b,c not all zero and each of absolute value less than one million, such that | a + b(2^1/2) +c(3^1/2)| < 10^-11.