Delta mi!

Uogólnijmy problem: udowodnimy, że jeżeli oraz są zbiorami skończonymi o tej samej liczbie elementów oraz jest iniekcją, to jest bijekcją. Rozwiązanie przebiega indukcyjnie ze względu na liczbę elementów zbioru Oczywiście przypadek jest spełniony, przechodzimy zatem do kroku indukcyjnego. Niech Niech będzie takie, że dla pewnego Takie jest jedyne na mocy iniektywności, zatem można rozważyć funkcję daną wzorem dla Wtedy oraz jest iniekcją. Istotnie, jeżeli i to Zauważmy teraz, że (ponownie korzystamy z iniektywności), zatem również Tym samym jest iniekcją, a więc z założenia indukcyjnego jest ona bijekcją. Stąd już łatwo wynika, że jest bijekcją (dorzucamy po różnym od pozostałych punkcie do dziedziny i przeciwdziedziny).

Rozwiązanie problemu wyjściowego polega teraz na zastosowaniu udowodnionego przed chwilą ogólniejszego faktu dla

Niech będzie liczbą uczestników pewnego kółka, spełniającego opisane w zadaniu warunki. Udowodnimy, że Przydatny okaże się następujący lemat, którego dowód można znaleźć na przykład w Wikipedii pod hasłem twierdzenie Ramseya:

Wybierzmy pewnego uczestnika Przypuśćmy, że lubi on pewnych 6 uczestników. Zgodnie z założeniem zadania oraz powyższym lematem wśród nich znajduje się 3, którzy wzajemnie się lubią, i razem z tworzą oni czwórkę, która przeczy założeniom zadania. Przypuśćmy teraz, że nie lubi pewnych 4 uczestników. Wśród nich znajduje się dwóch, którzy się nie lubią, i razem z tworzą oni trójkę sprzeczną z założeniami. Wynika stąd, że Gdyby jednak to każdy uczestnik musiałby lubić dokładnie 5 uczestników. Jest to sprzeczność, gdyż suma liczb sympatii poszczególnych uczestników wyniosłaby 45, a musi to być liczba parzysta ze względu na wzajemność uczuć. W tej sytuacji

Jeśli ponumerujemy 8 uczniów liczbami od 1 do 8 i okaże się, że uczniowie o numerach i lubią się tylko wtedy, gdy to ta grupka będzie spełniać warunki zadania, co kończy rozwiązanie.

Teza wynika wprost z tego, że mnożenie przez element niezerowy jest bijekcją ciała W języku bardziej elementarnym: jeśli jest permutacją zbioru zaś jest elementem zbioru to reszty z dzielenia liczb przez są wszystkie różne - tworzą więc także permutację zbioru Przy tym jeśli wyjściowa permutacja należała do zbioru - czyli spełniała zależność (mod ) - to po pomnożeniu wszystkich jej wyrazów przez utworzy permutację, w której analogiczna suma przystaje do - czyli permutację należącą do zbioru

Zostało w ten sposób określone odwzorowanie ze zbioru do zbioru Ono jest odwracalne; weźmy bowiem element dla którego (mod ) (taki element istnieje, bo reszty z dzielenia liczb przez są wszystkie różne i niezerowe). Jeśli teraz permutacja znajduje się w zbiorze to po pomnożeniu wszystkich wyrazów przez znajdzie się w zbiorze Uzyskane odwzorowania (mnożenie przez ) oraz (mnożenie przez gdzie ) są wzajemnie odwrotne. To dowodzi, że zbiór jest równoliczny ze zbiorem Skoro tak jest dla każdej niezerowej reszty znaczy to, że wszystkie zbiory są równoliczne.

Niech dla będzie liczbą elementów zbioru pomalowanych na biało. Zauważmy, że jest liczbą elementów zbioru pomalowanych na biało, czyli Jeśli to teza zadania zachodzi. W przeciwnym razie albo Przyjmijmy bez straty ogólności, że spełniony jest pierwszy przypadek (drugi jest analogiczny). Wtedy Jest jasne, że zatem istnieje taka liczba dla której mamy co jest równoważne z tezą zadania.

Oznaczmy przez wspólną wartość sumy elementów w obydwu podzbiorach. Wówczas

