Forum Instytutu Matematycznego UWr

zaraz

Edit by Pokemon: Po mniej więcej godzinie :


To jak już padła podpowiedź, to ja napiszę do czego doszedłem.
Myślę, że twierdzenie o którym mówi pan Newelski brzmi tak:

Definicja:
Niech kolorowaniem zbioru [tex]X^n [/tex]nazwiemy takie kolorowanie wszystkich punktów tego produktu [tex]n[/tex] kolorami, że każda prosta w kierunku [tex]i[/tex] ma tylko skończenie wiele punktów pokolorowanych na kolor [tex]i[/tex] (przy czym prosta w kierunku [tex]i[/tex] to prosta postaci [tex] \{x_{1}\}\times \{x_{2}\} \times ... \times \{x_{i-1}\} \times X \times \{x_{i+1}\} \times ... \times \{x_{n}\}[/tex]).

Twierdzenie:
Zbiór [tex]\aleph_m^{n}[/tex] można pokolorować iff [tex]m\leq n-2[/tex].

Pokażę, że nie ma kolorowania, gdy [tex]m>n-2[/tex].

Pokazać, że nie ma kolorowania dla [tex]\aleph_1^{2}[/tex] jest łatwo. Załóżmy, że takie kolorowanie jest. Wybieramy wtedy [tex]\aleph_0[/tex] prostych o pierwszej współżędnej ustalonej. Niech suma tych prostych tworzy zbiór [tex]A[/tex]. Na tych wszystkich prostych jest tylko [tex]\aleph_0[/tex] punktów o kolorze 1. Istnieje zatem prosta w drugim kierunku, czyli zbiór [tex]\aleph_1 \times \{c\}[/tex] dla pewnego [tex]c[/tex] taki, że [tex](\aleph_1 \times \{c\}) \cap A[/tex] składa się z samych punktów o kolorze 2. Więc na tej prostej jest nieskończenie wiele punktów o kolorze 2.

Załóżmy teraz, że udowodniliśmy już, że nie da się pokolorować zbioru [tex]\aleph_n^{n+1}[/tex] dla [tex]n<m[/tex]. Pokażemy, że nie da się pokolorować zbioru [tex]\aleph_m^{m+1}[/tex]. Załóżmy przeciwnie, że udało nam się to zrobić. Weżmy zbiór [tex]\aleph_{m-1} \subset \aleph_m[/tex] i popatrzmy na zbiór [tex]B = \aleph_{m-1}^m \times \aleph_m[/tex]. [tex]B[/tex] to suma [tex]\aleph_{m-1}[/tex] prostych w kierunku [tex]m+1[/tex], zatem na nich jest w sumie tylko [tex]\aleph_m-1[/tex] punktów o kolorze [tex]m+1[/tex]. Podobnie jak poprzednio istnieje hiperpłaszczyzna [tex]H = \aleph_m^m \times \{c\}[/tex] dla pewnego [tex]c[/tex] taka, że [tex]H \cap B = \aleph_{m-1}^m \times \{c\}[/tex] nie zawiera punktów pokolorowanych na kolor [tex]m+1[/tex]. Czyli zbiór [tex]H \cap B[/tex] jest kolorowany na [tex]m[/tex] kolorów. Z założenia indukcyjnego jest to niemożliwe.
Udowodniliśmy, że nie da się kolorować zbiorów [tex]\aleph_n^{n+1}[/tex]. Oczywiście tymbardziej nie da się kolorowac zbiórów [tex]\aleph_m^{n}[/tex] dla których [tex]m>n-2[/tex].

@MichalM: No tak, w ten sposób zrobił Pan łatwiejszą część dowodu: implikację [tex]\Rightarrow[/tex].

Pokażę że istnieje kolorowanie gdy [tex]m=n-2[/tex], więc również gdy [tex]m<n-2[/tex].

Rozpatrzmy najpierw sytuację dla [tex]\aleph _0^2[/tex]. Parę [tex]<a,b>[/tex] kolorujemy na 1. kolor jeśli[tex]a \leq b[/tex] a na kolor 2. w przeciwnym przypadku. Jeśli popatrzymy na prostą o nie ustalonej 1. współrzędnej [tex]x[/tex], to zobaczymy że istnieje tylko skończenie wiele liczb [tex]y_0\geq x[/tex] zatem i skończenie wiele punktów koloru 1. na tej prostej. Przy nie ustalonej 2. współrzędnej mamy analogiczną sytuację.

Udowodnijmy teraz tezę indukcyjnie względem [tex]m[/tex]. Dla [tex]m=0[/tex] teza zachodzi, przejdźmy zatem do kroku indukcyjnego.

Załóżmy, że [tex]\aleph_{m}^{m+2}[/tex] można pokolorować m+2 kolorami i pokażemy, że [tex]\aleph_{m+1}^{m+3}[/tex] można pokolorować m+3 kolorami.

rozpatrzmy dowolną prostą [tex]i[/tex] i punkt na niej [tex]\alpha[/tex]. Ponieważ [tex]|\alpha|\leq \aleph_{m}[/tex] to podzbiór przestrzeni o i-tej współrzędniej [tex]\alpha[/tex] a pozostałych współrzednych nie większych niż [tex]\alpha[/tex] (nazwijmy go [tex]X_{i,\alpha}[/tex]), na mocy założenia indukcyjnego można pokolorować przy użyciu m+2 kolorów, co też czynimy nie używając i-tego koloru.

Przy tej konstrukcji pewne punkty mogą otrzymać więcej niż jeden kolor, jednak nie trzeba się tym przejmować i można wybrać dowolny z nich.

Pokażmy teraz, że na każdej prostej o nieustalonej i-tej współrzędnej znajduje się tylko skończenie wiele punktów koloru i. Niech [tex]k[/tex] będzie taki, że [tex] c_k=\max{\{c_j:j \neq i\}}[/tex] . Wtedy fragment tej prostej dla [tex]x>c_k[/tex] jest kolorowany przy użyciu kolorów różnych od i, natomiast fragment prostej dla [tex] x\leq c_k[/tex] jest prostą leżącą w [tex]X_{k,c_k}[/tex], a zatem na mocy założenia indukcyjnego jest na nim tylko skończenie wiele punktów i-tego koloru.

A co z prostymi na których punkty miały początkowo więcej niż jeden kolor? Te proste należały jednocześnie maksymalnie do m+2 zbiorów postaci [tex] X_{i , \alpha}[/tex], a na każdym miały skończenie wiele punktów pokolorowanych na każdy kolor j, więc liczba punktów pokolorowanych na j-ty kolor we wszystkich m+2 przestrzeniach również będzie skończona.

Tomek Gogacz

Czy to zadanie ma rozwiązanie dla a, b < [tex]10^9[/tex]? Jeśli nie, to czy mógłby Pan dać jakąś wskazówkę?

W najmniejszym rozwiązaniu, które znam, a, b, c mają odpowiednio 13, 11, 10 cyfr.

Do uzyskania tego rozwiązania wystarczą jednak rachunki na liczbach maksymalnie 3-cyfrowych.

Wskazówka: 8+1=9

_________________
Konsultacje w semestrze letnim 2019/20: wtorki godz. 11-12, czwartki godz. 10-11, pok. 313 (zawieszone w czasie zawieszenia zajęć od 11 marca 2020)
Analiza Matematyczna 2 (lato 2019/20)

Dziękuję za tę wskazówkę.

Rozwiązanie:
[tex]a=2^{15} \cdot 3^{16} = 1410554953728[/tex]
[tex]b=2^{13} \cdot 3^{14} = 39182082048[/tex]
[tex]c=2^{12} \cdot 3^{13} = 6530347008[/tex]

Czy mógłby Pan podać ilość cyfr Pańskiego rozwiązania?

184

_________________
Konsultacje w semestrze letnim 2019/20: wtorki godz. 11-12, czwartki godz. 10-11, pok. 313 (zawieszone w czasie zawieszenia zajęć od 11 marca 2020)
Analiza Matematyczna 2 (lato 2019/20)

Czy mógłby Pan podać dyskretną wskazówkę do tego zadania?