LVI OM - I - Zadanie 4

Dana jest dodatnia liczba całkowita $ n $ oraz dodatnie liczby rzeczywiste $ a $, $ b $. Wyznaczyć największą możliwą wartość sumy

\[<br /> x_1y_1 +x_2y_2 +\ldots+x_ny_n,<br /> \]

gdy $ x_{1},\ x_{2},\ \ldots,\ x_{n},\ y_{1},\ y_{2},\ \ldots,\ y_{n} $ są liczbami z przedziału $ \langle 0;1\rangle $, spełniającymi warunki

\[<br /> (1)\qquad x_{1}+x_{2}+\ldots+x_{n}\leq a,\qquad y_{1}+y_{2}+\ldots+y_{n}\leq b.<br /> \]

Rozwiązanie

Dla dowolnych liczb $ x_{1},\ x_{2},\ \ldots,\ x_{n},\ y_{1},\ y_{2},\ \ldots,\ y_{n} $ spełniających warunki zadania zachodzą nierówności

\[<br /> \sum_{i=1}^{n} x_iy_i\leq n,\qquad \sum_{i=1}^{n} x_iy_i\leq\sum_{i=1}^{n}x_i\leq a,\qquad\sum_{i=1}^{n}x_iy_i\leq\sum_{i=1}^{n}y_i\leq b.<br /> \]

Zatem

\[<br /> (2)\qquad x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq\min(a,b,n).<br /> \]

Wykażemy najpierw, że jeśli $ a,\ b\geq n $ lub $ [a]\neq[b] $ (symbol $ [x] $ oznacza największą liczbę całkowitą nie większą od $ x $), to liczba $ \min(a,b,n) $ jest największą wartością rozpatrywanej sumy.

Jeżeli bowiem $ a, b\geq n $, to przyjmujemy $ x_{i}=y_{i}=1 $ dla $ i=1,2, \ldots, n $. Wówczas nierówności (1) są spełnione, a rozpatrywana suma przyjmuje wartość $ n = \min(a,b,n) $, która — na mocy mocy nierówności (2) — jest jej wartością największą.

W przypadku gdy $ A=[a]\neq[b]=B $, przyjmijmy bez straty ogólności, że $ A<B $. Aby nie rozpatrywać ponownie przypadku $ a, b\geq n $, możemy również założyć, że $ A<n $. Przyjmijmy

\[<br /> x_{1}=x_{2}=\ldots=x_{A}=1,\ x_{A+1}=a-A,\ x_{i}=0\textrm{ dla }i>A+1;<br /> \]
\[y_{1}=y_{2}=\ldots=y_{A+1}=1,\ y_{i}=0\textrm{ dla }i>A+1.\]

Tak wybrane liczby $ x_i, y_i $ należą do przedziału $ \langle 0;1\rangle $, nierówności (1) są dla nich spełnione, a rozpatrywane wyrażenie przyjmuje wartość $ a = \min(a,b,n) $, która — na mocy uzyskanej nierówności (2) — jest wartością największą rozpatrywanej sumy.

Pozostał do rozpatrzenia przypadek $ A = B<n $. Wykażemy, że wówczas największą wartością rozpatrywanej sumy jest liczba $ A+(a-A)(b-A) $, którą można uzyskać przyjmując

\[<br /> x_{1}=x_{2}=\ldots=x_{A}=1,\ x_{A+1}=a-A,\ x_{i}=0\textrm{ dla }i>A+1;<br /> \]
\[<br /> y_{1}=y_{2}=\ldots=y_{A}=1,\ y_{A+1}=b-A,\ y_{i}=0\textrm{ dla }i>A+1.<br /> \]

Pozostało zatem wykazać, że

\[<br /> (3)\qquad x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq A+(a-A)(b-A).<br /> \]

Jeśli $ x_{1}+x_{2}+\ldots+x_{n}\leq A $, to

\[<br /> x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq A\leq A+(a-A)(b-A).<br /> \]

Analogicznie dowodzimy nierówności (3) jeśli $ y_{1}+y_{2}+\ldots+y_{n}\leq A $. Przyjmijmy więc w dalszej części rozumowania, że

\[<br /> A<x_{1}+x_{2}+\ldots+x_{n}\leq a \ \textrm{oraz} \ A<y_{1}+y_{2}+\ldots+y_{n}\leq b.<br /> \]

Przypuśćmy, że pewne dwie liczby $ x_{k},\ x_{l} $ należą do przedziału $ (0;1) $. Bez straty ogólności możemy założyć, że $ y_k \leq y_l $. Zdefiniujmy $ \delta=\min(x_{k}, 1-x_{l}) $ oraz zmodyfikujmy ciąg $ x_1,x_2,\ldots,x_n $ przyjmując

\[<br /> x_k'=x_k-\delta,\ x_l'=x_l+\delta,\ x_i'=x_i\ \textrm{dla}\ i \neq k,l.<br /> \]

Wówczas $ x_{k}'=0 $ lub $ x_{l}'=1 $, liczby $ x_{1}', x_{2}', \ldots, x_{n}' $ należą do przedziału $ \langle 0;1\rangle $, $ x_{1}'+x_{2}'+\ldots+x_{n}'=x_{1}+x_{2}+\ldots+x_{n} $ oraz

\[<br /> \sum_{i=1}^{n}x_{i}'y_i^-\sum_{i=1}^{n}x_iy_i =(x_k-\delta)y_k+(x_l + \delta)y_l - x_ky_k - x_ly_l =\delta(y_l-y_k)\geq 0.<br /> \]

Wykazaliśmy zatem, ze zmodyfikowany ciąg $ x_1', x_2', \ldots, x_n' $ zawiera mniej wyrazów różnych od 0 lub 1 niż wyjściowy ciąg $ x_1, x_2, \ldots, x_n $, a przy tym wartość rozpatrywanej sumy nie zmalała. Jeśli uzyskany ciąg $ x_1', x_2', \ldots, x_n' $ zawiera co najmniej dwa wyrazy różne od 0 lub 1, to modyfikujemy go ponownie zgodnie z opisaną wyżej procedurą Po co najwyżej $ n-1 $ krokach uzyskujemy ciąg $ a_1,a_2, \ldots ,a_n $, który zawiera nie więcej niż jeden wyraz różny od 0 lub 1, a przy tym zachodzi nierówność

\[<br /> x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq a_{1}y_{1}+a_{2}y_{2}+\ldots+a_{n}y_{n}.<br /> \]

Następnie, ustalając liczby $ a_1, a_2, \ldots, a_n $ , przeprowadzamy analogiczną modyfikację ciągu $ y_1, y_2, \ldots, y_n $. W efekcie otrzymujemy ciąg $ b_1,b_2,\ldots,b_n $, który zawiera nie więcej niż jeden wyraz różny od 0 lub 1, a ponadto

\[<br /> a_{1}y_{1}+a_{2}y_{2}+\ldots+a_{n}y_{n}\leq a_{1}b_{1}+a_{2}b_{2}+\ldots+a_{n}b_{n}.<br /> \]

W każdym kroku suma modyfikowanych liczb nie ulega zmianie, więc

\[<br /> (4)\qquad A<a_{1}+a_{2}+\ldots+a_{n}\leq a \ \textrm{oraz} \ A<b_{1}+b_{2}+\ldots+b_{n}\leq b<br /> \]

Niech $ a_{1}', a_{2}', \ldots, a_{n}' $ będzie taką permutacją ciągu $ a_1, a_2, \ldots ,a_n $, że ciągi $ a_1', a_{2}', \ldots, a_{n}' $ oraz $ b_{1}, b_{2}, \ldots, b_{n} $ są jednakowo uporządkowane, tzn.

\[<br /> (a_{i}'-a_{j}')(b_{i}-b_{j})\geq 0\ \textrm{dla wszystkich}\ 1\leq i,j\leq n.<br /> \]

Wówczas zachodzi nierówność

\[<br /> a_1 b_1 + a_2 b_2 + \ldots + a_n b_n \leq a_1'b_1 + a_2' b_2 + \ldots + a_n' b_n.<br /> \]

(zob. Obóz Naukowy Olimpiady Matematycznej, Zwardoń 2003, Dodatek C, str. 38*). Bez straty ogólności przyjmijmy zatem, że $ a_{1}'\geq a_{2}'\geq\ldots\geq a_{n}' $ oraz $ b_{1}\geq b_{2}\geq\ldots\geq b_{n} $. Z nierówności (4) wynika więc, że

\[<br /> a_{i}'=b_{i}=1 \textrm{ dla } i<A+1 \textrm{ oraz } a_{i}'=b_{i}=0 \textrm{ dla }i>A+1,<br /> \]

a ponadto $ a_{p}\leq a-A $ oraz $ b_{p}\leq b-A $ dla $ p=A+1 $. Ostatecznie otrzymujemy

\[<br /> \sum_{i=1}^{n}x_{i}y_{i}\leq\sum_{i=1}^{n}a_{i}'b_{i}=A+a_{p}b_{p}\leq A+(a-A)(b-A),<br /> \]

co kończy dowód nierówności (3).

Reasumując: Największa wartość rozpatrywanego wyrażenia wynosi

\[<br /> \left\{<br /> \begin{array}{ll}<br /> \min(a,b,n),&\textrm{ jeśli } a,b\geq n \textrm{ lub } [a]\neq[b]; \\<br /> {}[a]+(a-[a])(b-[a]),& \textrm{ jeśli } [a]=[b]<n.<br /> \end{array}\right.<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź