Problem 1
Każda liczba całkowita dodatnia jest pomalowana jednym z kolorów: czerwonym lub niebieskim. Udowodnić, że istnieje ciąg nieskończony \(\displaystyle{ a_1< a_2 < a_3< ...}\) taki, że ciąg \(\displaystyle{ a_1, \frac{a_1+a_2}{2}, a_2, \frac{a_2+a_3}{2}, a_3, ... }\) jest jednokolorowy
Kolorowe liczby
- mol_ksiazkowy
- Użytkownik
- Posty: 11415
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Kolorowe liczby
Zadanie polega na kolorowaniu ciągu liczb całkowitych dodatnich dwoma kolorami, otóż po takim kolorowaniu zawsze otrzymamy zbiór monochromatyczny , którego Asymptotyczna górna gęstość jest większa od zera...
Znaczy, że:
\(\displaystyle{ \limsup_{n\to\infty} \frac{|A \cap \left\{ 1,2,3,...,n\right\}| }{n}>0 }\)
Z Twierdzenia Szemer´ediego wynika, że taki ciąg zawiera ciąg arytmetyczny o długości np. trzy...
W tym zadaniu mamy udowodnić, że w takim dwukolorowaniu istnieje zbiór monochromatyczny zawierający ciągi arytmetyczne długości trzy i ma być ich nieskończenie wiele...
\(\displaystyle{ (a_{1} , a_{2} , (a_{3}), a_{4} , (a_{5}) , a_{6}, (a_{7}),a_{8},...}\)
Jak widać trójki w nawiasach mają tworzyć ciągi arytmetyczne...
Jak na razie wykazaliśmy, że istnieje jedna trójka w zbiorze \(\displaystyle{ A}\) tworząca ciąg arytmetyczny wynika to z teorii Ramseya...
\(\displaystyle{ a, a+m, a+2m}\),...
Ale teraz korzystając z Twierdzenia Bergelsona-Leibmana, nam wystarczy jego okrojona wersja a mianowicie:
Przypomnijmy je dla: \(\displaystyle{ k=3}\)
\(\displaystyle{ P_{1}, P_{2}, P_{3}}\) - wielomiany o współczynnikach całkowitych, gdzie: \(\displaystyle{ P_{i}(0)=0}\)
To zbiór postaci:
\(\displaystyle{ \left\{ a+P_{1}(x) , a+P_{1}(x) ,a+P_{1}(x) \right\} }\) należy do dowolnego podzbioru liczb całkowitych dodatnich o niezerowej asymptotycznej gęstości górnej...
Czyli u nas zbiór ten może należeć do naszego zbioru \(\displaystyle{ A}\) monochromatycznego o niezerowej gęstości górnej...
Dobierzmy teraz nasze wielomiany:
Niech:
\(\displaystyle{ P_{1}(x)=0 , P_{2}(x)=x , P_{3}(x)=2x}\)
I teraz przeprowadźmy konstrukcję:
mamy:
\(\displaystyle{ a, a+m, a+2m =a+2m+P_{1}(t_{1}) , a+2m+P_{2}(t_{1})=a+2m+t_{1} , a+2m+P_{3}(t_{1})=a+2m+2t_{1} =a+2m+2t_{1}+P_{1}(t_{2}) , a+2m+t_{1}+P_{2}(t_{2})=a+2m+t_{1}+t_{2} , a+2m+t_{1}+P_{3}(t_{2})=a+2m+2t_{1}+2t_{2},...}\)
Otrzymamy w ten sposób:
\(\displaystyle{ a, a+m, a+2m , a+2m+t_{1} , a+2m+2t_{1} ,a+2m+2t_{1}+t_{2} , a+2m+2t_{1}+2t_{2},...}\)
Liczby te należą do naszego monochromatycznego zbioru \(\displaystyle{ A}\) o niezerowej gęstości górnej...
Jak widać zbiór ten spełnia warunki naszego zadania, cnd...
Znaczy, że:
\(\displaystyle{ \limsup_{n\to\infty} \frac{|A \cap \left\{ 1,2,3,...,n\right\}| }{n}>0 }\)
Z Twierdzenia Szemer´ediego wynika, że taki ciąg zawiera ciąg arytmetyczny o długości np. trzy...
W tym zadaniu mamy udowodnić, że w takim dwukolorowaniu istnieje zbiór monochromatyczny zawierający ciągi arytmetyczne długości trzy i ma być ich nieskończenie wiele...
\(\displaystyle{ (a_{1} , a_{2} , (a_{3}), a_{4} , (a_{5}) , a_{6}, (a_{7}),a_{8},...}\)
Jak widać trójki w nawiasach mają tworzyć ciągi arytmetyczne...
Jak na razie wykazaliśmy, że istnieje jedna trójka w zbiorze \(\displaystyle{ A}\) tworząca ciąg arytmetyczny wynika to z teorii Ramseya...
\(\displaystyle{ a, a+m, a+2m}\),...
Ale teraz korzystając z Twierdzenia Bergelsona-Leibmana, nam wystarczy jego okrojona wersja a mianowicie:
Przypomnijmy je dla: \(\displaystyle{ k=3}\)
\(\displaystyle{ P_{1}, P_{2}, P_{3}}\) - wielomiany o współczynnikach całkowitych, gdzie: \(\displaystyle{ P_{i}(0)=0}\)
To zbiór postaci:
\(\displaystyle{ \left\{ a+P_{1}(x) , a+P_{1}(x) ,a+P_{1}(x) \right\} }\) należy do dowolnego podzbioru liczb całkowitych dodatnich o niezerowej asymptotycznej gęstości górnej...
Czyli u nas zbiór ten może należeć do naszego zbioru \(\displaystyle{ A}\) monochromatycznego o niezerowej gęstości górnej...
Dobierzmy teraz nasze wielomiany:
Niech:
\(\displaystyle{ P_{1}(x)=0 , P_{2}(x)=x , P_{3}(x)=2x}\)
I teraz przeprowadźmy konstrukcję:
mamy:
\(\displaystyle{ a, a+m, a+2m =a+2m+P_{1}(t_{1}) , a+2m+P_{2}(t_{1})=a+2m+t_{1} , a+2m+P_{3}(t_{1})=a+2m+2t_{1} =a+2m+2t_{1}+P_{1}(t_{2}) , a+2m+t_{1}+P_{2}(t_{2})=a+2m+t_{1}+t_{2} , a+2m+t_{1}+P_{3}(t_{2})=a+2m+2t_{1}+2t_{2},...}\)
Otrzymamy w ten sposób:
\(\displaystyle{ a, a+m, a+2m , a+2m+t_{1} , a+2m+2t_{1} ,a+2m+2t_{1}+t_{2} , a+2m+2t_{1}+2t_{2},...}\)
Liczby te należą do naszego monochromatycznego zbioru \(\displaystyle{ A}\) o niezerowej gęstości górnej...
Jak widać zbiór ten spełnia warunki naszego zadania, cnd...