problem 3 fall 2011 of purdue POW

To solve problem 3, the pigeonhole principle should be knew first. The pigeonhole principle states that if n items put into m pigeonholes with n>m, then there is at least one pigeonhole must contain more than one item. In Chinese version is called 抽屜原理( drawer principle), which replace the pigeonholes with drawers. Beside this definition, there is another definition such n is greater than k times of m, then there is at least one pigeonhole must contain more than k items.

The problem 3 says: There are nine points in the interior of a cube of side 1. Show that at least two of the points are less than sqrt(3)/2. Can sqrt(3)/2 be replaced by a smaller number?

The idea of how to solve the problem is to set up the pigeonhole, then put the points in to the holes. Since the  side of cube equals to 1, half of the side is 1/2. Then we can cut the cube into 8 small cube with side of 1/2. The diagonal of small cube is just sqrt(3). sqrt((1/2)^2+(1/2)^2+(1/2)^2)=sqrt(3)/2. The distance of any two points in the interior of the small cube is less than sqrt(3). Then we set up 8 pigeonholes. But there are 9 points, so at least one small cube contain more than two point. Then the problem is solved.

The further question is easy, but it is hard to explain with english.

容易知道sqrt(3)/2不可以被更小的數代替，其實最極端的放置方法是：將8個點放在大正方形的四個角，而第九個點就放在大正方形的中心位置，那麼他們的距離就剛好都是sqrt(3)/2。但是全部點都放在正方形內部（interior），所以如果sqrt(3)/2換成比sqrt(3)/2的數d，至少有一種方法可以使全部點兩兩之間的距離小於d。