Kolorowe liczby

[mol_ksiazkowy]

Czy można wszystkie liczby rzeczywiste nieujemne pomalować jednym z kolorów: białym lub czarnym, tak aby nie było żadnej trójki \(\displaystyle{ a, b, c}\) kolejnych wyrazów ciągu arytmetycznego jednokolorowych ?

To samo pytanie dla zbioru liczb całkowitych nieujemnych ?

[3a174ad9764fefcb]

Ukryta treść:    

Nie da się tak pokolorować zbioru liczb całkowitych nieujemnych. Niech \(a_n\in\{c,b\}\) oznacza kolor liczby całkowitej nieujemnej \(n\). Wśród wyrazów \(a_2, a_3, a_4\) są co najmniej dwa takie same kolory, powiedzmy \(a_i=a_j=c\), gdzie \(i<j\). W ciągu arytmetycznym \(2i-j, i, j, 2j-i, \ldots, 11j-10i\) znajdziemy trójwyrazowy podciąg arytmetyczny jednokolorowy.

Jeśli \(a_{2j-i}=c\) to mamy jednokolorowy ciąg \(i, j, 2j-i\). Tak samo jeśli \(a_{2i-j}=c\) to mamy ciąg \(2i-j,i,j\). Dalej więc rozpatrzmy sytuację, gdy \(a_{2j-i}=a_{2i-j}=b\), czyli nasz rozpatrywany ciąg kolorów wygląda tak: \(b,c,c,b,\ldots\).

Teraz jeśli \(a_{5j-4i}=b\), to mamy ciąg arytmetyczny \(2i-j, 2j-i, 5j-4i\) w kolorze \(b\). W przeciwnym wypadku \(a_{5j-4i}=c\) i dostajemy ciąg kolorów \(b,c,c,b,?,?,c\).

Następnie jeśli \(a_{9j-8i}=c\) lub \(a_{10j-9i}=c\), to otrzymujemy trójwyrazowy ciąg \(a_i = a_{5j-4i}= a_{10j-9i}=c\) lub \(a_j = a_{5j-4i}= a_{9j-8i}=c\). W przeciwnym razie mamy \(a_{9j-8i}=a_{10j-9i}=b\) i nasz ciąg wygląda tak: \(b,c,c,b,?,?,c,?,?,?,b,b\).

Na końcu ciągu mamy dwa wyrazy w kolorze \(b\). Jeśli któryś sąsiadujący z nimi wyraz także jest \(b\), to mamy ciąg jaki chcieliśmy. W przeciwnym wypadku otrzymujemy: \(b,c,c,b,?,?,c,?,?,c,b,b,c\), ale tu także mamy już podciąg arytmetyczny jednokolorowy \(a_{5j-4i}=a_{8j-7i}=a_{11j-10i}=c\).

A gdybyśmy szukali ciągów czteroelementowych? Tu już próba dowodu w podobny sposób byłaby skomplikowana, więc może warto poszukać jakiegoś ogólniejszego dowodu.

[timon92]

@up zawsze będą istnieć dowolnie długie (ale skończone) monochromatyczne ciągi arytmetyczne --- zgooglaj sobie twierdzenie van der Waerdena

[Dasio11]

Weźmy dowolne kolorowanie liczb całkowitych/rzeczywistych nieujemnych. Przynajmniej dwa z elementów \(\displaystyle{ 4, 6, 8}\) są jednokolorowe - oznaczmy je przez \(\displaystyle{ a, b}\) i załóżmy bez zmniejszania ogólności, że są czarne. Jeśli wszystkie trzy liczby całkowite \(\displaystyle{ 2a-b, \frac{a+b}{2}, 2b-a}\) są białe, to tworzą biały ciąg arytmetyczny. A jeśli choć jedna jest czarna, to wraz z \(\displaystyle{ a}\) i \(\displaystyle{ b}\) tworzą czarny ciąg arytmetyczny. Tak czy owak, jednokolorowy ciąg istnieje.