XVIII ZMPB - Zadanie 1

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

\[<br /> {1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}<1.<br /> \]

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

\[<br /> \{1,2,\ldots,2n\}=\{1,2\}\cup\{3,4\}\cup\ldots\cup\{2n-1,2n\}. (1) \qquad<br /> \]

Rozpatrzmy w tym celu dowolne inne rozbicie

0

\[<br /> \{1,2,\ldots,2n\}=P_1\cup P_2\cup\ldots\cup P_n,<br /> \]

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

\[<br /> P_1=\{2k-1,a\},\qquad P_2=\{2k,b\},<br /> \]

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

\[<br /> P_1'=\{2k-1,2k\},\qquad P_2'=\{a,b\}.<br /> \]

Wówczas rozbiciom

\[<br /> (2) \qquad P_1\cup P_2\cup P_3\cup\ldots\cup P_n\quad\hbox{oraz}\quad<br /> P_1'\cup P_2'\cup P_3\cup\ldots\cup P_n<br /> \]

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

\[<br /> {1\over (2k-1)a}+{1\over 2k\cdot b}+{1\over p_3}+\ldots+{1\over p_n}<br /> \quad\hbox{oraz}\quad<br /> {1\over (2k-1)\cdot 2k}+{1\over ab}+{1\over p_3}+\ldots+{1\over p_n}.<br /> \]

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

\[<br /> {1\over (2k-1)\cdot 2k}+{1\over ab}-{1\over (2k-1)a}-{1\over 2k\cdot b}=<br /> {(a-2k)(b-(2k-1))\over(2k-1)2kab}>0.<br /> \]

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

\[<br /> {1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}\le<br /> {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n}.<br /> \]

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

\[<br /> {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n}<1.<br /> \]

Zauważmy w tym celu, że

\[<br /> {1\over m(m+1)}={1\over m}-{1\over m+1}<br /> \]

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

\[<br /> \begin{split}<br /> {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n}<br /> &\le7{1\over 1\cdot 2}+{1\over 2\cdot 3}+\ldots+{1\over n(n+1)}= \\<br /> &= 1-{1\over 2}+{1\over 2}-{1\over 3}+\ldots+{1\over n}-{1\over n+1}= \\<br /> &= 1-{1\over n+1}<1.<br /> \end{split}<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź