szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 9 wrz 2015, o 18:19 
Użytkownik

Posty: 5620
Lokalizacja: Kraków
Niech n_0 \in \NN a zbiory A, B \subset \NN są takie że A \cup B=\NN i A \cap B=\emptyset.
Udowodnić, że istnieją a,   bn_0 <a <b i:
\{ a, b, a+b \} \subset A lub \{ a, b, a+b \} \subset B
Góra
Mężczyzna Offline
PostNapisane: 28 wrz 2015, o 01:54 
Użytkownik
Avatar użytkownika

Posty: 1229
Hmm... dla n=0 teza jest oczywista, to może przez indukcję?...

Ustalmy n\in\NN i załóżmy, że teza jest spełniona dla wszystkich k < n, gdzie n > 0. Wtedy możemy sobie nasze zbiory A, B, troszkę przerobić, to znaczy w ten sposób: A' = \lbrace a-1: a\in A\rbrace\setminus\lbrace -1\rbrace, B' = \lbrace b-1: b\in B\rbrace\setminus\lbrace -1\rbrace. Wówczas A'\cup B' = \NN, oraz A'\cap B' = \emptyset. Na mocy założenia indukcyjnego istnieją takie a', b', że \lbrace a', b', a'+b'\rbrace\subseteq A' (lub B' - nieistotne), gdzie n-1 < a' < b'. To z kolei oznacza, że \lbrace a, b, a+b\rbrace\subseteq A. Koniec.

Może być?

-- 28 wrz 2015, o 01:20 --

Czy inspiracją do stworzenia tego zadania mógł być hotel Hilberta? :)
Góra
Mężczyzna Offline
PostNapisane: 28 wrz 2015, o 02:55 
Użytkownik

Posty: 15239
Lokalizacja: Bydgoszcz
A dlaczego teza jest oczywista dla n=0?
Góra
Mężczyzna Offline
PostNapisane: 28 wrz 2015, o 21:36 
Użytkownik

Posty: 293
Lokalizacja: Kraków
Bez straty ogólności załóżmy, że 1 \in A. Łatwo widać, że obydwa zbiory muszą być nieskończone. Więc teraz dwa przypadki:

2 \in B

Niech k > 3  \wedge k \in A, wtedy k-1 \in B \wedge k+1 \in B (ponieważ inaczej tworzyłyby trójkę z 1), wtedy trójka \left\{2, k-1, k+1\right\}  \subset B.

2 \in A

Wtedy 3 \in B i robimy jak wyżej tylko zamiast k-1, k+1 bierzemy k-1, k+2.
Góra
Mężczyzna Offline
PostNapisane: 28 wrz 2015, o 23:12 
Użytkownik
Avatar użytkownika

Posty: 1229
O, dzięki, nawet nie zdążyłem napisać :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Efektywne szeregowanie podzbiorów  RainbowDash  1
 ustawianie podzbiorów w ciąg  kolegasafeta  4
 liczba podzbiorów - zadanie 2  Rike  3
 wybieranie podzbiorów 5-elementowych ze zbioru 20-el.  Z_i_o_M_e_K  1
 Liczba możliwych podzbiorów.  cynikkk  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl