LVI OM - I - Zadanie 4

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

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

$ x_1y_1 +x_2y_2 +\ldots+x_ny_n, $

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

$ (1)\qquad x_{1}+x_{2}+\ldots+x_{n}\leq a,\qquad y_{1}+y_{2}+\ldots+y_{n}\leq b. $

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

$ \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. $

Zatem

$ (2)\qquad x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq\min(a,b,n). $

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

$ x_{1}=x_{2}=\ldots=x_{A}=1,\ x_{A+1}=a-A,\ x_{i}=0\textrm{ dla }i>A+1; $

$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

$ x_{1}=x_{2}=\ldots=x_{A}=1,\ x_{A+1}=a-A,\ x_{i}=0\textrm{ dla }i>A+1; $

$ y_{1}=y_{2}=\ldots=y_{A}=1,\ y_{A+1}=b-A,\ y_{i}=0\textrm{ dla }i>A+1. $

Pozostało zatem wykazać, że

$ (3)\qquad x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq A+(a-A)(b-A). $

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

$ x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq A\leq A+(a-A)(b-A). $

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

$ A<x_{1}+x_{2}+\ldots+x_{n}\leq a \ \textrm{oraz} \ A<y_{1}+y_{2}+\ldots+y_{n}\leq b. $

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

$ x_k'=x_k-\delta,\ x_l'=x_l+\delta,\ x_i'=x_i\ \textrm{dla}\ i \neq k,l. $

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

$ \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. $

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ść

$ 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}. $

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

$ 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}. $

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

$ (4)\qquad A<a_{1}+a_{2}+\ldots+a_{n}\leq a \ \textrm{oraz} \ A<b_{1}+b_{2}+\ldots+b_{n}\leq b $

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.

$ (a_{i}'-a_{j}')(b_{i}-b_{j})\geq 0\ \textrm{dla wszystkich}\ 1\leq i,j\leq n. $

Wówczas zachodzi nierówność

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

(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

$ a_{i}'=b_{i}=1 \textrm{ dla } i<A+1 \textrm{ oraz } a_{i}'=b_{i}=0 \textrm{ dla }i>A+1, $

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

$ \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), $

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

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

$ \left\{ \begin{array}{ll} \min(a,b,n),&\textrm{ jeśli } a,b\geq n \textrm{ lub } [a]\neq[b]; \\ {}[a]+(a-[a])(b-[a]),& \textrm{ jeśli } [a]=[b]<n. \end{array}\right. $