czyli

Gdyby pewien z rozważanych podzbiorów miał elementów, to jego suma elementów byłaby nie mniejsza od

Uzyskana sprzeczność kończy rozwiązanie zadania.

Odpowiedź: Największa możliwa liczba elementów zbioru jest równa

Przyjmując

mamy oraz suma każdych trzech elementów jest większa od a zatem nie należy do

Z drugiej strony, zbiory oraz

(dla ) stanowią rozbicie zbioru a w każdym z nich jeden z elementów jest sumą trzech innych, mianowicie

oraz

Pozostaje zauważyć, że jeżeli oraz to dla pewnego i w konsekwencji zbiór nie ma danej w treści zadania własności.

(a)

Odpowiedź: Nie.
Przypuśćmy, że taki zbiór istnieje. Aby liczby 0 oraz miały przedstawienia w postaci odpowiednich sum, musimy mieć Gdyby to mielibyśmy dwa przedstawienia tej liczby jako sumy elementów : a zatem Podobne rozważania prowadzą kolejno do wniosków, że Ale sprzeczność.

(b)

Odpowiedź: Tak.
Niech Wówczas każda liczba nieparzysta większa od (czyli każdy element zbioru ) postaci ma dokładnie jedno przedstawienie w postaci sumy dwóch elementów mianowicie oraz

Rozważmy dowolny podział zbioru dodatnich liczb całkowitych spełniający zadane warunki. Zauważmy, że jeżeli to dla dowolnego mamy co jest sprzeczne z założeniem, że zbiory i są rozłączne. Wobec tego

Oznaczmy przez najmniejszy element zbioru Korzystając z pierwszego z danych warunków, łatwo indukcyjnie udowodnić, że dla każdej dodatniej liczby całkowitej :

skąd wniosek, że wszystkie liczby niepodzielne przez należą do zbioru W szczególności z drugiego z danych warunków wynika, że każda liczba podzielna przez ale niepodzielna przez należy do zbioru

Przypuśćmy, że dla pewnej dodatniej liczby całkowitej Wówczas, skoro to co jest sprzeczne z konkluzją poprzedniego akapitu. To oznacza, że wszystkie liczby podzielne przez należą do zbioru

Pozostaje zauważyć, że dla każdego jeżeli jest zbiorem liczb niepodzielnych przez a - zbiorem liczb podzielnych przez to warunki zadania są spełnione.

Podany warunek przepisujemy równoważnie jako Niech będzie zbiorem odwrotności wszystkich liczb za zbioru Dowolne dwa elementy zbioru są więc oddalone o co najmniej Zatem w każdym spośród przedziałów

może być co najwyżej jeden element zbioru Pozostałe liczby dodatnie tworzą przedział w którym są jedynie odwrotności liczb naturalnych To pokazuje, że zbiór (więc i zbiór ) może liczyć co najwyżej elementów.

Odpowiedź na drugie pytanie z zadania jest przecząca: na przykład dla nie istnieje -elementowy zbiór o podanej własności. Jak w przypadku ogólnym, zauważamy, że w każdym z przedziałów może być tylko jeden element zbioru Dalej, odwrotności liczb naturalnych, leżące w przedziale rozbijamy na pięć podzbiorów:

- każdy z nich ma średnicę mniejszą niż więc zawiera co najwyżej jeden element zbioru No i zostają jeszcze ułamki Liczność zbioru (więc i ) nie przekracza czyli 16.

Dla każdego jest dokładnie pięć możliwości opisujących, które z liczb należą do podzbioru spełniającego warunek zadania. Mianowicie:

a.

żadna z nich nie należy;

b.

tylko należy;

c.

tylko należy;

d.

tylko należy;

e.

liczby oraz należą (natomiast nie należy).

Ponieważ dla różnych możliwości te są niezależne, to liczba szukanych pozdbiorów wynosi

Można przyjąć, że Wskażemy indukcyjną konstrukcję ciągu zbiorów o wymaganych własnościach. Zaczniemy od trójki Załóżmy, że zbiory zostały już określone. Wówczas definiujemy jako najmniejszą liczbę naturalną jeszcze niewykorzystaną (tzn. nieobecną w zbiorze ) - to już gwarantuje, że w wyniku całej konstrukcji wszystkie liczby naturalne zostaną użyte oraz że ciąg będzie rosnący.

