[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)

[arek1357]

A dla których dokładnie punktów to robisz?

Robię to dokładnie dla punktów ze zbioru A, każda krawędź w tym dwudzielnym grafie odpowiada jednemu punktowi na prostej poziomej...

[Dasio11]

Jaką masz zatem pewność, że dla każdego punktu w zbiorze \(\displaystyle{ B}\) kolory krawędzi zeń wychodzących będą zrównoważone?

[arek1357]

punkty (krawędzie) zbioru A pokrywają się z punktami (krawędziami wychodzącymi ze zbioru B)...

Każdy taki punkt to częś wspólna prostej poziomej i pionowej...

Natomiast w tym drugim powinienem dopisać bo możliwe, że z tego za bardzo nie wynikało ,kontrprzykład w sumie słuszny,
ale jak mamy punkt P w którym są dwa przejścia i ten punkt otaczają krawędzie:

\(\displaystyle{ (a_{1},a_{2},...,a_{m},b_{1},b_{2},...,b_{n})}\)

I teraz rozdzielmy ten punkt na dwa:

\(\displaystyle{ (a_{k+1},...,a_{m},b_{1},...,b_{l}) , 0<k<m \wedge 0<l<n}\) - krawędzie czerwone

\(\displaystyle{ b_{l+1},,...,b_{n},a_{1},...a_{k}}\) - krawędzie zielone

To wtedy niezależnie od koloru odcinka \(\displaystyle{ AB}\) , wierzchołki A i B będą wierzchołkami, w których są co najwyżej dwa przejścia...

I nie zajdzie splątanie jak na Twoim rysunku...

Może teraz będzie to jaśniejsze...

[Dasio11]

punkty (krawędzie) zbioru A pokrywają się z punktami (krawędziami wychodzącymi ze zbioru B)...

Każdy taki punkt to częś wspólna prostej poziomej i pionowej...

Ponieważ mam wrażenie, że to nie odpowiada na moje pytanie, zadam je tym razem w języku oryginalnego zadania, bez wspominania Twojego grafu, i proszę byś odpowiedział w ten sam sposób:

Jeśli dobrze rozumiem Twój algorytm, to na każdej prostej poziomej malujesz dowolną połowę punktów na czerwono, a drugą połowę na zielono (zaokrąglając w przypadku gdy ich liczba jest nieparzysta). Ale w takim razie nie ma żadnej gwarancji, że na każdej prostej pionowej około połowa punktów będzie czerwona, łatwo zresztą skonstruować odpowiednio kontrprzykład.

[arek1357]

Zad. 11.

Ukryta treść:    

Niech:

\(\displaystyle{ P=\left\{ 1,2,3,...,326\right\} }\)

\(\displaystyle{ 326:5=65 r 1}\)

Znaczy, że istnieje zbiór pomalowany na jeden kolor ...

niech będzie to zbiór A

\(\displaystyle{ A=\left\{ a_{1}<a_{2}<...<a_{66}\right\} }\)

Twórzmy różnice:

\(\displaystyle{ a_{2}-a_{1},a_{3}-a_{1},...,a_{66}-a_{1}}\)

Oznaczmy je przez \(\displaystyle{ b_{i}}\)

Niech:

