Problem: (1996 Germany – #2) Suppose  is a union of finitely many disjoint subintervals of ![[0, 1]](http://www.wangsblog.com/jeffrey//pictures/0f549f2002f52d04021f554206dea13d.gif "[0, 1]") such that no two points in have distance  . Show that the total length of the intervals comprising is at most  .
Solution: Consider partitioning the interval ![[0,1]](http://www.wangsblog.com/jeffrey//pictures/b8856e134afcc03f0221e2994b0559f6.gif "[0,1]") into the pairs
for  with  . By the given condition, we can have at most one value from each of these pairs so at most half of the total length, and since the total length of the interval is  , the maximum length of  is . QED.
——————–
Comment: Sort of an easy problem for a national olympiad, but a good exercise in sets and intervals. The hardest part about these problems is usually finding a way to prove it rigorously, instead of intuitively.
——————–
Practice Problem: Prove that given  real numbers in the interval  , there exist two such that the absolute value of their difference is at most  .
Leave a Reply
You must be logged in to post a comment.
|
March 18th, 2006 at 2:03 am
Proof 1: Pidgeonhole.
Proof 2: Suppose that there do not exist two such numbers. Arrange them in increasing order as the sequence a_n. The successive difference from each a_k to each a_{k+1} must be greater than 1/(n-1), and there are (n-1) such successive pairs; hence, the interval must have length greater than 1. Contradiction.
August 22nd, 2007 at 12:13 am
Yahoo Database
How add your blog to yahoo database?