Chcemy pokryć krawędzie kliki \(\displaystyle{ G}\) o wielkości \(\displaystyle{ 2n}\) klikami wielkości \(\displaystyle{ n}\).
Na początku próbujemy szacować pałkarsko, zliczając liczby krawędzi: małe kliki mają po \(\displaystyle{ {n \choose 2}}\) krawędzi, duża klika ma \(\displaystyle{ {2n \choose 2}}\) krawędzi, dzieląc jedno przez drugie dostaniemy, że potrzeba przynajmniej \(\displaystyle{ 5}\) małych klik do pokrycia dużej, to nie wystarczy, więc coś jest na rzeczy! Próbujemy bardziej grafowo:
Musi być przynajmniej jedna klika wielkości \(\displaystyle{ n}\), nazwijmy ją \(\displaystyle{ A}\). Niech \(\displaystyle{ B := G \setminus A}\), wtedy \(\displaystyle{ B}\) też składa się z \(\displaystyle{ n}\) wierzchołków. Będziemy teraz chcieli pokryć pełny graf dwudzielny o zbiorach wierzchołków \(\displaystyle{ A}\) i \(\displaystyle{ B}\). Ma on \(\displaystyle{ n^2}\) krawędzi. Klika pokrywająca jakąś krawędź tego grafu dwudzielnego ma \(\displaystyle{ x > 0}\) wierzchołków w \(\displaystyle{ A}\) i \(\displaystyle{ y > 0}\) wierzchołków w \(\displaystyle{ B}\). Pokrywa ona wtedy \(\displaystyle{ x \cdot y}\) krawędzi tego grafu. Ale \(\displaystyle{ x + y = n}\) i \(\displaystyle{ x \cdot y}\) osiąga maksimum w \(\displaystyle{ \frac{n^2}{4}}\) dla \(\displaystyle{ x = y = \frac{n}{2}}\) (to jest prosty fakt, trzeba policzyć maksimum funkcji kwadratowej \(\displaystyle{ f(x) = x(n - x)}\)). Tak więc potrzeba przynajmniej \(\displaystyle{ 4}\) klik aby pokryć wszystkie krawędzie tego grafu dwudzielnego. Jeżeli zużyjemy do tego \(\displaystyle{ 5}\) klik, to łącznie zużyjemy \(\displaystyle{ 6}\) klik i koniec. W przeciwnym przypadku pokrywamy ten graf dwudzielny dokładnie \(\displaystyle{ 4}\) klikami, a każda musi mieć po \(\displaystyle{ \frac{n}{2}}\) wierzchołków w zbiorach \(\displaystyle{ A}\) i \(\displaystyle{ B}\) (i \(\displaystyle{ n}\) musi być parzyste). To znaczy, że każda z nich ma \(\displaystyle{ { \frac{n}{2} \choose 2} = \frac{ \frac{n}{2} \cdot ( \frac{n}{2} - 1)}{2} = \frac{n}{4} \cdot (\frac{n}{2} - 1)}\) krawędzi w \(\displaystyle{ B}\). Czyli łącznie pokrywają co najwyżej \(\displaystyle{ n \cdot (\frac{n}{2} - 1) = \frac{n^2}{2} - n}\) krawędzi w \(\displaystyle{ B}\). Ale \(\displaystyle{ B}\) ma \(\displaystyle{ {n \choose 2} = \frac{n \cdot(n - 1)}{2} =\frac{n^2}{2} - \frac{n}{2}}\) krawędzi, czyli więcej niż mają razem w \(\displaystyle{ B}\) tamte \(\displaystyle{ 4}\) kliki, więc potrzebna jest jeszcze jedna klika do pokrycia \(\displaystyle{ B}\), czyli razem przynajmniej \(\displaystyle{ 6}\), cnd.
3 inaczej:
Bierzemy zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) jak powyżej. Załóżmy nie wprost, że wystarczy \(\displaystyle{ 5}\) małych klik do pokrycia dużej kliki. Bierzemy klikę \(\displaystyle{ A}\), to znaczy że resztę musimy pokryć przy pomocy \(\displaystyle{ 4}\) klik. Wtedy bierzemy dowolny wierzchołek z \(\displaystyle{ A}\). Musi być on połączony z każdym wierzchołkiem z \(\displaystyle{ B}\), a w każdej klice, która pokrywa takie krawędzie musi być on i \(\displaystyle{ n - 1}\) innych wierzchołków, ale \(\displaystyle{ |B| = n}\), czyli potrzeba przynajmniej dwóch klik, które będą pokrywały jego połączenia z \(\displaystyle{ B}\). Tak więc dowolny wierzchołek z \(\displaystyle{ A}\) jest w co najmniej dwóch małych klikach (poza kliką \(\displaystyle{ A}\)). Analogicznie każdy wierzchołek z \(\displaystyle{ B}\) jest w przynajmniej dwóch małych klikach. To znaczy, że łączna krotność występowania wszystkich wierzchołków w małych klikach to przynajmniej \(\displaystyle{ 2n \cdot 2 = 4n}\), ale pozostają nam do użycia tylko \(\displaystyle{ 4}\) kliki, które dają krotność właśnie \(\displaystyle{ 4n}\). To znaczy, że dowolny wierzchołek jest w dokładnie \(\displaystyle{ 2}\) małych klikach (poza \(\displaystyle{ A}\)). Weźmy pewien wierzchołek z \(\displaystyle{ B}\). Jest w dwóch klikach, a w każdej jest połączony z \(\displaystyle{ n - 1}\) wierzchołkami, czyli ma stopień \(\displaystyle{ 2n - 2}\), sprzeczność bo w dużej klice ma stopień \(\displaystyle{ 2n - 1}\), cnd.
3 jeszcze inaczej, najkrócej:
Weźmy dowolny wierzchołek kliki o wielkości \(\displaystyle{ 2n}\). Ma on stopień \(\displaystyle{ 2n - 1}\). W dowolnej małej klice (wycieczce) wielkości \(\displaystyle{ n}\) jest on połączony z \(\displaystyle{ n -1}\) wierzchołkami, czyli musi być w przynajmniej trzech klikach (wycieczkach) aby wszystkie krawędzie były pokryte. To znaczy, że łączna krotność wystąpień \(\displaystyle{ 2n}\) wierzchołków w wycieczkach to przynajmniej \(\displaystyle{ 2n \cdot 3 = 6n}\), ale jedna wycieczka pokrywa tylko \(\displaystyle{ n}\) wierzchołków, czyli wycieczek musi być przynajmniej \(\displaystyle{ 6}\), cnd.
Poza tym:
Dla \(\displaystyle{ n}\) parzystych zawsze \(\displaystyle{ 6}\) klik wielkości \(\displaystyle{ n}\) wystarcza do pokrycia tego grafu: bierzemy dwie rozłączne kliki \(\displaystyle{ A}\) i \(\displaystyle{ B}\) wielkości \(\displaystyle{ n}\) (jak powyżej) i dzielimy te kliki na połowy. Potem parujemy te połowy biorąc jedną połowę z \(\displaystyle{ A}\) i jedną z \(\displaystyle{ B}\), takich par jest \(\displaystyle{ 4}\), dla każdej z tych par dajemy klikę - te \(\displaystyle{ 4}\) kliki pokrywają pełny graf dwudzielny o zbiorach \(\displaystyle{ A}\) i \(\displaystyle{ B}\). Wszystkie pozostałe krawędzie znajdują się wewnątrz klik \(\displaystyle{ A}\) i \(\displaystyle{ B}\) i są już pokryte.
Gdyby było max. \(\displaystyle{ 5}\) wycieczek, pewien uczeń poszedłby na wycieczkę max. \(\displaystyle{ 2}\) razy. Ale wtedy ten uczeń miałby okazję na spotkanie max. \(\displaystyle{ 2n-2}\) uczniów. Sprzeczność.
4:
Oznaczmy \(\displaystyle{ N, S, W, E}\) cztery główne kierunki geograficzne. Przez symetrie wzdłuż osi układu współrzędnych mamy \(\displaystyle{ P(NE)=P(NW)=P(SE)=P(SW)}\), a że zawsze wystąpi dokładnie jedno z tych czterech zdarzeń (poza pomijalnymi przypadkami), to wszystkie te prawdopodobieństwa są równe \(\displaystyle{ \frac{1}{4}}\).
Inaczej mówiąc: \(\displaystyle{ P(\lbrace x_2=x_1 \rbrace \cup \lbrace y_2=y_1 \rbrace)=0}\), zatem pomijając te "nieprawdopodobne" przypadki, wśród czterech par punktów:
1) \(\displaystyle{ (x_1, y_1)}\), \(\displaystyle{ (x_2, y_2)}\)
2) \(\displaystyle{ (-x_1, y_1)}\), \(\displaystyle{ (-x_2, y_2)}\)
3) \(\displaystyle{ (x_1, -y_1)}\), \(\displaystyle{ (x_2, -y_2)}\)
4) \(\displaystyle{ (-x_1, -y_1)}\), \(\displaystyle{ (-x_2, -y_2)}\)
zachodzą po \(\displaystyle{ 1}\) razie każda z \(\displaystyle{ 4}\) możliwości - drugi punkt znajduje się w kierunku \(\displaystyle{ NE, NW, SW, SE}\) od pierwszego punktu.
Ze wskazanej symetrii wynika \(\displaystyle{ P(NE)=P(NW)=P(SE)=P(SW)=\frac{1}{4}}\).