Thursday, March 16, 2006

Itty Bitty Intervals. Topic: Algebra/Sets. Level: Olympiad.

Problem: (1996 Germany - #2) Suppose $S$ is a union of finitely many disjoint subintervals of $ [0, 1] $ such that no two points in $S$ have distance $ \frac{1}{10} $. Show that the total length of the intervals comprising $S$ is at most $ \frac{1}{2} $.

Solution: Consider partitioning the interval $ [0,1] $ into the pairs

$ \{\alpha, \alpha+\frac{1}{10}\} $

for $ \frac{k}{5} \le \alpha \le \frac{k}{5}+\frac{1}{10} $ with $ 0 \le k \le 4 $. 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 $ 1 $, the maximum length of $ S $ is $ \frac{1}{2} $. 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 $ n $ real numbers in the interval $ [0,1) $, there exist two such that the absolute value of their difference is at most $ \frac{1}{n-1} $.


  1. 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.

  2. Yahoo Database

    How add your blog to yahoo database?