Aby dokończyć określenie zbioru (gdy już mamy), patrzymy na liczbę Jeżeli jest ona jeszcze niewykorzystana, przyjmujemy ją jako Jeżeli jest wykorzystana, bierzemy jako liczbę ; i z konieczności przyjmujemy (tak więc jedna z różnic będzie równa a druga ). Tak określona liczba jest większa od liczb więc nie została wcześniej wykorzystana.

Pozostaje uzasadnić, że w przypadku, gdy liczba została już wykorzystana, wówczas liczba pozostała niewykorzystana (i może być użyta jako ). Przypuśćmy, że liczba znalazła się w którymś zbiorze o numerze Skoro to ; musiałaby zajść równość Ale więc mielibyśmy Liczba niewykorzystana aż do -tego kroku konstrukcji, tym bardziej nie była jeszcze wykorzystana w momencie konstrukcji zbioru więc na mocy przyjętego algorytmu powinna była zostać użyta jako

Uzyskana sprzeczność dowodzi niesłuszności przypuszczenia, że i uzasadnia poprawność określenia ; powstały zbiór jest rozłączny ze zbiorami

Liczba jest nieparzysta, zatem zbiór wszystkich liczb parzystych, mniejszych od ma własność, o którą chodzi. Jest ich Wykażemy, że jest to największa możliwa liczność.

Rozbijamy zbiór na rozłączne pary:

Mamy razem par liczb. Zbiór o większej liczności (zawarty w ) musi zawierać jedną z wymienionych par. Ale w każdej parze albo suma, albo różnica elementów jest równa Stąd nasza teza.

Niech będzie parą zbiorów, spełniających wymienione warunki. Ponumerujmy te warunki, w podanej kolejności, (i), (ii), (iii), (iv).

Gdyby liczba 0 była w zbiorze to dla każdej liczby mielibyśmy (z war. (iv)) ; to by znaczyło, że zbiór zawiera się w zbiorze czyli (z war. (i)) Wtedy (z war. (iii)) także co daje sprzeczność z warunkiem (ii). Wniosek: Warunek (i) wymusza konkluzję: Stąd (i z war. (iii))

Gdyby liczba 1 była w zbiorze to (z war. (iii)) ; a przecież Tak więc czyli (z war. (i))

Wykażemy indukcyjnie, że dla każdej liczby całkowitej :

(*)

Dla tak jest. Ustalmy liczbę i przyjmijmy słuszność związków (*) dla tej liczby Przypuśćmy, że ; wtedy (z war. (iv)) wbrew założeniu indukcyjnemu. Zatem czyli (z war. (i))

Przypuśćmy z kolei, że Wtedy (z war. (iii)) wbrew temu, co wykazaliśmy tuż przed chwilą. Zatem czyli (z war. (i)) Uzyskaliśmy związki (*) z liczbą zastąpioną przez Z zasady indukcji własność (*) przysługuje wszystkim liczbom całkowitym nieujemnym.

Teraz pokażemy, że ujemnym - też. Przypuśćmy, że dla pewnej liczby Wiemy już (własność (*)), że a więc (z war. (iv)): ; sprzeczność z wcześniejszym ustaleniem W takim razie czyli (z war. (i))

Wreszcie przypuśćmy, że dla pewnej liczby ; wtedy (z war. (iii)) wbrew temu, co stwierdziliśmy przed chwilą. Zatem czyli (z war. (i))

Mamy więc słuszność związków (*) dla wszystkich Mówią one, że jest zbiorem wszystkich liczb parzystych, a jest zbiorem wszystkich liczb nieparzystych. Ta para zbiorów spełnia, rzecz jasna, wymagane warunki - i jest to jedyna taka para.

Przyjmijmy, że to podzbiory zbioru oznaczające składy drużyn na pierwszym treningu, a – na drugim. Chcemy udowodnić, że dla pewnych mamy Przypuśćmy, że nie ma takiej pary zbiorów. Ponieważ są parami rozłączne i także, więc mamy

co daje sprzeczność.