Przede wszystkim nieskończoność występuje w metamatematyce. Po prostu mamy potencjalnie nieskończenie wiele różnych zapisów, w szczególności predykatów, gdzie predykat rozumiem w sensie logiki matematycznej. Poświęcę temu kilka słów.
Niektórzy autorzy, definiując teorię matematyczną, zaczynają od tego, że ma nieskończony alfabet, po czym dają przykład:
x x' x'' x''' ...
Wolałbym, żeby zbioru tak złożonych wyrażeń, jak x'''', nie nazywali alfabetem. Prawdziwa teoria powinna zaczynać od skończonego zbioru znaków, przy tym niewielkiego, łatwego do ogarnięcia wzrokiem, tak by każde dwa różne znaki można było z łatwościę odróżnić. Można na przykład, przynajmniej celem ścisłego wprowadzenia danej teorii, do zbioru znaków wyjściowych zaliczyć 26 liter małych i 26 dużych alfabetu angielskiego, cyfry dziesiętne 0 ... 9, nawiasy ( ), prim ', oraz ' + - * =. Razem powiedzmy 60 znaków (teoretycznie dwa wystarczyłyby). Dopiero na następnym etapie buduje się wyrażenia oznaczające na przykład zmienne, jak wymienione wyrażenia: x x' x'' x''' ... (które kolejno składają się z 1 2 3 ... znaków - nie są pojedynczymi znakami). Można mieć też konstrukcje definiujące nowe pojęcia, jak powiedzmy SUMA, których syntaks znowu używa podane wyjściowe znaki (tu: A M S U).
UWAGA 0: Odstęp " " należy do metateorii (nie jest znakiem teorii). W każdym razie możemy tak się rozsądnie umówić.
UWAGA 1: Można teorię stworzyć dla komputera, żeby komputer ją uprawiał. Znowu wyjściowych "znaków" powinno być skończenie wiele, i powinny być łatwo przez komputer rozróżniane. Z tego powodu stosuje się tylko dwa znaki wewnątrz komputera, o których ludzie na ogół mówią 0 oraz 1. Próbowano więcej "znaków", ale z powodów technologicznych wtedy kłopoty z błędami tak wzrastały, że w zasadzie z tych prób zrezygnowano, prawie.
Kilka słów o predykatach: są to ciągi znaków (struny czyli po angielsku strings), w których jednoznacznie można wyróżnić zmienne (jeżeli występują). Gdy za zmienne podstawimy konkretne wartości stałe, to powinniśmy otrzymać zdanie (w sensie formalnej definicji danej teorii), czyli coś, co jest albo prawdziwe albo fałszywe. Czyli predykat jest funkcją logiczną, której wartościami są Prawda i Fałsz. Na przykład słynny jest predykat Fermata, z jego tak zwanego Ostatniego Twierdzenia:
EXP(x n) + EXP(y n) = EXP(z n)
gdzie EXP(a b) oznacza [;a^b;], ale dla ilustracji chciałem się ograniczyć do wcześniej wspomnianych 60 znaków. Fermat wyraził przypuszczenie, że ten predykat jest zawsze fałszywy, gdy x y z n są liczbami naturalnymi 1 2 ..., takimi że n > 2. Dowód zajął ponad trzysta lat.
Wednesday, November 17, 2010
Sunday, October 10, 2010
Pokój z lampą. Ćwiczenie na przekazywanie informacji. Cz. 0
W naqnaq, w grupie "Zagadki", niejaki Witzar podał szereg świetnych zadań kombinatoryczno-informatycznych, które nazwał logicznymi. Jego scenariusz więzienny zastąpię szkolnym, żeby zadanie brzmiało mniej ponuro.
ZADANIE [;n;] zdolnych uczniów zebrano razem, żeby ustalili optymalną strategię prowadzenia wspólnej gry. Każdy uczeń za ten honor i możliwość wpłacił 300zł na pewne konto. Do wygrania mają wspólną podróż dookoła świata i stypendium dla każdego z nich do końca studiów. Po zebraniu, już do końca gry, nie wolno się im komunikować. Otóż po zebraniu, każdego dnia losowo wybrany uczeń uda się do pewnego pokoiku, w którym lampa będzie zapalona lub zgaszona. Po sobie zostawi lampę zgaszoną lub zapaloną według swojego życzenia (według wspólnie ustalonej strategii). Może też oświadczyć, że wraz z nim każdy student już w tym pokoiku był co najmniej jeden raz. Jeżeli pomyli się, to wpłaty uczniów przepadną, oraz będą nici z podróży i stypendium. Jeżeli oświadczenie będzie poprawne, to wszyscy uczniowie wygrają, zgodnie z obietnicą.
Podpowiedz uczniom jak najlepszą strategię.
Dla n=1, przy jednym uczniu, uczeń wchodzi do pokoiku i woła wygrałem! - i rzeczywiście wygrał. Koniec.
Przy n=2 uczniowie mogą się umówić, że
Jest to absolutnie najlepsza strategia. Szybciej wygrać jest niemożliwym.
Przy n=3 następująca umowa jest optymalna (lepszej nie ma):
Znowu opisana strategia jest optymalna. Za każdym razem wygrywa jak tylko najszybciej można. Już dla n=4 tak dobrej strategii nie ma, co wykażę w następnej nocie. Teraz podam jeszcze definicje kilku pojęć, by dało się rozmawiać o zadaniu ściśle. W szczegółności ściśle zdefiniuję strategię.
Uczniów numerujemy: [;0\ \ldots\ n-1;]. Podobnie numerujemy od zera, ale w nieskończoność, dni w pokoiku: [;0\ 1\ 2\ \ldots;].
Przebiegiem (losowania) nazywamy dowolny ciąg
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
UWAGA Chociaż gra, aż po okrzyk "zwycięstwo!" może trwać skończoną liczbę dni, to teoretycznie wygodnie jest zakładać, że losowanie uczniów powtarza się każdego dnia w nieskończoność (po zakończeniu gry nikogo to już nie obchodzi, nikomu to nie przeszkadza).
Poniższe funkcje za swój argument mają także przebieg, co będziemy często pomijać, żeby za bardzo nie piętrzyć notacji.
Zapisem ucznia [;u;] w dniu gry [;d;] nazywamy strukturę
[;\bullet\quad\quad \ker_{u\ d} := (v_{u\ d}\ \ \delta_{u\ d}\ \ b_{u\ d});]
następujących danych:
Strategią nazywamy dowolną funkcję [;S;] która każdemu a priori możliwemu zapisowi [;\ker;] przypisuje wartość [;S(\ker);], będącą równą 0 (lampę przed opuszczeniem pokoju gasimy lub pozostawiamy zgaszoną) albo 1 (lampę przed opuszczeniem pokoju zapalamy lub zostawiamy zapaloną) albo 2 (wołamy wtedy: zwycięstwo!).
W praktyce, pełna definicja uczniowskiej strategi powinna dać się opisać w notesiku, który uczeń będzie miał przy sobie - strategia powinna dać się opisać jako skonczony algorytm. Teoretycznie prościej jest mówić o strategiach będących dowolnymi funkcjami, jak wyżej.
Uczeń po wejściu do pokoiku uaktualnia swój zapis [;\ker;], po czym stosuje do niego funkcję strategiczną, [;S(\ker);].
Dla liczby uczniów n=1 lub 2 lub 3 podane wyżej strategie dają najszybszą wygraną - nawet granie na szczęście, bez żadnej strategii, też nigdy nie da szybszej wygranej. Takie strategie nazwijmy natychmiastowymi. Zdefiniuję je teraz ściśle, a nawet całe spektrum różnych klas strategii.
Najpierw z każdym przebiegiem
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
zwiążmy jego stopień zaawansowania [;\deg_w;] :
[;\bullet\quad\quad \deg_w(d)\ :=\ \min_{u=0\ \ldots\ n-1}\ v_{u\ d};]
Ponadto zdefiniujmy końce cykli, [;C_w(q);], jako numer pierwszego dnia, w którym każdy uczeń wszedł do pokoiku minimum [;q;] razy:
[;\bullet\quad\quad C_w(q) := min_{\deg_w(d) = q}\ d;]
a gdy takiego dnia nie ma (gdy pewien uczeń nigdy nie był wylosowany aż [;q;] razy), to przyjmujemy [;C(q) := \infty;].
Gdy dla pewnego [;q;] strategia [;S;] zapewnia zwycięstwo nie później niż w dniu [;C_w(q);], to powiemy, że jest opieszała rzędu [;q;].
Strategie opieszałę rzędu 1 są absolutnie najlepsze, są natychmiastowe. Istnieją jednak tylko dla liczby uczniów n=1 2 3. Już dla n=4, i dla wszystkich większych n, strategia natychmiastowa nie istnieje.
Prawdopodobnie uzyskanie strategii, której opieszałość jest rzędu [;\sqrt{n};] (gdzie n jest liczbą uczniów), jest całkiem dobrym wynikiem.
ZADANIE [;n;] zdolnych uczniów zebrano razem, żeby ustalili optymalną strategię prowadzenia wspólnej gry. Każdy uczeń za ten honor i możliwość wpłacił 300zł na pewne konto. Do wygrania mają wspólną podróż dookoła świata i stypendium dla każdego z nich do końca studiów. Po zebraniu, już do końca gry, nie wolno się im komunikować. Otóż po zebraniu, każdego dnia losowo wybrany uczeń uda się do pewnego pokoiku, w którym lampa będzie zapalona lub zgaszona. Po sobie zostawi lampę zgaszoną lub zapaloną według swojego życzenia (według wspólnie ustalonej strategii). Może też oświadczyć, że wraz z nim każdy student już w tym pokoiku był co najmniej jeden raz. Jeżeli pomyli się, to wpłaty uczniów przepadną, oraz będą nici z podróży i stypendium. Jeżeli oświadczenie będzie poprawne, to wszyscy uczniowie wygrają, zgodnie z obietnicą.
Podpowiedz uczniom jak najlepszą strategię.
Dla n=1, przy jednym uczniu, uczeń wchodzi do pokoiku i woła wygrałem! - i rzeczywiście wygrał. Koniec.
Przy n=2 uczniowie mogą się umówić, że
- będą zapalać lampkę albo nie, byle jak;
- początkowego dnia uczeń w pokoiku będzie cicho (nie zawoła, że wygrał);
- każdego następnego dnia, jeżeli uczeń w pokoiku nie był w nim poprzedniego dnia, to zawoła "wygraliśmy!".
Jest to absolutnie najlepsza strategia. Szybciej wygrać jest niemożliwym.
Przy n=3 następująca umowa jest optymalna (lepszej nie ma):
- uczeń, który do danego dnia włącznie, od początkowego, był w pokoiku za każdym razem, pozostawia za sobą światło zgaszone;
- gdy dzień nie jest początkowy, a w czasie przynajmniej jednego z poprzednich dni był w pokoiku inny uczeń od danego, to:
- zastawszy światło zgaszone, uczeń pozostawia po sobie światło zapalone;
- jeżeli uczeń był w pokoiku także poprzedniego dnia, i pozostawił światło zapalone, to znowu zostawia po sobie światło zapalone;
- jeżeli poprzedniego dnia był inny uczeń od danego, i pozostawił światło zapalone, to obecny uczeń woła "wygraliśmy!".
Znowu opisana strategia jest optymalna. Za każdym razem wygrywa jak tylko najszybciej można. Już dla n=4 tak dobrej strategii nie ma, co wykażę w następnej nocie. Teraz podam jeszcze definicje kilku pojęć, by dało się rozmawiać o zadaniu ściśle. W szczegółności ściśle zdefiniuję strategię.
Uczniów numerujemy: [;0\ \ldots\ n-1;]. Podobnie numerujemy od zera, ale w nieskończoność, dni w pokoiku: [;0\ 1\ 2\ \ldots;].
Przebiegiem (losowania) nazywamy dowolny ciąg
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
UWAGA Chociaż gra, aż po okrzyk "zwycięstwo!" może trwać skończoną liczbę dni, to teoretycznie wygodnie jest zakładać, że losowanie uczniów powtarza się każdego dnia w nieskończoność (po zakończeniu gry nikogo to już nie obchodzi, nikomu to nie przeszkadza).
Poniższe funkcje za swój argument mają także przebieg, co będziemy często pomijać, żeby za bardzo nie piętrzyć notacji.
Zapisem ucznia [;u;] w dniu gry [;d;] nazywamy strukturę
[;\bullet\quad\quad \ker_{u\ d} := (v_{u\ d}\ \ \delta_{u\ d}\ \ b_{u\ d});]
następujących danych:
- [;v_{u\ d};] jest liczbą wizyt ucznia [;u;] w pokoiku, w czasie dni [;0\ \ldots\ d;];
- [;\delta_{u\ d} : \{0\ \ldots\ v_{u\ d}-1\} \rightarrow \{0\ 1\ \ldots\};] jest funkcją, która informuje nas o dniach wizyt [;\delta_{u\ d}(0)\ \ldots\ \delta_{u\ d}(v-1);], ucznia [;u;];
- [;b_{u\ d} : \{0\ \ldots\ v_{u\ d}-1\} \rightarrow \{0\ 1\};] jest funkcją, która informuje nas o zastanym stanie lampy, [;b_{u\ d}(t);] na początku wizyty w dniu [;\delta_{u\ d}(t);]; gdy uczeń zastał ciemność, to zapisze wartość funkcji [;b;] jako [;0;]. a jeżeli lampa świeciła się, to zapisze [;1;]; dla ustalenia uwagi (to zupełnie nieważne) zakładamy, że na samym początku dnia [;0;] lampa była zgaszona .
Strategią nazywamy dowolną funkcję [;S;] która każdemu a priori możliwemu zapisowi [;\ker;] przypisuje wartość [;S(\ker);], będącą równą 0 (lampę przed opuszczeniem pokoju gasimy lub pozostawiamy zgaszoną) albo 1 (lampę przed opuszczeniem pokoju zapalamy lub zostawiamy zapaloną) albo 2 (wołamy wtedy: zwycięstwo!).
W praktyce, pełna definicja uczniowskiej strategi powinna dać się opisać w notesiku, który uczeń będzie miał przy sobie - strategia powinna dać się opisać jako skonczony algorytm. Teoretycznie prościej jest mówić o strategiach będących dowolnymi funkcjami, jak wyżej.
Uczeń po wejściu do pokoiku uaktualnia swój zapis [;\ker;], po czym stosuje do niego funkcję strategiczną, [;S(\ker);].
Dla liczby uczniów n=1 lub 2 lub 3 podane wyżej strategie dają najszybszą wygraną - nawet granie na szczęście, bez żadnej strategii, też nigdy nie da szybszej wygranej. Takie strategie nazwijmy natychmiastowymi. Zdefiniuję je teraz ściśle, a nawet całe spektrum różnych klas strategii.
Najpierw z każdym przebiegiem
[;\bullet\quad\quad w : \{0\ 1\ \ldots\} \rightarrow \{\0\ \ldots\ n-1\};]
zwiążmy jego stopień zaawansowania [;\deg_w;] :
[;\bullet\quad\quad \deg_w(d)\ :=\ \min_{u=0\ \ldots\ n-1}\ v_{u\ d};]
Ponadto zdefiniujmy końce cykli, [;C_w(q);], jako numer pierwszego dnia, w którym każdy uczeń wszedł do pokoiku minimum [;q;] razy:
[;\bullet\quad\quad C_w(q) := min_{\deg_w(d) = q}\ d;]
a gdy takiego dnia nie ma (gdy pewien uczeń nigdy nie był wylosowany aż [;q;] razy), to przyjmujemy [;C(q) := \infty;].
Gdy dla pewnego [;q;] strategia [;S;] zapewnia zwycięstwo nie później niż w dniu [;C_w(q);], to powiemy, że jest opieszała rzędu [;q;].
Strategie opieszałę rzędu 1 są absolutnie najlepsze, są natychmiastowe. Istnieją jednak tylko dla liczby uczniów n=1 2 3. Już dla n=4, i dla wszystkich większych n, strategia natychmiastowa nie istnieje.
Prawdopodobnie uzyskanie strategii, której opieszałość jest rzędu [;\sqrt{n};] (gdzie n jest liczbą uczniów), jest całkiem dobrym wynikiem.
Thursday, October 7, 2010
LXII OM3
Termin nadsyłania: 4 października, 2010 r. - I seria
Zadanie konkursowe zawodów stopnia pierwszego:
3. W czworokącie wypukłym ABCD punkty M i N są odpowiednio środkami boków AB i CD, zaś przekątne przecinają się w punkcie E. Wykazać, że prosta zawierająca dwusieczną kąta BEC jest prostopadła do prostej MN wtedy i tylko wtedy, gdy AC = BD.
ROZWIĄZANIE
Potraktujmy płaszczyznę (euklidesową) jako płaszczyznę liczb zespolonych. Dzięki temu możemy stosować algebraiczną notację. Na przykład założenia o punktach M N można zapisać jako:
Niech A' C' będą takimi dowolnymi punktami prostej AC, że E leży pomiędzy A' C', oraz zachodzi równość:
A'- A = C'- C
Punkt przecięcia prostych A'C' i BD dalej jest tym samym punktem E. Także rozpatrywana w zadaniu dwusieczna jest dalej ta sama. Definiujemy nowe środki odcinków:
Oczywiście zachodzi równość:
N'- M' = N - M
Zatem prosta M'N' jest równoległa do prostej MN, i tworzy taki sam kąt z dwusieczną co prosta MN.
Teraz z kolei gdy także punkty B D zastąpić przez punkty B' D', leżące na prostej BD, tak że E leży pomiędzy B' i D', i spełniające równanie:
D' - B' = D - B
Da to nowe punkty M" N", będące środkami odcinków A'B' i C'D' odpowiednio. I znowu dwiusieczna będzie tworzyć ten sam kąt z M"N" co z MN.
Wybierzmy teraz A' B' C' D' jak wyżej, i tak, żeby E było środkiem A'C' oraz środkiem B'D'. Analitycznie możemy przyjąć:
Punkty A' B' C' D' są wierzchołkami równoległoboku, przy czym M"N" jest równoległe do B'C'. Dwusieczna kąta E trójkąta B'EC' jest prostopadła do podstawy B'C' <==> gdy boki EB' i EC' są równe:
implikacja <== jest oczywista, a implikacja ==> dana jest przez to, że każdy z boków EB' i EC' ma długość h/cos(E/2), gdzie E/2 jest kątem połówkowym w wierzchołku E, oraz h jest wysokością.
Z powyższej równoważności natychmiast wynika teza zadania.
KONIEC ROZWIĄZANIA
W przypadku niewypukłym czasem zamiast prostopadłości mamy równoległość.
Zadanie konkursowe zawodów stopnia pierwszego:
3. W czworokącie wypukłym ABCD punkty M i N są odpowiednio środkami boków AB i CD, zaś przekątne przecinają się w punkcie E. Wykazać, że prosta zawierająca dwusieczną kąta BEC jest prostopadła do prostej MN wtedy i tylko wtedy, gdy AC = BD.
ROZWIĄZANIE
Potraktujmy płaszczyznę (euklidesową) jako płaszczyznę liczb zespolonych. Dzięki temu możemy stosować algebraiczną notację. Na przykład założenia o punktach M N można zapisać jako:
- M := (A + B) / 2
- N := (C + D) / 2
Niech A' C' będą takimi dowolnymi punktami prostej AC, że E leży pomiędzy A' C', oraz zachodzi równość:
Punkt przecięcia prostych A'C' i BD dalej jest tym samym punktem E. Także rozpatrywana w zadaniu dwusieczna jest dalej ta sama. Definiujemy nowe środki odcinków:
- M' := (A' + B) / 2
- N' := (C' + D tworzyć ten sam kąt) / 2
Oczywiście zachodzi równość:
Zatem prosta M'N' jest równoległa do prostej MN, i tworzy taki sam kąt z dwusieczną co prosta MN.
Teraz z kolei gdy także punkty B D zastąpić przez punkty B' D', leżące na prostej BD, tak że E leży pomiędzy B' i D', i spełniające równanie:
Da to nowe punkty M" N", będące środkami odcinków A'B' i C'D' odpowiednio. I znowu dwiusieczna będzie tworzyć ten sam kąt z M"N" co z MN.
Wybierzmy teraz A' B' C' D' jak wyżej, i tak, żeby E było środkiem A'C' oraz środkiem B'D'. Analitycznie możemy przyjąć:
- A' := E + (A-C)/2 oraz C' := E + (C-A)/2
- B' := E + (B-D)/2 oraz D' := E + (D-B)/2
Punkty A' B' C' D' są wierzchołkami równoległoboku, przy czym M"N" jest równoległe do B'C'. Dwusieczna kąta E trójkąta B'EC' jest prostopadła do podstawy B'C' <==> gdy boki EB' i EC' są równe:
implikacja <== jest oczywista, a implikacja ==> dana jest przez to, że każdy z boków EB' i EC' ma długość h/cos(E/2), gdzie E/2 jest kątem połówkowym w wierzchołku E, oraz h jest wysokością.
Z powyższej równoważności natychmiast wynika teza zadania.
KONIEC ROZWIĄZANIA
W przypadku niewypukłym czasem zamiast prostopadłości mamy równoległość.
Monday, October 4, 2010
LXII OM4
Termin nadsyłania: 4 października, 2010 r. - I seria
Zadanie konkursowe zawodów stopnia pierwszego:
4. Dana jest liczba naturalna k. Dowieść, że z każdego zbioru liczb całkowitych, mającego więcej niż [;3^k;] elementów, można wybrać (k+1)-elementowy podzbiór S o następujacej własności:
Dla dowolnych dwóch różnych podzbiorów A B zbioru S suma wszystkich elementów zbioru A jest różna od sumy wszystkich elementów zbioru B. (Przyjmujemy, że suma elementów zbioru pustego wynosi 0).
ROZWIĄZANIE
Niech [; X_0\ X_1\ X_2\ \ldots;] będzie dowolnym ciągiem zbiorów liczb całkowitych, takich że ich moce przewyższają kolejne potęgi liczby 3:
[;\bullet\quad\quad \forall_{\ j = 0\ 1\ \ldots}\quad|X_j| > 3^j ;]
Niech [;S_{-1};] będzie dowolnym 1-elementowym zbiorem liczb całkowitych, którego elementem nie jest 0. Zbiór [;S_{-1};] ma własność zbioru S z zadania. Załóżmy, że zdefiniowaliśmy już zbiór j-elementowy [;S_{j-1};], który ma własność zbioru S z zadania, dla pewnej nieujemnej liczby całkowitej [;j;]. Liczba wszystkich ciągów (t.j. funkcji)
[;\bullet\quad\quad\quad e : S_{j-1} \rightarrow \{-1\ \ 0\ \ 1\} ;]
wynosi [;3^j;]. Więc liczb (kombinacji liniowych) postaci:
[;\bullet\quad\quad\quad \sum_{s\in S_{j-1}}\ e(s)\cdot s ;]
jest nie więcej niż [;3^j;]. Istnieje zatem element zbioru [;X_j;], który nie jest powyższej postaci. Zdefiniujmy zbiór [;S_j;] jako [;S_{j-1};], powiększone o ten jeden element, tak, że moc nowego zbioru jest równa j+1. Jest jasnym, że nowy zbiór ma własność zbioru S z zadania. Zakończyliśmy tym indukcyjną definicję rosnącego (w sensie inkluzji) ciągu (j+1)-elementowych zbiorów [;S_j;], dla [;j=-1\ 0\ 1\ \ldots;], mających własność zbioru S z zadania; przy tym
[;\bullet\quad\quad\quad \forall_{\ j=0\ 1\ \ldots}\ S_j\, \backslash\, S_{j-1} \subseteq X_j ;]
Dodatkowo, dla dowolnego zbioru [;X;] liczb całkowitych, z tekstu zadania [;(|X| > 3^k);], możemy wybrać ciąg [;X_0\ X_1\ \ldots;] tak, żeby:
Wtedy S := [;S_k;] jest rozwiązaniem zadania.
Twierdzenie z zadania zachodzi nie tylko dla (grupy addytywnej) liczb całkowitych, lecz także dla dowolnej grupy abelowej. W przypadku szczególnym, gdy każdy niezerowy element grupy jest rzędu 2, wystarczy założyć, że moc zbioru X przewyższa [;2^k;].
Zadanie konkursowe zawodów stopnia pierwszego:
4. Dana jest liczba naturalna k. Dowieść, że z każdego zbioru liczb całkowitych, mającego więcej niż [;3^k;] elementów, można wybrać (k+1)-elementowy podzbiór S o następujacej własności:
Dla dowolnych dwóch różnych podzbiorów A B zbioru S suma wszystkich elementów zbioru A jest różna od sumy wszystkich elementów zbioru B. (Przyjmujemy, że suma elementów zbioru pustego wynosi 0).
ROZWIĄZANIE
Niech [; X_0\ X_1\ X_2\ \ldots;] będzie dowolnym ciągiem zbiorów liczb całkowitych, takich że ich moce przewyższają kolejne potęgi liczby 3:
[;\bullet\quad\quad \forall_{\ j = 0\ 1\ \ldots}\quad|X_j| > 3^j ;]
Niech [;S_{-1};] będzie dowolnym 1-elementowym zbiorem liczb całkowitych, którego elementem nie jest 0. Zbiór [;S_{-1};] ma własność zbioru S z zadania. Załóżmy, że zdefiniowaliśmy już zbiór j-elementowy [;S_{j-1};], który ma własność zbioru S z zadania, dla pewnej nieujemnej liczby całkowitej [;j;]. Liczba wszystkich ciągów (t.j. funkcji)
[;\bullet\quad\quad\quad e : S_{j-1} \rightarrow \{-1\ \ 0\ \ 1\} ;]
wynosi [;3^j;]. Więc liczb (kombinacji liniowych) postaci:
[;\bullet\quad\quad\quad \sum_{s\in S_{j-1}}\ e(s)\cdot s ;]
jest nie więcej niż [;3^j;]. Istnieje zatem element zbioru [;X_j;], który nie jest powyższej postaci. Zdefiniujmy zbiór [;S_j;] jako [;S_{j-1};], powiększone o ten jeden element, tak, że moc nowego zbioru jest równa j+1. Jest jasnym, że nowy zbiór ma własność zbioru S z zadania. Zakończyliśmy tym indukcyjną definicję rosnącego (w sensie inkluzji) ciągu (j+1)-elementowych zbiorów [;S_j;], dla [;j=-1\ 0\ 1\ \ldots;], mających własność zbioru S z zadania; przy tym
[;\bullet\quad\quad\quad \forall_{\ j=0\ 1\ \ldots}\ S_j\, \backslash\, S_{j-1} \subseteq X_j ;]
Dodatkowo, dla dowolnego zbioru [;X;] liczb całkowitych, z tekstu zadania [;(|X| > 3^k);], możemy wybrać ciąg [;X_0\ X_1\ \ldots;] tak, żeby:
- [; X_k = X;]
- [;\forall_{\ j\ =\ 1\ 2\ \ldots}\ X_{j-1}\subseteq X_j ;]
Wtedy S := [;S_k;] jest rozwiązaniem zadania.
Twierdzenie z zadania zachodzi nie tylko dla (grupy addytywnej) liczb całkowitych, lecz także dla dowolnej grupy abelowej. W przypadku szczególnym, gdy każdy niezerowy element grupy jest rzędu 2, wystarczy założyć, że moc zbioru X przewyższa [;2^k;].
LXII OM2
Termin nadsyłania: 4 października, 2010 r. - I seria
Zadanie konkursowe zawodów stopnia pierwszego:
2. Dane są liczby całkowite dodatnie [;m\ n;] oraz [;d;]. Udowodnić, że jeżeli liczby [;m^2\cdot n + 1;] oraz [;m\cdot n^2+1;] są podzielne przez [;d;], to również liczby [;m^3+1;] i [;n^3+1;] są podzielne przez [;d;].
ROZWIĄZANIE
Z założenia wynika, że
[;\bullet\quad d\ |\ (m^2\cdot n + 1) - (m\cdot n^2+1) = m\cdot n\cdot(m-n);]
ponieważ [;d;] jest względnie pierwsze z [;m\cdot n;], to
[;\bullet\quad\quad\quad d\ |\ m-n;]
Zatem:
[;\bullet\quad m^3+1 = (m^2\cdot n + 1) + m^2\cdot (m-n);]
jest podzielne przez [;d;]. Podobnie podzielne przez [;d;] jest [;n^3+1;] (role [;m\ n;] są symetryczne).
Zadanie konkursowe zawodów stopnia pierwszego:
2. Dane są liczby całkowite dodatnie [;m\ n;] oraz [;d;]. Udowodnić, że jeżeli liczby [;m^2\cdot n + 1;] oraz [;m\cdot n^2+1;] są podzielne przez [;d;], to również liczby [;m^3+1;] i [;n^3+1;] są podzielne przez [;d;].
ROZWIĄZANIE
Z założenia wynika, że
[;\bullet\quad d\ |\ (m^2\cdot n + 1) - (m\cdot n^2+1) = m\cdot n\cdot(m-n);]
ponieważ [;d;] jest względnie pierwsze z [;m\cdot n;], to
[;\bullet\quad\quad\quad d\ |\ m-n;]
Zatem:
[;\bullet\quad m^3+1 = (m^2\cdot n + 1) + m^2\cdot (m-n);]
jest podzielne przez [;d;]. Podobnie podzielne przez [;d;] jest [;n^3+1;] (role [;m\ n;] są symetryczne).
LXII OM1
Termin nadsyłania: 4 października, 2010 r. - I seria
Zadanie konkursowe zawodów stopnia pierwszego:
1. Wyznaczyć wszystkie takie pary [;(a\ b);] liczb wymiernych dodatnich, że
[;\bullet\quad\quad\quad \sqrt{a} + \sqrt{b} = \sqrt{4 + \sqrt{7}} ;]
ROZWIĄZANIE
Podane równanie ma dokładnie te same rozwiązania [;(a\ b);] co równanie:
[;\bullet\quad\quad\quad a+2\cdot\sqrt{a\cdot b} + b = 4 + \sqrt{7} ;]
czyli
[;\bullet\quad\quad\quad 2\cdot\sqrt{a\cdot b} = t + \sqrt{7} ;]
gdzie [; t := 4 - a - b;] jest liczbą wymierną. Gdy równanie to jest spełnione, to:
[;\bullet\quad\quad 4\cdot a\cdot b = t^2 + 7 + 2\cdot t \cdot \sqrt{7} ;]
czyli [;2\cdot t \cdot \sqrt{7};] jest liczbą wymierną. Stąd [;t = 0;]. Innymi słowy:
Zatem:
[;\bullet\quad (a-b)^2 = (a+b)^2 - 4\cdot a\cdot b = 9 ;]
skąd [;\max(a\ b) - \min(a\ b) = 3;]. Ponieważ
[;\bullet\quad\quad\quad a+b = \max(a\ b) + \min(a\ b) ;]
to [;\max(a\ b) = 7/2;] i [;\min(a\ b) = 1/2;].
I na odwrót, gdy para [;(a\ b);] spełnia ostatnie 2 równości, to spełnia równanie wyjściowe z tekstu zadania, bo spełnia podane, równoważne z nim:
[;\bullet\quad\quad\quad \frac{7}{2}+2\cdot\sqrt{\frac{7}{2}\cdot \frac{1}{2}} + \frac{1}{2}\ \ =\ \ 4 + \sqrt{7} ;]
Zatem odpowiedź brzmi: podane równanie ma dokładnie dwie pary rozwiązań:
Zadanie konkursowe zawodów stopnia pierwszego:
1. Wyznaczyć wszystkie takie pary [;(a\ b);] liczb wymiernych dodatnich, że
[;\bullet\quad\quad\quad \sqrt{a} + \sqrt{b} = \sqrt{4 + \sqrt{7}} ;]
ROZWIĄZANIE
Podane równanie ma dokładnie te same rozwiązania [;(a\ b);] co równanie:
[;\bullet\quad\quad\quad a+2\cdot\sqrt{a\cdot b} + b = 4 + \sqrt{7} ;]
czyli
[;\bullet\quad\quad\quad 2\cdot\sqrt{a\cdot b} = t + \sqrt{7} ;]
gdzie [; t := 4 - a - b;] jest liczbą wymierną. Gdy równanie to jest spełnione, to:
[;\bullet\quad\quad 4\cdot a\cdot b = t^2 + 7 + 2\cdot t \cdot \sqrt{7} ;]
czyli [;2\cdot t \cdot \sqrt{7};] jest liczbą wymierną. Stąd [;t = 0;]. Innymi słowy:
- [;a+b = 4 ;]
- [;a\cdot b = \frac{7}{4};]
Zatem:
[;\bullet\quad (a-b)^2 = (a+b)^2 - 4\cdot a\cdot b = 9 ;]
skąd [;\max(a\ b) - \min(a\ b) = 3;]. Ponieważ
[;\bullet\quad\quad\quad a+b = \max(a\ b) + \min(a\ b) ;]
to [;\max(a\ b) = 7/2;] i [;\min(a\ b) = 1/2;].
I na odwrót, gdy para [;(a\ b);] spełnia ostatnie 2 równości, to spełnia równanie wyjściowe z tekstu zadania, bo spełnia podane, równoważne z nim:
[;\bullet\quad\quad\quad \frac{7}{2}+2\cdot\sqrt{\frac{7}{2}\cdot \frac{1}{2}} + \frac{1}{2}\ \ =\ \ 4 + \sqrt{7} ;]
Zatem odpowiedź brzmi: podane równanie ma dokładnie dwie pary rozwiązań:
- [;(a\ b) = (\frac{7}{2}\ \ \frac{1}{2});]
- [;(a\ b) = (\frac{1}{2}\ \ \frac{7}{2});]
Saturday, October 2, 2010
Greasemonkey LaTeX
Poprzedni LaTeX chyba przestał działać?
I tak Greasemonkey wydaje się być lepszy.
Ale czy da sobie rade z współczynnikami Netwona?
Najpierw "choose":
![[;\bullet\quad\quad {5\choose 2} = {5 \choose {5-2}} = 10 ;]](http://www.codecogs.com/gif.latex?%5Cbullet%5Cquad%5Cquad%20%7B5%5Cchoose%202%7D%20=%20%7B5%20%5Cchoose%20%7B5-2%7D%7D%20=%2010 "\bullet\quad\quad {5\choose 2} = {5 \choose {5-2}} = 10")
Teraz "binom":
![[;\bullet\quad\quad \binom{6}{2} = \binom{6}{6-2} = 15 ;]](http://www.codecogs.com/gif.latex?%5Cbullet%5Cquad%5Cquad%20%5Cbinom%7B6%7D%7B2%7D%20=%20%5Cbinom%7B6%7D%7B6-2%7D%20=%2015 "\bullet\quad\quad \binom{6}{2} = \binom{6}{6-2} = 15")
Popatrzmy (?). "binom" działa gładko. "choose" ma kłopoty. Dodam klamry (braces). Jak teraz?
Sprawa jest jasna. Należy używać binom, a o choose zapomnieć, czyli należy choose binom :-)
Dopisek 2012-01-01: choose też działa dobrze. Należało całe wyrażenie z choose zamknąć w klamrach, na przykład 5+{5\choose 2} = {6 choose 2} = 15, co daje:
Najpierw "choose":
Teraz "binom":
Popatrzmy (?). "binom" działa gładko. "choose" ma kłopoty. Dodam klamry (braces). Jak teraz?
Sprawa jest jasna. Należy używać binom, a o choose zapomnieć, czyli należy choose binom :-)
Dopisek 2012-01-01: choose też działa dobrze. Należało całe wyrażenie z choose zamknąć w klamrach, na przykład 5+{5\choose 2} = {6 choose 2} = 15, co daje:
Subscribe to:
Posts (Atom)