[Teoria liczb][Kombinatoryka] Kilka zadań

[limes123]

Taki minimix - czyli kilka fajnych zadań.
1. Zbiór wszystkich liczb naturalnych podzielono na dwie klasy A i B, a pewna liczba ułamkowa x ma nieskończone rozwinięcie w zapisie dziesiętnym \(\displaystyle{ x=0,x_1x_2x_3...}\). Udowodnij, że ciąg \(\displaystyle{ x_1x_2...}\) można podzielić na takie części skończone \(\displaystyle{ x_1x_2...x_{n_1},x_{n_1+1}x_{n_1+2}...x_{n_2},x_{n_2+1}...}\), że wszystkie one (poza być może pierwszą), rozumiane jako liczby naturalne, należą do tej samej klasy A lub B.
2. Udowodnij, że każda liczba całkowita dodatnia mniejsza od \(\displaystyle{ m=10^{2n}}\), gdzie n jest liczbą całkowitą dodatnią, jest dzielnikiem liczby m lub sumą różnych dzielników liczby m.
3. Kwadrat podzielono dwoma sposobami na 81 części o równych polach. Wykaż, że istnieje wewnątrz kwadratu zbiór 81 punktów o takiej własności: w każdej części dowolnego podziału znajduje się jeden punkt.

[Sylwek]

Istotnie ciekawe te zadanka, skąd je masz?

ad. 2 indukcyjnie - dla n=1 jakoś sobie poradzimy, przypuśćmy, że twierdzenie jest prawdziwe dla n, wówczas rozpatrzmy: \(\displaystyle{ 10^{2(n+1)}=100 10^{2n}}\). Niech P(x) będzie przedstawieniem liczby \(\displaystyle{ x}\) w sposób podany w zadaniu. Zatem każdą liczbę z przedziału \(\displaystyle{ }\) (tą ostatnią wiadomo czemu, a czemu cały zbiór - założenie indukcyjne) da się przedstawić w sposób podany w zadanku. Niech \(\displaystyle{ t \equiv k \ (mod 100)}\), gdy k=0 oczywistość, w innym wypadku k da się przedstawić w sposób podany w zadaniu, niech P(k) to będzie to przedstawienie, ale z drugiej strony: \(\displaystyle{ 10^{2n} \cdot 100 >t>t-k=100y}\) dla pewnego y całkowitego, zatem \(\displaystyle{ yqslant t=100y+k=100P(y)+P(k)}\)

[andkom]

3.
Oczywiście nie ma znaczenia, czy dzielimy kwadrat, czy jakikolwiek inny zbiór o dodatnim polu. Nie ma też znaczenia na ile części dzielimy. Oznaczmy liczbę części przez n. Pole każdej z części oznaczmy t (t>0).
Rozwiązanie zadania jest łatwe, jeśli znamy

Twierdzenie Halla (które można dowieść przez indukcję po |X|)
Niech X i Y będą zbiorami skończonymi. Załóżmy, że dany jest graf, którego wierzchołkami są elementy \(\displaystyle{ X\cup Y}\). Każda krawędź w naszym grafie jest taka, że jeden jej koniec jest w X, a drugi w Y.
Niech ponadto spełniony będzie warunek: Dla każdego \(\displaystyle{ A\subset X}\) mamy
\(\displaystyle{ |\{y\in Y:\exists_{x\in A}\ x}\) jest połączony krawędzią z \(\displaystyle{ y\}|\geqslant|A|}\)
(|A| oznacza liczbę elementów zbioru A.)
Wówczas dla każdego \(\displaystyle{ x\in X}\) można wybrać jedną krawędź o końcu x w taki sposób, że wszystkie wybrane krawędzie (jest ich |X|) mają różne końce w Y.


