Własność podzbiorów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Własność podzbiorów

Post autor: mol_ksiazkowy »

Niech \(\displaystyle{ n_0 \in \NN}\) a zbiory \(\displaystyle{ A, B \subset \NN}\) są takie że \(\displaystyle{ A \cup B=\NN}\) i \(\displaystyle{ A \cap B=\emptyset}\).
Udowodnić, że istnieją \(\displaystyle{ a, b}\)\(\displaystyle{ n_0 <a <b}\) i:
\(\displaystyle{ \{ a, b, a+b \} \subset A}\) lub \(\displaystyle{ \{ a, b, a+b \} \subset B}\)
Ostatnio zmieniony 9 wrz 2015, o 18:54 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
jutrvy
Użytkownik
Użytkownik
Posty: 1202
Rejestracja: 24 lis 2014, o 18:04
Płeć: Mężczyzna
Podziękował: 10 razy
Pomógł: 239 razy

Własność podzbiorów

Post autor: jutrvy »

Hmm... dla \(\displaystyle{ n=0}\) teza jest oczywista, to może przez indukcję?...

Ustalmy \(\displaystyle{ n\in\NN}\) i załóżmy, że teza jest spełniona dla wszystkich \(\displaystyle{ k < n}\), gdzie \(\displaystyle{ n > 0}\). Wtedy możemy sobie nasze zbiory \(\displaystyle{ A, B}\), troszkę przerobić, to znaczy w ten sposób: \(\displaystyle{ A' = \lbrace a-1: a\in A\rbrace\setminus\lbrace -1\rbrace}\), \(\displaystyle{ B' = \lbrace b-1: b\in B\rbrace\setminus\lbrace -1\rbrace}\). Wówczas \(\displaystyle{ A'\cup B' = \NN}\), oraz \(\displaystyle{ A'\cap B' = \emptyset}\). Na mocy założenia indukcyjnego istnieją takie \(\displaystyle{ a', b'}\), że \(\displaystyle{ \lbrace a', b', a'+b'\rbrace\subseteq A'}\) (lub \(\displaystyle{ B'}\) - nieistotne), gdzie \(\displaystyle{ n-1 < a' < b'}\). To z kolei oznacza, że \(\displaystyle{ \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?
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Własność podzbiorów

Post autor: a4karo »

A dlaczego teza jest oczywista dla \(\displaystyle{ n=0}\)?
Dakurels
Użytkownik
Użytkownik
Posty: 291
Rejestracja: 16 paź 2009, o 18:31
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 55 razy

Własność podzbiorów

Post autor: Dakurels »

Bez straty ogólności załóżmy, że \(\displaystyle{ 1 \in A}\). Łatwo widać, że obydwa zbiory muszą być nieskończone. Więc teraz dwa przypadki:

\(\displaystyle{ 2 \in B}\)

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

\(\displaystyle{ 2 \in A}\)

Wtedy \(\displaystyle{ 3 \in B}\) i robimy jak wyżej tylko zamiast \(\displaystyle{ k-1, k+1}\) bierzemy \(\displaystyle{ k-1, k+2}\).
Awatar użytkownika
jutrvy
Użytkownik
Użytkownik
Posty: 1202
Rejestracja: 24 lis 2014, o 18:04
Płeć: Mężczyzna
Podziękował: 10 razy
Pomógł: 239 razy

Własność podzbiorów

Post autor: jutrvy »

O, dzięki, nawet nie zdążyłem napisać
ODPOWIEDZ