Paradoks urodzin
Ile osób musi być w grupie, by prawdopodobieństwo, że co najmniej dwie z nich mają urodziny w ten sam dzień, wynosiło \(\frac 12\)? Odpowiedź: 23. Rozpocznijmy od wyliczenia prawdopodobieństwa, że wśród 23 osób nie ma pary, która obchodzi urodziny jednego dnia.
Pierwsza osoba może się urodzić w każdym z 365 dni, druga w każdym z 364 itd.
\[ \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \ldots \cdot \frac{343}{365}=0.4927
\]
Jakie jest zdarzenie przeciwne? Takie: co najmniej dwie osoby spośród dwudziestu trzech mają urodziny w jeden dzień. A jego prawdopodobieństwo wynosi tyle:
\[ 1-0.4927=0.5073
\]
Każde dwa punkty otwartego podzbioru spójnego przestrzeni \(\mathbb{C}\) można połączyć łamaną w całości zawartą w tym zbiorze
Uwaga: prawdziwe jest też twierdzenie odwrotne: Jeśli każde dwa punkty zbioru można połączyć łamaną w całości zawartą w tym zbiorze, to ten zbiór jest spójny. Ale dowód nie jest taki ciekawy.
Niech \(C \subset \mathbb{C}\) będzie otwartym i spójnym zbiorem. Weźmy dowolny punkt \(a \in C\). Niech \(A \subset C\) będzie zbiorem punktów, które da się połączyć z \(a\) łamaną w całości zawartą w \(C\) (dalej takie punkty będziemy nazywać łączalnymi z \(a\)). Niech \(K=C-A\) - zbiór punktów, które nie są łączalne z \(a\).
Weźmy \(x \in A\). Należy on też do \(C\) (bo \(A \subset C\)). Skoro \(C\) jest otwarty, to istnieje taki \(\varepsilon>0\), że kula \(B(x,\varepsilon)\) jest w całości zawarta w \(C\).
Dla każdego punktu \(y \in B(x,\varepsilon)\) odcinek \(xy\) zawiera się w tej kuli. Ale \(x \in A\), więc jest łączalny z \(a\). Zatem \(y\) też jest łączalny z \(a\): przez \(x\). Zatem \(y \in A\) dla każdego \(y\) z kuli, więc cała kula zawiera się w \(A\). Skoro tak, to \(A\) jest zbiorem otwartym.
Teraz niech \(x \in K\). Znowu istnieje \(\varepsilon>0 \colon B(x,\varepsilon) \subset C\) - z tego samego powodu, co wcześniej. Jeśli jakikolwiek punkt z tej kuli jest łączalny z \(a\), to \(x\) jest łączalny z \(a\) (przez ten jakikolwiek punkt). Ale \(x \in K\) - należy do zbioru punktów niełączalnych. Mamy zatem sprzecznosć.
W takim razie, żaden z punktów z tej kuli nie jest łączalny z \(a\). W takim razie, cała kula zawiera się w zbiorze punktów niełączalnych: \(B(x,\varepsilon) \subset K\). To oznacza, że \(K\) jest otwarty.
Podsumujmy: \(A \cap K = \varnothing, \ A \cup K = C, \ a \in A \), więc \(A \neq \varnothing \). Skoro \(C\) jest sumą dwóch otwartych i rozłącznych zbiorów, to jeden z nich musi być pusty (nie da się inaczej). Tym pustym nie jest \(A\), więc jest nim \(K\). Czyli \(C=A\), czyli wszystkie punkty są łączalne ze sobą (bo \(a\) było dowolne).
Ciągłość liniowego operatora z unormowanej przestrzeni liniowej w unormowaną przestrzeń liniową
Niech \(T \colon X \to Y\) będzie operatorem liniowym, gdzie \(X,Y\) to unormowane przestrzenie liniowe. Niech \(T\) będzie ciągły w punkcie \(x_0\). Weźmy dowolny punkt \(x\) i ciąg \(x_n \to x \in X\). Wtedy ciąg \(x_n-x+x_0 \to x_0\).
\(T\) jest ciągły w \(x_0\), więc \(T(x_n-x+x_0) \to T(x_0)\).
Ale \(T\) jest liniowy, więc \(T(x_n-x+x_0) = T(x_n)-T(x)+T(x_0)\), czyli mamy \(T(x_n)-T(x)+T(x_0) \to T(x_0)\), co oznacza, że \(T(x_n)-T(x) \to 0\), zatem \(T\) jest ciągły w \(x\), który był dowolny, więc \(T\) jest ciągły w każdym punkcie, zatem jest ciągły. Zatem jeśli \(T\) jest ciągły w jednym punkcie, to jest ciągły na całej dziedzinie.
Niech \(T\) będzie ciągły. Oznacza to, że jest ciągły w każdym punkcie, czyli w szczególności każdym punkcie z osobna. Oznacza to, że ciągłość w jednym punkcie jest równoważna ciągłości! Ale to jeszcze nie koniec.
Teraz pokażemy, że ciągłość jest równoważna ograniczoności. Załóżmy nie wprost, że \(T\) jest ciągły, ale nie jest ograniczony. Wtedy \(\neg \exists M \in \mathbb{R} \ \forall x \in X \colon ||T(x)|| \leq M \cdot ||x|| \), czyli \(\forall M \ \exists x \in X \colon ||T(x)|| > M \cdot ||x||\). Niech \(M=n\). Istnieje taki ciąg \(y_n\), że \(||T(y_n)|| > n \cdot ||y_n||\).
Niech \(x_n=\frac{y_n}{n \cdot ||y_n||}\). Wtedy \(||x_n||=\left|\left|\frac{1}{n \cdot ||y_n||} \cdot y_n\right|\right|=\frac{1}{n \cdot ||y_n||} \cdot ||y_n||=\frac 1n \to 0 \), czyli \(x_n \to 0\). Natomiast \(||T(x_n)||=\frac{1}{n \cdot ||y_n||} \cdot ||T(y_n)||\) (z liniowości \(T\) i własności normy).
Ale \(||T(y_n)|| > n \cdot ||y_n||\), więc \(||T(x_n)|| > \frac{1}{n \cdot ||y_n||} \cdot n \cdot ||y_n||=1\), czyli \(T\) nie jest ciągły w zerze. Sprzeczność z założeniem ciągłości. Zatem \(T\) jest ograniczony.
Teraz załóżmy, że \(T\) jest ograniczony. Pokażemy ciągłość. Istnieje takie \(M\), że \(||T(x)|| \leq M \cdot ||x||\) dla każdego \(x \in X\). Niech \(x_n \to 0\). Wtedy \(||x_n|| \to 0\) i \(M \cdot ||x_n|| \to 0\). Ale \(||T(x_n)|| \leq M \cdot ||x_n||\), a norma jest zawsze dodatnia, więc \(||T(x_n)|| \to 0\), więc \(T(x_n) \to 0\), więc \(T\) jest ciągły w zerze.
Ciągłość w jednym punkcie jest równoważna ciągłości, więc \(T\) jest ciągły.
Wniosek z dowodów jest taki, że następujące trzy są równoważne:
1. \(T\) jest ciągły w jednym punkcie.
2. \(T\) jest ciągły na całym \(X\).
3. \(T\) jest ograniczony.
Prawo wzajemności reszt kwadratowych
Jest to twierdzenie Gaussa i udowodnimy to, korzystając z lematu Eisensteina: dla nieparzystych liczb pierwszych \(p,q\) zachodzi \(\left(\frac{q}{p}\right)=(-1)^{\displaystyle\sum_{j=1}^{\frac{p-1}{2}} \left\lfloor \frac{jq}{p}\right\rfloor}\). To po lewej to oczywiście symbol Legendre'a. Wyjątkowo przeraźliwie wyglądający lemat.
Jednak dowód prawa wzajemności jest tak fajny, że nawet nie trzeba wiedzieć czym są te całe reszty kwadratowe, żeby się podobało.
Rozpatrzmy poniższy prostokąt.
W nawiasach mamy współrzędne punktów. Przekątna wyraża się wzorem \(y=\frac qp x\).
Ile punktów kratowych leży wewnątrz prostokąta \(ABCD\), definiując punkty kratowe jako punkty o współrzędnych całkowitych? \(p,q\) są nieparzyste, więc tych punktów kratowych jest \(\frac{p-1}{2}\cdot\frac{q-1}{2}\). Czy na odcinku \(AC\) są punkty kratowe? Załóżmy, że \((k,l)\) leży na naszym odcinku. Spełniają wtedy równanie przekątnej, czyli \(l=\frac qp k\).
\(p\neq q, \ p,q\) są pierwsze, więc stamtąd mamy, że \(k\) jest podzielne przez \(p\). Ale nie jest to możliwe, bo \(k < p\). Czyli część punktów kratowych leży powyżej przekątnej, a część poniżej. Obliczmy ile jest poniżej.
W kolumnie \(x=j\) punktów kratowych jest \(\left\lfloor\frac pq j\right\rfloor\) (wynika to ze wzoru przekątnej). Bierzemy \(j=1,2,\ldots,\frac{p-1}{2}\) i sumujemy. Liczba punktów kratowych poniżej to \(\displaystyle\sum_{j=1}^{\frac{p-1}{2}} \left\lfloor\frac qp j\right\rfloor\).
Analogicznie nad prostą jest ich \(\displaystyle\sum_{i=1}^{\frac{q-1}{2}} \left\lfloor\frac pq i\right\rfloor\). Zatem łącznie \(\displaystyle\sum_{j=1}^{\frac{p-1}{2}} \left\lfloor\frac qp j\right\rfloor + \displaystyle\sum_{i=1}^{\frac{q-1}{2}} \left\lfloor\frac pq i\right\rfloor\).
Ale na początku dowodu policzyliśmy w inny sposób i doszliśmy, że jest ich \(\frac{p-1}{2}\cdot\frac{q-1}{2}\). Zatem
\[ \displaystyle\sum_{j=1}^{\frac{p-1}{2}} \left\lfloor\frac qp j\right\rfloor + \displaystyle\sum_{i=1}^{\frac{q-1}{2}} \left\lfloor\frac pq i\right\rfloor = \frac{p-1}{2}\cdot\frac{q-1}{2}
\]
I teraz praktyczne wykorzystanie lematu Eisensteina:
\[ \left(\frac{p}{q}\right)\cdot\left(\frac{q}{p}\right) = (-1)^{\displaystyle\sum_{i=1}^{\frac{q-1}{2}} \left\lfloor \frac{ip}{q}\right\rfloor+ \sum_{j=1}^{\frac{p-1}{2}} \left\lfloor \frac{jq}{p}\right\rfloor} = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}
\]
To właśnie chcieliśmy udowodnić.
<< Poprzednie ulubione dowody | |
Kolejne ulubione dowody >> (na razie nie ma)