XVIII ZMPB - Zadanie 1

Zawody matematyczne:

XVIII ZMPB, 2007

Dla dodatniej liczby całkowitej $n$ rozważmy rozbicie zbioru $\{1,2,\ldots,2n\}$ na $n$ podzbiorów dwuelementowych $P_1$ , $P_2$ , $\ldots$ , $P_n$ . W każdym zbiorze $P_i$ niech $p_i$ będzie iloczynem obu elementów zbioru $P_i$ . Udowodnić, że

$ {1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}<1. $

Rozwiązanie

Istnieje tylko skończenie wiele sposobów rozbicia zbioru $\{1,2,\ldots,2n\}$ na $n$ podzbiorów dwuelementowych, więc wśród wszystkich wartości wyrażenia ${1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}$ odpowiadających tym rozbiciom istnieje wartość największa. Udowodnimy, że ta największa wartość odpowiada rozbiciu

$ \{1,2,\ldots,2n\}=\{1,2\}\cup\{3,4\}\cup\ldots\cup\{2n-1,2n\}. (1) \qquad $

Rozpatrzmy w tym celu dowolne inne rozbicie

$ \{1,2,\ldots,2n\}=P_1\cup P_2\cup\ldots\cup P_n, $

Ponieważ jest to rozbicie różne od (1), więc istnieje taka najmniejsza liczba $k\in\{1,2,\ldots,n\}$ , że liczby $2k-1$ i $2k$ nie należą do tego samego zbioru danego rozbicia. Możemy przyjąć, że

$ P_1=\{2k-1,a\},\qquad P_2=\{2k,b\}, $

gdzie liczby $a$ i $b$ są różne i większe od $2k$ . Przyjmijmy

$ P_1'=\{2k-1,2k\},\qquad P_2'=\{a,b\}. $

Wówczas rozbiciom

$ (2) \qquad P_1\cup P_2\cup P_3\cup\ldots\cup P_n\quad\hbox{oraz}\quad P_1'\cup P_2'\cup P_3\cup\ldots\cup P_n $

odpowiadają następujące wartości danego w treści zadania wyrażenia:

$ {1\over (2k-1)a}+{1\over 2k\cdot b}+{1\over p_3}+\ldots+{1\over p_n} \quad\hbox{oraz}\quad {1\over (2k-1)\cdot 2k}+{1\over ab}+{1\over p_3}+\ldots+{1\over p_n}. $

Obliczamy, że różnica dwóch powyższych liczb wynosi

$ {1\over (2k-1)\cdot 2k}+{1\over ab}-{1\over (2k-1)a}-{1\over 2k\cdot b}= {(a-2k)(b-(2k-1))\over(2k-1)2kab}>0. $

Zatem drugiemu z rozbić (2) odpowiada większa wartość wyrażenia. Wynika stąd, że żadnemu rozbiciu różnemu od rozbicia (1) nie może odpowiadać największa wartość wyrażenia ${1\over p_1}+{1 \over p_2}+\ldots+{1\over p_n}$ .

Dowiedliśmy w ten sposób nierówności

$ {1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}\le {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n}. $

Aby dokończyć rozwiązanie, wystarczy sprawdzić, że

$ {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n}<1. $

Zauważmy w tym celu, że

$ {1\over m(m+1)}={1\over m}-{1\over m+1} $

dla dowolnej liczby całkowitej $m\ge 1$ , skąd dostajemy

$ \begin{split} {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n} &\le7{1\over 1\cdot 2}+{1\over 2\cdot 3}+\ldots+{1\over n(n+1)}= \\ &= 1-{1\over 2}+{1\over 2}-{1\over 3}+\ldots+{1\over n}-{1\over n+1}= \\ &= 1-{1\over n+1}<1. \end{split} $