Jak skorzystać z twierdzenia Halla w naszym zadaniu?
Niech X będzie zbiorem części z jednego podziału, a Y zbiorem części z drugiego podziału. Oczywiście |X|=|Y|=n. Jeśli \(\displaystyle{ x\in X}\) oraz \(\displaystyle{ y\in Y}\), to x i y łączymy krawędzią, gdy \(\displaystyle{ x\cap y\ne\emptyset}\).
Zauważmy, że spełnione są założenia twierdzenia Halla:
Jeśli \(\displaystyle{ A\subset X}\) i \(\displaystyle{ B=\{y\in Y:\exists_{x\in A}\ x}\) jest połączony krawędzią z \(\displaystyle{ y\}=\{y\in Y:\exists_{x\in A}\ x\cap y\ne\emptyset\}}\), to
\(\displaystyle{ \bigcup_{x\in A}x\subset\bigcup_{y\in B}y}\),
a stąd
\(\displaystyle{ t|A|=Pole\left(\bigcup_{x\in A}x\right)\leqslant Pole\left(\bigcup_{y\in B}y\right)=t|B|}\).
Zatem na podstawie twierdzenia Halla istnieje n krawędzi z których każda ma inny koniec w X i inny koniec w Y, czyli istnieje takie ponumerowanie elementów \(\displaystyle{ X=\{x_1,x_2,\ldots,x_n\}}\) oraz \(\displaystyle{ Y=\{y_1,y_2,\ldots,y_n\}}\), że \(\displaystyle{ x_i}\) jest połączone krawędzią z \(\displaystyle{ y_i}\) dla i=1,2,...,n.
Teraz dla i=1,2,...,n niech \(\displaystyle{ A_i}\) będzie dowolnym elementem (niepustego) przecięcia \(\displaystyle{ x_i\cap y_i}\).
Uzyskane punkty \(\displaystyle{ A_1,A_2,\ldots,A_n}\) spełniają żądane warunki, bo jeśli \(\displaystyle{ x\in X}\), to \(\displaystyle{ x=x_i}\) dla pewnego i i mamy \(\displaystyle{ A_i\in x_i=x}\). Podobnie, jeśli \(\displaystyle{ y\in Y}\), to \(\displaystyle{ y=y_i}\) dla pewnego i i mamy \(\displaystyle{ A_i\in y_i=y}\).

Jeśli zamiast dwóch podziałów będziemy mieć trzy, to takiego układu n punktów dobrego dla wszystkich trzech podziałów może nie być.

[limes123]

Sylwek, ładnie. Da się też udowodnić tw. mocniejsze, czyli udowodnić twierdzenie z zadania dla liczb postaci \(\displaystyle{ 4^k5^n}\) gdzie k i n są liczbami naturalnymi. Dowód też ind. przy ustalonym k i po n. Dla n=0 mamy \(\displaystyle{ 2^{2k}}\) i liczba ta jest liczbą o podanej własności (2 się da, zał, że zachodzi dla \(\displaystyle{ 2^s}\), dla \(\displaystyle{ 2^{s+1}}\) jeśli weźmiemy liczbą t taką, że \(\displaystyle{ 2^s<t<2^{s+1}}\) to t również daje się tak przedstawić). Weźmy dowolną liczbę nat. p mniejszą od \(\displaystyle{ 4^k5^{n+1}}\) i podzielny ją przez 5 otrzymując iloraz q i resztę r. \(\displaystyle{ p=5q+r}\) gdzie \(\displaystyle{ q<4^k5^n}\) oraz \(\displaystyle{ 0\leq r\leq 4}\). W myśl zał. q daje się przedstawić w postaci \(\displaystyle{ q=d_1+d_2+...+d_l}\), czyli dla r=1,2,4 \(\displaystyle{ s=5d_1+5d_2+...+5d_l+r}\) czyli zachodzi. Dla r=0 oczywiste. Dla r=3 \(\displaystyle{ s=5d_1+5d_2+...+5d_l+1+2}\) czyli również zachodzi cdk. Teraz wystarczy zauważyć, że \(\displaystyle{ 10^{2n}=4^n5^{2n}}\) i gotowe .
andkom, o grafach niestety nie mam pojęcia a moje rozwiązanie opiera się na wykorzystaniu tw. Birkhoffa (z którego wynika od razu teza). Jego treść oraz dowód wrzucę później

1 i 3 z musztariego 2 trochę zmodyfikowałem zadanie z którejś OM;p

