XXXV OM - II - Zadanie 3

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Dane są ciągi $(x_1, x_2, \ldots, x_n)$ , $(y_1, y_2, \ldots, y_n)$ o wyrazach dodatnich. Udowodnić, że istnieje taka permutacja $p$ zbioru $\{1, 2, \ldots, n\}$ , że dla każdego rzeczywistego $t$ ciąg

$ (x_{p(1)}+ty_{p(1)}, x_{p(2)}+ty_{p(2)}, \ldots, x_{p(n)}+ty_{p(n)}) $

ma następującą własność: istnieje taka liczba $k$ , że $1 \leq k \leq n$ oraz wszystkie niezerowe wyrazy ciągu o wskaźnikach mniejszych od $k$ są jednakowego znaku i wszystkie niezerowe wyrazy ciągu o wskaźnikach nie mniejszych od $k$ są jednakowego znaku.

Rozwiązanie

Obliczamy ilorazy $\frac{x_1}{y_1}, \frac{x_2}{y_2}, ldots, \frac{x_n}{y_n}$ , znajdujemy takie $j$ , że $\frac{x_j}{y_j}$ jest nie większe od wszystkich pozostałych ilorazów i przyjmujemy $p(1) = j$ . Następnie znajdujemy takie $k$ , że $\frac{x_k}{y_k}$ jest nie większe od wszystkich ilorazów $\frac{x_i}{y_i}$ różnych od $\frac{x_j}{y_j}$ i przyjmujemy $p(2) = k$ itd.

Wobec tego

$ \frac{x_{p(1)}}{y_{p(1)}} \leq \frac{x_{p(2)}}{y_{p(2)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}}. $

Rozważamy dowolną liczbę rzeczywistą $t$ i porównujemy liczbę $- t$ z liczbami $\frac{x_{p(j)}}{y_{p(j)}}$ . Istnieje liczba naturalna $k$ , dla której

$ (*) \qquad \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(k-1)}}{y_{p(k-1)}} \leq-t \leq \frac{x_{p(k)}}{y_{p(k)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}} $

przy czym może być $k = 1$ , tj.

$ -t \leq \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}}, $

albo $k = n +1$ , tj.

$ \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}} \leq -t, $

Z nierówności (*) wynika, że

$ \frac{x_{p(1)}}{y_{p(1)}} +t \leq 0, \ldots, \frac{x_{p(k-1)}}{y_{p(k-1)}} +t\leq 0, \frac{x_{p(k)}}{y_{p(k)}}+t \geq 0,\ldots, \frac{x_{p(n)}}{y_{p(n)}}+t \geq 0, $