Delta mi!

Każdy pan musi znać jakąś panią, inaczej nie znajdzie partnerki. Każdych dwóch panów musi znać łącznie co najmniej dwie panie – jeśli znają tylko jedną, to jeden z nią zatańczy, a drugi zostanie bez pary. Każdych trzech panów musi znać łącznie co najmniej trzy panie i tak dalej, każdych  panów musi znać łącznie co najmniej  pań.

Czy jeśli powyższe warunki są spełnione, to już wystarczy i na pewno uczestnicy balu mogą dobrać się w pary? Tak, to właśnie orzeka twierdzenie Halla, którego dowód i zastosowania były tematem wykładu.

Nie. Suma nieparzystej liczby nieparzystych liczb musi być nieparzysta, nie może być równa 20.

Przypuśćmy, że  Pomnóżmy obie strony równania przez  Wtedy

więc

Stąd  dzieli się przez  sprzeczność. Zatem liczby  o żądanych własnościach nie istnieją.

Ponieważ  nierówność dana do udowodnienia jest równoważna następującej:

Bez straty ogólności przyjmijmy, że

Jeżeli  to w ostatniej nierówności lewa strona jest nieujemna, prawa jest niedodatnia i nie ma czego dowodzić.

Gdy zaś  możemy tak przekształcać lewą stronę i szacować ją z dołu, by uzyskać wyrażenie widoczne po prawej stronie:

Niech punkt  będzie czwartym wierzchołkiem równoległoboku  a  – czwartym wierzchołkiem równoległoboku Równoległoboki te są przystające, ponieważ    oraz    Stąd

Niech punkt  będzie czwartym wierzchołkiem równoległoboku  Wtedy  także jest równoległobokiem (bo ). Wobec tego punkt  jako środek jego przekątnej  jest też środkiem drugiej przekątnej  Analogicznie  jest środkiem  Stąd i z twierdzenia Talesa uzyskujemy  oraz

Niech punkt  będzie czwartym wierzchołkiem prostokąta Wtedy  jest równoległobokiem o środku  (bo  oraz ), więc punkty  są współliniowe. Odcinki  i  są średnicami okręgu opisanego na prostokącie  Ponadto  więc punkt  leży na tym okręgu. Stąd

Niech punkt  będzie czwartym wierzchołkiem równoległoboku Wtedy  także jest równoległobokiem oraz zachodzą równości

(*)

oraz

(**)

---

Z równości  (uwzględniając wzajemne położenie odpowiednich punktów) wynika, że punkty  leżą na jednym okręgu. Wobec tego  co razem z równością  daje tezę.

Załóżmy, że liczbę zapisano jako dla pewnych liczb naturalnych i takich że To oznacza, że

Zauważmy, iż jedna z liczb jest nieparzysta i większa od czyli ma czynnik nieparzysty, więc nie jest potęgą dwójki. Z drugiej strony, jeżeli nie jest potęgą dwójki, to liczba zapisuje się jako iloczyn liczby parzystej i nieparzystej Jeśli oznacza większą z tych liczb, to możemy przyjąć, iż

Niech  ( ).

Gdy  wystarczy wziąć dowolną liczbę  będącą iloczynem  różnych liczb pierwszych. Są one oczywiście dzielnikami liczby  Dalej przyjmijmy, że

Najpierw wykażemy, że zbiór dzielników pierwszych wszystkich liczb  jest nieskończony. Przypuśćmy bowiem, że jest to zbiór skończony  Biorąc jako  dowolną liczbę postaci  (  całkowite), mamy

Liczba w nawiasie kwadratowym nie dzieli się przez żadną z liczb pierwszych  (a swoboda wyboru  pozwala przyjąć, że jest różna od ); ma więc jakiś inny dzielnik pierwszy, wbrew uczynionemu przypuszczeniu.

Stąd wniosek, że dla dowolnego  istnieją różne liczby pierwsze  oraz takie liczby całkowite  że

Znajdujemy liczbę  spełniającą układ kongruencji

taka liczba istnieje, w myśl chińskiego twierdzenia o resztach. Wówczas

liczba  ma więc co najmniej  różnych dzielników pierwszych.

Niech będzie okresem funkcji Z równości czyli

(czyli jeszcze prościej: ) wnosimy, że

Pochodna też jest funkcją -okresową: czyli

Zatem albo (liczba wymierna), albo skąd ( ),

Przekręcamy diagram o tak, by otrzymać tabelę – nieskończoną macierz ; jest to lewa z dwóch tabelek poniżej:

Zgodnie z treścią zadania, jej wyrazy są związane zależnościami:

W kolejnych wierszach widzimy ciągi arytmetyczne; odgadujemy wzór jawny Sprawdzamy, że te liczby spełniają napisane przed chwilą równania (które wyznaczają zawartość całej tabeli jednoznacznie).

Tworzymy nową macierz nieskończoną o wyrazach  (prawy diagram powyżej). Zachodzą równości

Tak więc jest po prostu tabliczką mnożenia liczb nieparzystych. Każda liczba nieparzysta występuje w niej tyle razy, ile ma różnych dzielników dodatnich.

Niech teraz będzie zadaną liczbą całkowitą. Bierzemy dowolną liczbę pierwszą ; wówczas liczba wystąpi w tabeli dokładnie  razy. Wracając do tabeli widzimy, że dokładnie  razy pojawi się w niej liczba Jest nieskończenie wiele liczb pierwszych – mamy więc tezę zadania.

Dwunastościan widziany przez przednią ścianę.

(a) Można (rysynek obok). Kolorem zaznaczono krawędzie o nieparzystych numerach.

(b) Nie można. Niech oznacza sumę wszystkich numerów krawędzi:

Niech oznacza sumę numerów w -tym wierzchołku ( ). Wtedy bo numer każdej krawędzi jest liczony dwukrotnie – przy każdym z jej końców. Gdyby każda z liczb była podzielna przez 4, to także. Jednak nie dzieli się przez 4.

(a) Nie. Opisana operacja zwiększa o 2 sumę wszystkich liczb. Początkowo suma ta jest równa 1, więc zawsze jest nieparzysta, czyli niepodzielna przez 8.

(b) Nie. Wyróżnijmy liczby w czterech wierzchołkach, jak na rysunku. Niech oznacza ich sumę, a – sumę pozostałych czterech liczb. Opisana operacja nie zmienia Początkowo Tymczasem gdyby i to

Nie można. Liczby we wszystkich wierzchołkach muszą być tej samej parzystości, aby dla każdej krawędzi liczba umieszczona na jej środku była całkowita. Liczba 1 nie jest średnią arytmetyczną żadnych liczb większych od niej, zatem musi stać w wierzchołku, podobnie liczba 18. Nie są one jednak tej samej parzystości.