\(\displaystyle{ B'=\left\{ b_{1},b_{2},...,b_{65} \right\} }\)

Jeżeli teraz \(\displaystyle{ b_{i} \in A}\) to po zadaniu

Ale może się zdarzyć, że żadne \(\displaystyle{ b_{i}}\) nie należy do A

Zostaje nam cztery kolory, podzielmy:

\(\displaystyle{ 65:4=16 r 1}\)

Zatem istnieje kolor drugi gdzie musi być pomalowane siedemnaście elementów zbioru B'

Mamy więc:

\(\displaystyle{ B=\left\{ b_{1},b_{2},...,b_{17}\right\} }\) o tym samym kolorze

Nie mylić \(\displaystyle{ b_{i}}\) ze zbioru B' i B nie muszą być w tej samej kolejności...

Twórzmy teraz różnice:

\(\displaystyle{ b_{2}-b_{1},b_{3}-b_{1},...,b_{17}-b_{1}}\)

Oznaczmy różnice przez \(\displaystyle{ c_{i}}\)

niech teraz:

\(\displaystyle{ C'=\left\{ c_{1},c_{2},...,c_{16}\right\} }\)

jeżeli któreś \(\displaystyle{ c_{i} \in B}\)

To teza spełnione , jeżeli jednak nie to mamy do dyspozycji trzy kolory i wiemy, że :

\(\displaystyle{ 16:3=5 r 1}\)

Więc mamy zbiór :

\(\displaystyle{ C=\left\{ c_{1},c_{2},...,c_{6}\right\} }\) jednokolorowy sześcioelementowy...

Tworzymy teraz różnice:

\(\displaystyle{ c_{2}-c_{1},c_{3}-c_{1},...,c_{6}-c_{1}}\)

Oznaczamy je:

\(\displaystyle{ d_{i}}\)

Czyli:

\(\displaystyle{ D'=\left\{ d_{1},d_{2},...,d_{5}\right\}}\)

jeżeli któreś \(\displaystyle{ d_{i} \in C}\) - to teza spełniona

Ale tak być nie musi, więc mamy do dyspozycji jeszcze dwa kolory:

\(\displaystyle{ 5:2=2 r 1}\)

Znaczy, że trzy elementy zbioru D' mają jeden z dwóch ostatnich kolorów:

\(\displaystyle{ D'=\left\{ d_{1},d_{2},d_{3}\right\} }\) - te elementy mają jeden kolor

Utwórzmy różnice:

\(\displaystyle{ d_{3}-d_{2},d_{2}-d_{1},d_{3}-d_{1}}\)

Jeżeli któraś z tych różnic leży w zbiorze D' to po zadaniu teza spełniona,

Ale tak być nie musi , czyli oznacza to , że te trzy różnice mają ostatni kolor czyli leżą w zbiorze D

\(\displaystyle{ D=\left\{ d_{3}-d_{2},d_{2}-d_{1},d_{3}-d_{1}\right\} }\)

Ale to też oznacza koniec zadania ponieważ:

\(\displaystyle{ d_{3}-d_{1}=d_{3}-d_{2}+d_{2}-d_{1}}\)

Czyli jedna liczba ze zbioru C jest sumą dwóch pozostałych , a wszystkie są jednokolorowe

Dodano po 10 minutach 30 sekundach:
Tak już czaję co masz na myśli, masz rację, przemyślę to jeszcze bo dla pionowych i poziomych jednocześnie nie musi to działa , dzięki za uwagę...

Dodano po 1 godzinie 9 sekundach:
Taki pomysł na szybko co mi wpadł do głowy do tego pierwszego to takie kolorowanie:

Dalej zostajemy przy grafie dwudzielnym:

\(\displaystyle{ A \cup B}\)

Wybieramy ten wierzchołek grafu, którego stopień jest najniższy, w przypadku wierzchołków o równych stopniach nie ma to znaczenia , który wybierzemy...

I tak jak wybraliśmy wierzchołek dajmy na to ze zbioru B ten o najmniejszym stopniu to numerujemy kolorami jego krawędzie:

Na przemian.:\(\displaystyle{ 1,0,1,0,1,...}\) - krok pierwszy

Oczywiście przez to numerowanie obniżyliśmy stopnie w zbiorze wierzchołków A, dla ułatwienia możemy ponumerowane krawędzie wymazać...
Mając już dalej graf dwudzielny ale "mniejszy"...(Jeżeli z wierzchołka nie wychodzi żadna krawędź bo wymazane to też go mażemy)...

W tym "mniejszym" grafie przeprowadzamy rozumowanie identyczne jak w kroku 1, otrzymując graf jeszcze mniejszy....

Postępujemy tak aż do wymazania wszystkich krawędzi ...

I tak ponumerowane krawędzie kolorami powinny spełniać naszą tezę, choć jeszcze do końca nie jestem pewny , uwagi mile widziane...

Dodano po 38 minutach 26 sekundach:
zad. 10

Ukryta treść:    

W zadaniu 10 sprawa jest prosta, kluczem do zrozumienia jest fakt, że jeżeli mamy region o n krawędziach , znaczy, że graniczy on z n regionami,
ale te regiony nie graniczą ze sobą , więc każdy z tych regionów malujemy kolorem np.: 1 (regiony to zbiory wypukłe)...

łatwo widać, że można zastosować tu graf wielodzielny, zastosować taki podział:

Weźmy jakiś obszar \(\displaystyle{ a_{1}}\), graniczący z n obszarami (które nie graniczą ze sobą) \(\displaystyle{ b_{i}}\)

Obszar ten umieśćmy w zbiorze \(\displaystyle{ A_{1}}\) , do obszaru \(\displaystyle{ A_{1}}\) wrzućmy te obszary jeszcze , które graniczą z obszarami\(\displaystyle{ b_{i}}\), nazwijmy je \(\displaystyle{ a_{i}}\) , razem z \(\displaystyle{ a_{1} }\) oczywiście...

Obszary \(\displaystyle{ b_{i}}\) wrzućmy do Zbioru \(\displaystyle{ A_{2}}\), teraz do zbioru\(\displaystyle{ A_{3}}\) wrzućmy obszary graniczące z \(\displaystyle{ a_{i}}\) ale nie graniczące z \(\displaystyle{ b_{i}}\)

Tak skonstruujemy graf n -dzielny:

\(\displaystyle{ A_{1},A_{2},A_{3},...A_{n}}\) , możemy je kolorować naprzemiennie \(\displaystyle{ 1,0,1,0,1...}\) nie powodując kolizji...

Dodano po 2 godzinach 37 minutach 30 sekundach:
Uwaga do numerowania:

Jeżeli za pierwszym razem numerujemy na przykład:

\(\displaystyle{ 1,0,1,0,1,...}\)

To w drugim numerowaniu (drugi krok) powinniśmy na odwrót:

\(\displaystyle{ 0,1,0,1,0...}\)

Potem znowu jak w pierwszym kroku, itd...

Dodano po 10 godzinach 31 minutach 21 sekundach:
W 8 wyszło mi maksymalnie dla \(\displaystyle{ n=4}\)

Dodano po 1 dniu 3 godzinach 41 minutach 51 sekundach:
Zad. 13. najciekawsze...

Ukryta treść:    

Warunek:

\(\displaystyle{ i, |k-i|}\), są pomalowane tym samym kolorem daje bardzo ciekawą obserwację, że liczby:

\(\displaystyle{ 1,1+k,1+2k,....}\)

\(\displaystyle{ 2,2+k,2+2k,....}\)

............................................

\(\displaystyle{ k,2k, 3k,....}\)

Każdy ciąg też jest pomalowany tym samym kolorem...

Tworzą ciągi arytmetyczne o różnicy \(\displaystyle{ k}\) generując cały zbiór: \(\displaystyle{ \left\{ 1,2,3,...,n-1\right\} }\)

łatwo też zauważyć, że ciągi:

\(\displaystyle{ s, s+k,s+2k,... \wedge (k-s),(k-s)+2k,(k-s)+3k,..., k>s}\)

też są pomalowane tym samym kolorem...

Teraz wystarczy wszystkie te ciągi zmodulić modulo k...

I otrzymamy:

\(\displaystyle{ Z_{k}=\left\{ 0,1,2,3,...k-1\right\} }\)

Potraktujmy to jak grupę cykliczną z dodawaniem modulo...

Zauważmy, że każdy element tej grupy to w sumie jeden ciąg arytmetyczny ...

Ale jeszcze nie użyliśmy danego nam warunku, że:

\(\displaystyle{ i}\) oraz.: \(\displaystyle{ n-i}\) - są pomalowane na jeden kolor...

A to oznacza tyle, że skoro \(\displaystyle{ (n,k)=1}\) - bardzo ważny warunek

więc jeżeli:

\(\displaystyle{ n=r \mod k}\)

to \(\displaystyle{ r}\) jest generatorem tejże grupy , a co za tym idzie, że wszystkie elementy tej grupy są wymalowane jednym kolorem a co za tym idzie wszystkie ciągi mają jeden kolor, czyli wszystkie elementy zbioru wyjściowego mają jeden kolor cnd...

Próbowałem to najpierw rozbijać na grafy, działało(tylko dla konkretnych liczb) ale nijak nie dawało się uogólnić...