XLI OM - II - Zadanie 5

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Danych jest $n$ liczb naturalnych ( $n\geq 2$ ), których suma równa jest ich iloczynowi. Wykazać, że ta wspólna wartość nie przekracza $2n$ .

Rozwiązanie

Jak zwykle, gdy mowa jest o liczbach naturalnych, pojawia się kwestia umowy, czy zero uważamy za liczbę naturalną. W tym zadaniu nie ma to znaczenia: jeśli choć jedna z rozważanych liczb jest zerem, to ich iloczyn także jest zerem i teza jest oczywista.

Gdyby $n -1$ spośród $n$ danych liczb było jedynkami, warunek dany w założeniu nie mógłby być spełniony. W dalszym ciągu będziemy więc rozważać układ $n$ liczb całkowitych dodatnich, wśród których co najmniej dwie są większe od $1$ .

Oznaczmy dane liczby przez

$ 1 + x_1, 1 + x_2, \ldots ,1 + x_n, $

przyjmując, że

$ x_1 \geq x_2 \geq \ldots \geq x_n \geq 0, \quad x_2 \geq 1. $

W myśl założenia zachodzi równość

$ (1) \qquad \prod_{i=1}^n (i+x_i) = \sum_{i=1}^n (1+x_i). $

Oznaczmy wspólną wartość lewej i prawej strony (1) przez $s$ . Mamy dowieść, że $s \leq 2n$ .

Gdy $n = 2$ , warunek (1) prowadzi do równania $x_1x_2 = 1$ , czyli $x_1 = x_2 = 1$ . Wówczas $s = 4 = 2n$ ; teza zachodzi.

Dalej zakładamy, że $n \geq 3$ . Prawa strona (1) równa się

$ (2) \qquad s = n + \sum_{i=1}^n x_i. $

Wymnażając czynniki iloczynu znajdującego się po lewej stronie (1) dostajemy sumę składników następującej postaci:

$ \begin{split} (3) \qquad s & = \prod_{i=1}^n (1+x_i) = \\ & = 1 + \sum_{1 \leq i \leq n} x_i + \sum_{1 \leq i < j \leq n} x_i x_j + \sum_{1 \leq i < j < k \leq n} x_i x_j x_k + \ldots \\ & \ldots + (x_1 x_2 \ldots x_n). \end{split} $

Przez przyrównanie prawych stron (2) i (3) otrzymujemy równość

$ \begin{split} (4) \qquad n-1 = \sum_{1 \leq i < j \leq n} x_i x_j + \sum_{1 \leq i < j < k \leq n} & x_i x_j x_k + \ldots \\ & \ldots + (x_1 x_2\ldots x_n). \end{split} $

Rozważymy teraz dwa przypadki.

Przypadek I. $x_3 \geq 1$ .

Oszacujemy z dołu prawą stronę równości (4) opuszczając pewne nieujemne składniki:

$ \begin{split} n-1 & \geq \sum_{1 \leq i < j \leq n} x_ix_j+ \sum_{1 \leq i < j < k \leq n} x_ix_jx_k \geq \\ & \geq x_1x_2 + x_1x_3 + x_2x_3 + \sum_{3 < i\leq n} x_ix_3 + x_1x_2x_3 = \\ & x_1x_2+ x_3 \left( \sum_{i=1}^3 x_i - x_3 + x_1x_2 \right). \end{split} $

Kontynuujemy szacowanie, wykorzystując nierówności $x_1x_2 \geq x_3 \geq 1$ oraz równość (2):

$ n - 1 \geq x_1x_2 + x_3 \cdot \sum_{i=1}^n x_i = x_1x_2 + x_3(s-n) \geq 1+s-n. $

Stąd $s \leq 2n - 2$ , więc tym bardziej $s \leq 2n$ .

Przypadek II. $x_3 = 0$ (czyli $x_i = 0$ dla $i \geq 3$ ).

Warunek (4) przybiera postać

$ (5) \qquad n-1 = x_1x_2 $

(wszystkie pozostałe składniki prawej strony (4) są zerami). Stąd, wobec (2):

$ s = n+x_1+x_2 = n+(x_1x_2-(x_1-1)(x_2-1) + 1) \leq n+x_1x_2 + 1 = 2n. $

Teza jest więc udowodniona.

Uwaga. Równość $s = 2n$ jest możliwa tylko w przypadku II, i to tylko wtedy, gdy $(x_1 - 1)(x_2 -1) = 0$ , czyli gdy $x_2 = 1$ (bo $x_1 \geq x_2$ ). Wówczas, zgodnie z (5), $x_1 = n-1$ . A zatem równość $s = 2n$ zachodzi tylko dla $(x_1,\ldots, x_n) = (n-1,1,0,\ldots,0)$ - czyli tylko wtedy, gdy jedna spośród danych w zadaniu liczb równa się $n$ , jedna równa się $2$ , a pozostałe są jedynkami.