Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
1.Rozważmy kratę \(\displaystyle{ \mathbb{Z}^2}\) na płaszczyźnie. Początkową kongurację kamyków tworzymy układając kamyki w punktach płaszczyzny o współrzędnych całkowitych na osi OX i pod nią. Mając daną kongurację początkową możemy przesuwać kamyki w następujący sposób: jeżeli dwa kamyki sąsiadują ze sobą poziomo lub pionowo, możemy jednym z nich przeskoczyć drugi, o ile w miejscu lądowania nie ma innego kamyka. Po takim ruchu kamyk przeskakiwany usuwamy z kraty, a skaczący kamyk przesuwa się o dwa kroki poziomo lub pionowo. Początkową konfigurację wybieramy w taki sposób, aby wykonując dozwolone ruchy dowolna ilość razy dotrzec jak najdalej w górę kraty. Pokazać, że nie istnieje skończona początkowa konfiguracja kamyków umożliwiająca dotarcie do poziomu 5.
2.Czy istnieje podzbiór zbioru liczb rzeczywistych, który jest domknięty, nieprzeliczalny i rozłączny ze zbiorem liczb wymiernych?
3.Niech n będzie liczbą naturalną. Definiujemy \(\displaystyle{ a_k=\frac{1}{ {n \choose k} }}\) oraz \(\displaystyle{ b_k=2^{k-n}}\) dla \(\displaystyle{ k=1,2,...,n}\). Pokazać, że \(\displaystyle{ \sum_{i=1}^{n} \frac{a_i-b_i}{i}=0}\)
4.Mamy sobie skoczka który skacze po prostej linii, wykonuje on n ruchów przy czym każdy jest innej długości i nie większej niż n. Tzn. wykonuje ruchy długości \(\displaystyle{ 1;2;3;....n-1;n}\) przy czym w dowolnej kolejności. Czy jest możliwe, aby ustawiając na drodze n-1 min skoczek nie mógł przejść?
No to może dorzucę jeszcze dwa zadanka z tegoż konkursu: 5. Oblicz resztę z dzielenia przez 20 liczby \(\displaystyle{ \left\lfloor (5+\sqrt{29})^{1120} \right\rfloor}\) 6. Czy dla dowolnej liczby naturalnej k istnieje wielomian \(\displaystyle{ Q_k}\) k- zmiennych, taki że \(\displaystyle{ Q_k: \mathbb N^k \to \mathbb{N}}\) jest bijekcją
Ostatnio zmieniony 31 lip 2011, o 18:23 przez exupery, łącznie zmieniany 5 razy.
Ponieważ bazę topologii stanowią przedziały otwarte, to każdy zbiór otwarty jest sumą pewnej liczby rozłącznych przedziałów. Ponieważ każdy przedział zawiera liczbę wymierną, to rozłącznych przedziałów nie może być nieprzeliczalnie wiele. Zatem każdy zbiór otwarty jest sumą przeliczalnie wielu rozłącznych przedziałów. Dopełnieniem zbioru tej postaci jest suma rozłącznych przedziałów domkniętych oraz singletonów. Ponownie, ponieważ każdy przedział zawiera liczbę wymierną, to zbiór domknięty, który jest rozłączny z Q, nie zawiera żadnego przedziału,jest więc sumą przeliczalnej liczby singletonów. Zatem zbiór o podanych własnościach nie istnieje.
no to może przedstawię mniej inwazyjną metodę na zad 2.
Ukryta treść:
\(\displaystyle{ A=\left\{ x \in (0,1): x=0.a_10a_2a_30a_4a_5a_60a_7... a_i \in \left\{ 4,5\right\} \quad dla \quad i \in \mathbb N \right\}}\)
Nieprzeliczalność i fakt, że zawiera on tylko liczby niewymierne widać od razu, udowodnijmy domkniętość.
Niech \(\displaystyle{ \left\{ x_n\right\} _{n=1}^{ \infty } \subset A}\). Oraz niech \(\displaystyle{ \lim_{n \to \infty } x_n=x}\). Trzeba pokazać, że \(\displaystyle{ x \in A}\). Niech \(\displaystyle{ x_n=0.a_1(n)0a_2(n)a_3(n)0a_4(n)...}\) \(\displaystyle{ x=0.b_1b_2b_3...}\) Wówczas dla każdego i zachodzi \(\displaystyle{ \lim_{n \to \infty } a_i(n)=b_i}\) Co kończy dowód
Hahaha słynna "piąta kolumna" !
Rozwiązanie oczywiście nie jest mojego autorstwa.
Piąta kolumna:
Załóżmy, że jakiś pionek doszedł do 5 wiersza. W to pole wpisujemy liczbę 1, a w pozostałe pola wpisujemy \(\displaystyle{ \phi^d}\), gdzie \(\displaystyle{ \phi}\), to dodatni pierwiastek równania \(\displaystyle{ x^2+x-1=0}\), a \(\displaystyle{ d}\) to odległość pola od tamtego, w które wpisaliśmy liczbę 1, w metryce miejskiej, czyli po prostu suma odległości po iksie i po igreku.
Przyjmijmy jako półniezmiennik sumę wartości pól, na których stoją wszystkie kamyki. Zauważmy, że z określenia \(\displaystyle{ \phi}\) wynika, że nasz półniezmiennik się nigdy nie zwiększa. Gdyby udało się dojść do 5 wiersza, to ta suma byłaby równa 1, lecz po pewnych obliczeniach wychodzi, że suma liczb, na których mogą stać pionki na początku jest mniejsza od 1.
Z jednej strony można, wystarczy postawić minę w punkcie \(\displaystyle{ \frac{n(n+1)}{2}}\).
Jednak jeśli założymy, że nie wolno kłaść miny właśnie tam, skoczek zawsze będzie mógł przejść. Zachodzi ogólniejsze twierdzenie:
Skoczek ma do dyspozycji n skoków o naturalnych długościach \(\displaystyle{ a_1 < a_2 < ... <a_n}\). Zbiór \(\displaystyle{ M}\) zawiera \(\displaystyle{ n-1}\) liczb całkowitych, przy czym nie zawiera sumy skoków. Wówczas skoczek startując z zera może tak zaplanować kolejność skoków, że ani razu nie odwiedzi punktu należącego do \(\displaystyle{ M}\).
Łatwy dowód przez indukcję:
Dla \(\displaystyle{ n=1,2}\) sprawa jest trywialna.
Teraz niech \(\displaystyle{ d}\) oznacza najmniejszą liczbę w \(\displaystyle{ M}\). Dwa przypadki:
1) \(\displaystyle{ d<a_n}\)
Wtedy, jeśli \(\displaystyle{ M}\) nie zawiera liczby \(\displaystyle{ a_n}\), to wykonujemy pierwszy skok o tejże długości, przeskakując co najmniej jeden element z \(\displaystyle{ M}\), resztę skoków możemy zrobić na mocy założenia.
Gdy jednak \(\displaystyle{ a_n \in M}\), to rozważamy zbiory \(\displaystyle{ \left\{ a_n \right\}, \left\{ a_1,a_1+a_n \right\}, \left\{ a_2, a_2+a_n \right\} , ... , \left\{ a_{n-1},a_{n-1}+a_n \right\}}\). Są one oczywiście rozłączne, więc któryś jest rozłączny ze zbiorem \(\displaystyle{ M}\), powiedzmy ten który ma w środku indeks \(\displaystyle{ k}\). Wtedy robimy na początku dwa skoki: \(\displaystyle{ a_k}\) i \(\displaystyle{ a_n}\), przeskakując punkty \(\displaystyle{ d}\) i \(\displaystyle{ a_n}\), które należą do M. Dalej na mocy założenia.
2) \(\displaystyle{ d \ge a_n}\)
Teraz robimy pierwszy skok \(\displaystyle{ a_n}\), i stosujemy założenie indukcyjne do zbioru \(\displaystyle{ M \setminus \left\{ a_n \right\}}\). Wtedy są dwie opcje: albo przeskoczyliśmy wszystko, albo nadzialiśmy się na \(\displaystyle{ a_n}\). Jak zachodzi pierwsza to jest fajnie, a jak nie:
Powiedzmy, że trafiamy na \(\displaystyle{ a_n}\) po \(\displaystyle{ m}\) skokach. Wiemy, że pierwszy skok to \(\displaystyle{ a_n}\), czyli najdłuższy. Teraz robimy myk, że przekręcamy cyklicznie pierwsze \(\displaystyle{ m+1}\) skoków: pierwszy skok to teraz wcześniejszy drugi, drugi to wcześniejszy trzeci, ... \(\displaystyle{ m}\)-ty to wcześniejszy \(\displaystyle{ (m+1)}\)-szy, a ostatni to \(\displaystyle{ a_n}\). Resztę zostawiamy w spokoju. Łatwo się przekonać, że wtedy przeskakujemy wszystko co trzeba, koniec.
Trochę się spóźniłem z tym rozwiązaniem, ale jak już zrobiłem to napisze
4:
Skoczek zawsze będzie mógł przejść. Pokażmy to indukcyjnie. Dla n=1 teza zadania jest oczywista. Załóżmy teraz ze teza spełniona jest dla n-1. Rozpatrzmy trzy przypadki:
1. na pierwszych n-1 polach jest przynajmniej jedna mina, a w polu n-tym jej nie ma
2. na n-tym polu jest mina
3. nie ma miny na pierwszych n polach
Ad. 1:
Skaczemy o n pól, na pozostałych polach jest wystarczająco mało min, aby skoczek mógł przeskoczyć obijając je.
Ad. 2:
Niech \(\displaystyle{ X=\left\{ x_1, x_2, ...\right\}}\) będzie zbiorem pozycji min z pól 1, ..., n-1. Ustawmy nowe miny na polach \(\displaystyle{ x_1+n, x_2+n, ...}\). Z założenia idukcyjnego wynika, że da się dojść z pola n do końca trasy skoczka omijając wszystkie miny(poza tą na polu n-tym), niech \(\displaystyle{ a_1 ,a_2, ..., a_{n-1}}\), będzie jednym z takich ciągów skoków skoczka. Łatwo zauważyć, że ciąg skoków \(\displaystyle{ a_1, n, a_2, ..., a_{n-1}}\) jest rozwiązaniem w tym przypadku.
Ad. 3:
Zapomnijmy o pierwszej minie. Z założenia idukcyjnego wynika, że istnieje ciąg skoków\(\displaystyle{ n, a_1, a_2, ..., a_{n-1}}\) omijający wszystkie pozostałe miny. Rozpatrzmy przypadek, w którym jesteśmy w polu z zapomnianą mina przed skokiem a_i(jeśli ominiemy zapomnianą minę teza jest oczywista). Łatwo widać, że ciąg skoków \(\displaystyle{ a_1, ..., a_i, n,..., a_{n-1}}\) spełnia warunki zadania.
Udowodnienie indukcji we wszystkich trzech przypadkach kończy dowód tezy zadania.
Zauważmy, że \(\displaystyle{ x = \left\lfloor (5+\sqrt{29})^{1120} \right\rfloor = (5+\sqrt{29})^{1120}+(5-\sqrt{29})^{1120}-1}\) po rozpisaniu z dwumianu Newtona dostajemy:
\(\displaystyle{ x = 2\left(\sum_{i=0}^{560} {1120 \choose 2i} 5^{1120-2i}\cdot 29^i \right)-1}\) z Chińskiego Twierdzenia o resztach wynika, że mamy znaleźć:
(To, że \(\displaystyle{ \sum_{i=0}^{k} {2k \choose 2i} = 2^{2k-1}}\) wynika od razu z rozpisania \(\displaystyle{ (1+1)^{2k}}\) oraz \(\displaystyle{ (1-1)^{2k}}\) z dwumianu Newtona)
Czyli:
\(\displaystyle{ \begin{cases} x \equiv 3\pmod{4}\\ x\equiv 1\pmod{5} \end{cases}}\) co nam od razu daje \(\displaystyle{ x \equiv 11 \pmod{20}}\)
No to może pochwale się swoim sposobem na zadanie 5:
Ukryta treść:
zauważyć, że \(\displaystyle{ x_n=(5+\sqrt{29})^n+(5-\sqrt{29})^n}\) jest wyrazem ogólnym ciągu rekurencyjnego: \(\displaystyle{ \left\{\begin{array}{l} x_0=2\\x_1=10\\x_{n+2}=10 x_{n+1}+4 x_{n} \end{array}}\)
exupery pisze:No to może pochwale się swoim sposobem na zadanie 5:
Ukryta treść:
zauważyć, że \(\displaystyle{ x_n=(5+\sqrt{29})^n+(5-\sqrt{29})^n}\) jest wyrazem ogólnym ciągu rekurencyjnego: \(\displaystyle{ \left\{\begin{array}{l} x_0=2\\x_1=10\\x_{n+2}=10 x_{n+1}+4 x_{n} \end{array}}\)
Jest tak, bo liczba \(\displaystyle{ (5+\sqrt{29})^{1120} + (5-\sqrt{29})^{1120}}\) jest całkowita, gdyż wszystkie pierwiastki się poredukują, a wobec tego, że liczba \(\displaystyle{ (5-\sqrt{29})^{1120} <1}\), to widzimy, że nasza równość faktycznie zachodzi.
Zauważmy, że z naszego układu rekurencji możemy obliczyć: \(\displaystyle{ a_{n} = 10a_{n-1} + 4a_{n-2}}\)
Obliczamy jeszcze w oparciu o układ wartość \(\displaystyle{ a_{2} = 54}\).
Zdefiniujmy kolejny (xd) ciąg
\(\displaystyle{ x_{n} = a_{n} \ (mod \ 5)}\)
Zauważmy, że ciąg ten będzie miał wzór \(\displaystyle{ x_{n} = 4x_{n-2}}\), oraz \(\displaystyle{ x_{1} = 0}\), \(\displaystyle{ x_{2} = 4}\) oraz będzie okresowy co \(\displaystyle{ 4}\) i łatwo wyliczamy, że \(\displaystyle{ x_{1120} = 1}\)
Analogicznie
\(\displaystyle{ y_{n} = a_{n} \ (mod \ 4)}\)
Robimy to samo, co wcześniej - ciąg jest równy 0 od 2 wyrazu, więc \(\displaystyle{ y_{1120} = 0}\).