[Dumel]

Sylwek, tutaj nie powinno być \(\displaystyle{ 10^{2(n+1)}}\):

\(\displaystyle{ 10^{2n} \cdot 100 >t}\)

?

[Sylwek]

Nie, troszkę skróciłem zapis, liczba t jest mniejsza od \(\displaystyle{ 10^{2(n+1)}}\) (założenie zadania) oraz większa od 100y. Zatem \(\displaystyle{ 10^{2(n+1)}>100y \iff 10^{2n} \cdot 100 > 100y \iff 10^{2n}>y}\)

A chyba nie o to Ci chodziło, po prostu zauważ: \(\displaystyle{ 10^{2(n+1)} = 10^{2n}\cdot100}\)

[ Dodano: 30 Lipca 2008, 00:21 ]

1 i 3 z musztariego

kurcze muszę sobie tą książeczkę w końcu załatwić, bo nawet w tym roku nie zrobiłem banalnej kombi na 2. etapie, nie mówiąc już o takich zadaniach, które wymagają bardzo zaawansowanych twierdzeń (Twierdzenie Halla, tw. Birkhoffa oO)

[Dumel]

możesz zalatwic tez sobie "złote rybki w oceanie matematyki"- najlepsza książka do kombinatoryki (tzn. 1/3 książki) jaką czytałem

[limes123]

W musztarim jest dość dużo kombinatoryki (dość ciekawe sposoby, twierdzenia, fajny dział o niezmiennikach), trochę gier i ogólnie sporo takich zadań na znalezienie jakiegoś pomysłowego rozwiązania często średnio skomplikowanego. Oooo a jakie inne działy są jeszcze w "złotych rybkach..."?

[Edit]
A co do tw. Birkhoffa to może nie jest ono bardzo przydatne ale warto znać.
Jeśli dowolny kwadrat podzielimy dwoma sposobami na n części o równych polach, to w tym kwadracie istnieje zbiór n punktów takich, że w każdej części z obu podziałów leży punkt. Z wrzuceniem dowodu może poczekam, może ktoś chce pomyśleć nad swoim A po drugie ten z Musztariego jest długi :p

[Dumel]

Oooo a jakie inne działy są jeszcze w "złotych rybkach..."?

dział II- geometria - dużo ciekawych własności trójkąta prostokątnego, troche o geometrii kombinatorycznej, elementach wymiernych trójkąta i (to akurat mało przydatne) o rozinaniu figur
dział III- metody geometryczne w arytmetyce- krzywe eliptyczne

jakbyś sie zdecydował kupić to uważaj na jeden podrozdział ("szklane kule") w dziale o kombinatoryce bo chyba jest w jeden nim spory błąd merytoryczny

[limes123]

Dobra zapamiętam no to zostało 1

[ Dodano: 13 Sierpnia 2008, 19:57 ]
Widzę, że pierwsze dalej bez rozwiązania, a nie jest wcale takie trudne jak na pierwszy rzut oka, więc może mała podpowiedź. To jest z działu "zadania z alternatywą" i wystarczy rozważyć dwa różne przypadki.......

[ Dodano: 23 Sierpnia 2008, 14:20 ]
Przypadek 1 - istnieje niekończenie wiele cyfr, dla których każdy odcinek tego ciągu zaczynający sie od jednej z nich należy do klasy A.
Przypadek 2 - przypadek 1 nie zachodzi.
1 jest prawdziwe - trywialne.
2 jest prawdziwe. Wtedy zaczynając od pierwszej cyfry tego ciągu w końcu trafimy na taką, że istnieje dla niej nieskończenie wiele liczb zaczynających się od niej i należących do B (jeśli taka cyfra by nie istaniała, to 2 nie byłoby prawdziwe). Jak już ją znajdziemy to znowu wykonujemy taką operację i znajdujemy kolejną cyfrę, dla której istnieje nieskończenie wiele liczb należących do B, i znowu kończymy ją tak by otrzymać kolejną cyfrę od tej własności itd itd... W ten sposób otrzymamy same (być może oprócz pierwszej) liczby należące do B ckd.