Komentarz

XLII OM - II - Zadanie 5

$ P_1, P_2, \ldots, P_n $ są różnymi podzbiorami dwuelementowymi zbioru $ \{1,2,\ldots,n\} $. Zbiory $ P_i $, $ P_j $ dla $ i\neq j $ mają element wspólny wtedy i tylko wtedy, gdy zbiór $ \{i,j\} $ jest jednym ze zbiorów $ P_1, P_2, \ldots, P_n $. Dowieść, że każda z liczb $ 1,2,\ldots,n $ jest elementem wspólnym dokładnie dwóch zbiorów spośród $ P_1, P_2, \ldots, P_n $.

Rozwiązanie

Dla każdego $ k \in \{1,2,\ldots,n\} $ oznaczmy przez $ m_k $ liczbę tych zbiorów $ P_i $, które zawierają element $ k $. Suma tych liczb (gdy $ k $ przebiega wartości od $ 1 $ do $ n $) równa się $ 2n $, bo każdy ze zbiorów $ P_1,\ldots, P_n $ ma dwa elementy, jest więc liczony dwukrotnie. Mamy zatem równość

\[<br /> (1) \qquad \sum_{k=1}^n m_k = 2n.<br /> \]

Należy zaś udowodnić, że $ m_k=2 $ dla $ k = 1, \ldots, n $.

Zgodnie z warunkiem zadania, rozważana rodzina $ n $ zbiorów $ P_1,\ldots, P_n $ składa się dokładnie z tych par $ \{i,j\} $ elementów zbioru $ \{1,2,\ldots,n\} $, dla których zbiory $ P_i $, $ P_j $ mają wspólny element. Tym wspólnym elementem może być dowolna liczba $ k \in \{1,2,\ldots,n\} $. Dla ustalonego $ k $ istnieje $ m_k $ zbiorów $ P_i $ zawierających $ k $; istnieje więc

\[<br /> (2) \qquad \binom{m_k}{2} = \frac{m_k(m_k-1)}{2}<br /> \]

par $ \{ i,j \} $ takich, że $ P_i \cap P_j = \{k\} $. Liczba wszystkich rozważanych par jest sumą wyrażeń (2) gdy $ k $ przebiega wartości od $ 1 $ do $ n $. Ponieważ każda taka para $ \{i,j\} $ jest jednym ze zbiorów $ P_1,\ldots, P_n $, liczba tych par wynosi $ n $. Otrzymujemy równość

\[<br /> n = \sum_{k=1}^n \binom{m_k}{2} = \frac{1}{2} \sum_{k=1}^n m_k(m_k-1),<br /> \]

czyli

\[<br /> \sum_{k=1}^n m_k^2 - \sum_{k=1}^n m_k =2n.<br /> \]

Stąd, wobec (1),

\[<br /> (3) \qquad \sum_{k=1}^n m_k^2 = 4n.<br /> \]

Chcemy dowieść, że wszystkie liczby $ m_k $ równają się $ 2 $. Rozważmy wobec tego różnice $ m_k - 2 $. Obliczmy sumę kwadratów tych różnic, korzystając ze związków (1) i (3):

\[<br /> \sum_{k=1}^n (m_k-2)^2 = \sum_{k=1}^n m_k^2 - 4 \sum_{k=1}^n m_k + 4\sum_{k=1}^n 1 = 4n-8n+4n=0.<br /> \]

Suma liczb nieujemnych równa się zeru tylko wtedy, gdy wszystkie te liczby są zerami. Zatem $ m_1 = \ldots = m_n = 2 $.

To znaczy, że każda liczba $ k \in \{1,2,\ldots,n\} $ należy do dokładnie dwóch
zbiorów $ P_i $. Dowód jest zakończony.

Uwaga 1. Modyfikując przekształcenie zastosowane w końcówce rozwiązania łatwo możemy otrzymać dowód nierówności między {\it średnią arytmetyczną}

\[<br /> A(x_1, \ldots, x_n) = \frac{1}{n} \sum_{k=1}^n x_k<br /> \]

układu liczb $ x_1,\ldots,x_n \geq 0 $ a {\it średnią kwadratową} tych liczb, określoną wzorem

\[<br /> Q(x_1, \ldots, x_n) = \sqrt{\frac{1}{n} \sum_{k=1}^n x_k^2}.<br /> \]

