Consider in the plane a finite set of segments such that the sum of their lengths is less than $\sqrt{2}$. Prove that there exists an infinite unit square grid covering the plane such that the lines defining the grid do not intersect any of the segments. Vasile Pop
Problem
Source: Romania TST 1998
Tags: analytic geometry, trigonometry, function, combinatorics proposed, combinatorics
13.05.2012 22:31
Lemma: Given segments on the number line such that the sum of their lengths is less than $\sqrt 2$, we can label the integers on the number line on intervals of length $1$ such that no part of a segment is labeled. Proof: Assume the contrary. We set a starting point for the integer $0$, and from that starting point we translate the intervals a length $1$. (Note that our intervals are still distinct in each translated position). Then the sum of all the segment lengths that have been overlapped with an integer on the number line must be 1, so the segments have length sum at least 1, a contradiction. Assume that there are $k$ total segments. Let the have lengths $l_1, l_2, \cdots l_k$. For a given orientation $O$ of the coordinate plane, let $x_1(O) \cdots x_k(O)$ and $y_1(O) \cdots y_k(O)$ denote the lengths $x$ and $y$ components of the segments, respectively. Let $\displaystyle S_x(O) = \sum_{i = 1}^{k} x_i(O)$ and $\displaystyle S_y(O) = \sum_{i = 1}^{k} y_i(O)$. By Cauchy-Schwarz, $x_i(O) + y_i(O) \le \sqrt {2(x_i(O)^2 + y_i(O)^2)} = l_i \sqrt 2$. Therefore, \[ \begin {align*} S_x(O) + S_y(O) \le \sum_{i = 1}^{k} l_i \sqrt 2 < \sqrt 2 \cdot \sqrt 2 = 2 \end {align*} \] Note that we can also write $x_i(O) = l_i |\cos (\theta + \alpha_i)|$ for fixed $\alpha_i$. Similarly, $y_i (O) = l_i |\sin (\theta + \alpha_i)| = l_i |\cos (\theta + 3\pi + \alpha_i)|$. If for a given $O$, $S_x(O) < 1$ and $S_y(O) < 1$, then by the lemma we can fix the $x$ and $y$ coordinate lines to not overlap with any of the segments. Or else, if $S_x(O) < 1$ and $S_y(O) > 1$, since $S_x(O)$ is a continuous function of $\theta$, and $S_y(O)$ is the same function of $\theta$, there exists a value of $\theta$ such that $S_x(O) = 1$. This means that since $S_x(O) + S_y(O) < 2$, we can again use continuity to find a value of $\theta$ such that $S_x(O) < 1$ and $S_y(O) < 1$, and apply to lemma to fix the $x$-coordinate lines and $y$-coordinate lines for the desired result.
04.01.2016 17:55
Firstly, it's no need to change the $sin$ to $cos$. They should remain as they are. Secondly, we use continuity to prove that $f(x)=g(x)$, for some $x$ from the interval $\bigg[0,\frac{\pi}{2}\bigg]$ and from $f(x)+g(x)<2$ it immediately follows that $f(x)<1$ and $f(y)<1$ and then just apply the "Lemma" and finish the problem. $$\odot$$