Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Rozważmy liczby rzeczywiste \(a_1,a_2,\ldots,a_n\) (\(n\ge1\)) o średniej arytmetycznej \(A.\) Wówczas:
dla pewnego \(i\) zachodzi nierówność \(a_i\ge A,\) jak również dla pewnego \(j\) zachodzi nierówność \(a_j\le A\);
jeśli wszystkie liczby \(a_1,a_2,\ldots,a_n\) są całkowite nieujemne oraz \(A<1,\) to dla pewnego \(i\) mamy \(a_i=0.\)
Dowód można przeprowadzić ,,w pamięci”, więc go pominę. Poniższe przykłady pokazują te własności w akcji.
Podstawowe pojęcia związane z grafami prostymi Czytelnik znajdzie – jeśli jest taka potrzeba – w kąciku nr 68 (\(\Delta^8_{24}\)). Graf zorientowany to taki, w których każda krawędź ma nadany zwrot od jednego wierzchołka do drugiego. Krawędź \(uv\) grafu zorientowanego można rozumieć jako parę uporządkowaną \((u,v)\); tu nadany jest zwrot od \(u\) do \(v.\) Stosuje się również notację \(u\to v.\) Krawędzie \(uv\) i \(vu\) nie mogą wystąpić jednocześnie. Turniej to graf pełny zorientowany. Ścieżką zorientowaną nazywamy ciąg wierzchołków \(v_1\to v_2\to\ldots\to v_k,\) a jeśli przechodzi ona przez wszystkie wierzchołki, to nazywamy ją (zorientowaną) ścieżką Hamiltona.
Przykład 1 (twierdzenie Szelego). Niech \(n\) będzie liczbą całkowitą dodatnią. Istnieje turniej o \(n\) wierzchołkach, w którym jest co najmniej \(\frac{n!}{2^{n-1}}\) ścieżek Hamiltona.
Rozwiązanie. Rozważmy wszystkie turnieje o wierzchołkach \(v_1,v_2,\ldots,v_n.\) Jest ich \(2^{\binom n2},\) gdyż dla każdego dwuelementowego zbioru wierzchołków musimy zdecydować, czy krawędź między nimi będzie skierowana do wierzchołka o większym indeksie, czy przeciwnie. Ścieżka Hamiltona o kolejnych wierzchołkach \(v_1\to v_2\to \ldots \to v_n\) występuje w \(2^{\binom n2 -(n-1)}\) grafach, gdyż \(n-1\) krawędzi ma ustalony, zgodny ze ścieżką zwrot, a pozostałe krawędzie mogą mieć zwrot dowolny. Możemy to zrobić dla każdej permutacji zbioru wierzchołków, więc łącznie we wszystkich możliwych turniejach jest dokładnie \(n!\cdot2^{\binom n2 -(n-1)}\) ścieżek Hamiltona. Średnia ich liczba jest równa \[\frac{n!\cdot2^{\binom n2 -(n-1)}}{2^{\binom n2}} = \frac{n!}{2^{n-1}},\] więc na mocy własności (1) poszukiwany turniej istnieje.
Przykład 2 (liczby Ramseya). Dla \(m\ge2\) przez \(R(m)\) oznaczamy najmniejszą liczbę naturalną \(n,\) dla której w każdym kolorowaniu krawędzi grafu pełnego o \(n\) wierzchołkach dwoma kolorami otrzymamy jednobarwny graf pełny o \(m\) wierzchołkach. Udowodnić, że \(R(m)>\sqrt[m]{m!}\cdot2^{\frac12m-1}.\)
Rozwiązanie. Niech \(n=R(m).\) Rozważmy wszystkie możliwe kolorowania krawędzi grafu \(K_n\) (pełnego o \(n\) wierzchołkach). Jest ich \(2^{\binom n2}.\) Ustalmy pewien podgraf \(K_m\) tego grafu. Wszystkich kolorowań, w których ten podgraf ma krawędzie w tym samym kolorze, jest \(2\cdot2^{\binom n2 - \binom m2},\) gdyż \(\binom m2\) krawędzi musi być tego samego koloru (jednego lub drugiego), a pozostałe mają kolor dowolny. Wobec tego średnia liczba jednobarwnych podgrafów pełnych na \(m\) wierzchołkach jest równa \[\frac{\binom nm \cdot 2\cdot2^{\binom n2 -\binom m2}}{2^{\binom n2}} = \frac{\binom nm}{2^{\binom m2-1}} \le \frac{n^m/m!}{2^{\binom m2-1}}.\] Z drugiej strony ta średnia jest równa co najmniej \(1,\) gdyż w przeciwnym razie warunek (2) nie byłby spełniony. Otrzymujemy stąd \[n \ge \sqrt[m]{m!\cdot2^{\binom m2-1}} = \sqrt[m]{m!}\cdot 2^{\frac12m-\frac12-\frac1m} \ge \sqrt[m]{m!}\cdot 2^{\frac12m-1}.\]
Zadania
-
Pewien graf ma \(t\) trójkątów. Wykazać, że można pomalować jego krawędzie dwoma kolorami w taki sposób, by liczba jednobarwnych trójkątów nie przekraczała \(\frac14t.\)
Wskazówka Niech \(k\) oznacza liczbę krawędzi tego grafu. Rozważmy wszystkie \(2^k\) ich kolorowań – każdy z trójkątów jest jednobarwny w dokładnie \(2\cdot 2^{k-3}\) z nich. Otrzymujemy stąd średnią liczbę jednobarwnych trójkątów równą \(\frac 14 t.\)
-
Wykazać, że graf o \(k>0\) krawędziach ma podgraf dwudzielny o co najmniej \(\frac 12 k\) krawędziach.
Wskazówka Niech \(V\) będzie zbiorem wierzchołków tego grafu i \(|V|=n.\) Podzielmy zbiór \(V\) na dwa niepuste podzbiory \(A\) i \(B\); dodając do tego wszystkie krawędzie danego grafu łączące \(a\in A\) z \(b\in B,\) otrzymamy podgraf dwudzielny. Aby obliczyć średnią liczbę krawędzi w tak otrzymanym grafie, wystarczy dla każdej z \(k\) krawędzi wyjściowego grafu policzyć liczbę podziałów, przy których będzie ona uwzględniona.
-
(Liczby van der Waerdena) Niech \(W(m)\) oznacza najmniejszą taką liczbę \(n,\) że przy każdym kolorowaniu zbioru \({1,2,\ldots,n}\) dwoma kolorami będziemy mogli z niego wybrać \(m\)-wyrazowy, jednobarwny ciąg arytmetyczny. Udowodnić, że \(W(m)>2^{m/2}.\)
Wskazówka Niech \(n=W(m).\) Aby ułatwić obliczenia, można zauważyć, że rosnący ciąg arytmetyczny jednoznacznie określają dwa pierwsze wyrazy, więc z liczb \(1,2,\ldots,n\) można ich utworzyć nie więcej niż \(\binom n2<\frac 12 n^2.\) Każdy taki \(m\)-wyrazowy ciąg jest jednobarwny w \(2\cdot 2^{n-m}\) kolorowaniach, czyli łączna liczba jednobarwnych ciągów we wszystkich kolorowaniach jest mniejsza niż \(n^2\cdot 2^{n-m}.\) Teraz można obliczyć średnią i skorzystać z tego, że jest ona większa lub równa \(1.\)
-
Dane są wektory \(\vec{v}_1,\vec{v}_2,\ldots,\vec{v}_n,\) każdy o długości \(1.\) Udowodnić, że można tak dobrać \(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n\in\{-1,1\},\) aby zachodziła nierówność \[\left|\varepsilon_1\vec{v}_1+\varepsilon_2\vec{v}_2+\ldots+\varepsilon_n\vec{v}_n\right| \le \sqrt{n}.\]
Wskazówka Przypomnijmy, że kwadrat długości wektora jest równy iloczynowi skalarnemu tego wektora przez siebie. Średni kwadrat długości wektora \(\varepsilon_1\vec{v}_1+\varepsilon_2\vec{v}_2+\ldots+\varepsilon_n\vec{v}_n\) jest równy \(\sum_i\sum_ju_{ij}(\vec{v}_i\circ \vec{v}_j) ,\) gdzie \(u_{ij}\) to średnia wartość iloczynu \(\varepsilon_i\varepsilon_j.\) Nietrudno przekonać się, że dla \(i=j\) mamy \(u_{ij}=1,\) a w przeciwnym przypadku \(u_{ij}=0.\) Oznacza to, że średni kwadrat długości wektora jest równy \(n,\) skąd wynika teza.