Pisząc krótko $ A $ i $ Q $ zamiast $ A(x_1,\ldots,x_n) $ i $ Q(x_1,\ldots,x_n) $ mamy:

\[<br /> \begin{split}<br /> 0 & \leq \sum_{k=1}^n (x_k - A)^2 =\sum_{k=1}^n x_k^2 - 2A \sum_{k=1}^n x_k + \sum_{k=1}^n A^2=\\<br /> & = nQ^2 - 2A \cdot nA + nA^2 = n(Q^2-A^2) = n(Q+A)(Q-A),<br /> \end{split}<br /> \]

skąd

\[<br /> (4) \qquad Q(x_1, \ldots, x_n) \geq A(x_1, \ldots, x_n);<br /> \]

równość zachodzi tylko dla $ x_1 = \ldots = x_n = A $.

Na odwrót: przyjmując nierówność (4) (wraz z informacją, kiedy przechodzi ona w równość) za fakt znany, możemy dowodzoną tezę ($ m_1 = \ldots = m_n = 2 $) wydedukować natychmiast z wzorów (1) i (3).

Uwaga 2. W tym zadaniu mamy do czynienia z parą $ (V,E) $, gdzie $ V $ jest zbiorem $ \{1,2,\ldots,n\} $, a $ E $ jest rodziną zbiorów dwuelementowych $ P_1,\ldots,P_n $, z których każdy jest zawarty w $ V $. Tego typu konfiguracja tworzy graf. Ogólnie, {\it grafem} nazywamy parę $ (V,E) $, gdzie $ V $ jest dowolnym zbiorem, a $ E $ jest pewną rodziną wyróżnionych dwuelementowych podzbiorów $ V $. (W zastosowaniach najczęściej $ V $ jest zbiorem skończonym.) Wygodnie jest interpretować $ V $ jako pewien zbiór punktów (na płaszczyźnie lub w przestrzeni), a każdy zbiór dwuelementowy $ \{u,v\} $ należący do rodziny $ E $ - jako odcinek łączący punkty $ u $ i $ v $. Taka interpretacja uzasadnia stosowaną w teorii grafów terminologię: elementy zbioru $ V $ nazywa się wierzchołkami rozważanego grafu, a elementy zbioru $ E $ - jego krawędziami (por. zadanie 4 z XXXII Międzynarodowej Olimpiady Matematycznej).

Liczbę krawędzi, których końcem jest ustalony wierzchołek grafu, nazywa się {\it krotnością} tego wierzchołka.

Dwie krawędzie grafu nazywamy przyległymi, jeśli mają wspólny koniec. Dwa wierzchołki grafu nazywamy przyległymi, jeśli łączy je pewna krawędź.

Należy podkreślić, że taka interpretacja ma jedynie ułatwiać wyobrażanie sobie danych zbiorów i ich wzajemnych relacji (o charakterze mnogościowo-kombinatorycznym); nie ma w tym żadnej ,,geometrii''. Abstrahuje się od długości krawędzi i kątów między nimi oraz ich ewentualnych przecięć poza wierzchołkami grafu. Na przykład graf $ (V_1,E_1) $, gdzie $ V_1 $ jest zbiorem wierzchołków kwadratu, a $ E_1 $ składa się z jego trzech boków oraz obu przekątnych, jest nieodróżnialny od grafu $ (V_2, E_2) $, gdzie $ V_2 $ jest zbiorem wierzchołków czworościanu, a $ E_2 $ - zbiorem dowolnych jego pięciu krawędzi.

Twierdzenie podane do udowodnienia w tym zadaniu formułuje się w języku grafów następująco:

Dany jest graf $ (V,E) $, w którym zbiory $ V $ i $ E $ mają jednakową, skończoną liczbę elementów, ponumerowanych liczbami naturalnymi od $ 1 $ do $ n $. Dla każdej pary różnych liczb naturalnych $ i,j \in \{1,2,\ldots,n\} $ wierzchołki o numerach $ i $, $ j $ są przyległe wtedy i tylko wtedy, gdy krawędzie o numerach $ i $, $ j $ są przylegle. Przy tych założeniach krotność każdego wierzchołka wynosi $ 2 $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz