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.
To zadanie, to szczególny przypadek lematu Burnside'a: u nas \(\displaystyle{ G = S_{n}}\) (grupa permutacji zbioru n-elementowego), \(\displaystyle{ X = \{1,\ldots, n\}}\), orbita działania \(\displaystyle{ G}\) na \(\displaystyle{ X}\) jest tylko jedna (tzn dla każdych dwóch elementów \(\displaystyle{ X}\) znajdziemy permutację, która przerzuca jeden na drugi), więc lemat Burnside'a wypluwa nam dokładnie to co chcemy dostać.
Przy czym zdaję sobie sprawę, że chyba bardziej tego zadania już spałować nie można;)
Dlatego proszę się zbyt nie bulwersować - napisałem to jedynie na wypadek, gdyby kogoś interesowały uogólnienia.
bijekcję reprezentujmy przez graf. chcemy skonstruować bijekcję z co najmniej jednym punktem stałym i jeden taki punkt pokolorować na biało - to jest w oczywisty sposób lewa strona. mozemy tez najpierw wybrać na n sposobów biały punkt stały, a reszte ustawić dowolnie na (n-1)! sposobów skąd teza. analogicznie dochodzimy do uogólnienia:
dla dowolnego \(\displaystyle{ 1 \le l \le n}\) zachodzi: \(\displaystyle{ \sum_{k=l}^{n} {k \choose l} p_n(k) = {n \choose l}(n-l)!}\)
mozemy tez wziac wiele kolorów i otrzymać: \(\displaystyle{ \sum_{k=l}^{n} \frac{k!}{(k-l)!} p_n(k) = \frac{n!}{(n-l)!} \cdot (n-l)! = n!}\)
-- 30 września 2010, 22:17 --
ciekawe nr 6:
Ukryta treść:
bijekcja składa sie z cykli wiec wystarczy pokazać że dla dowolnego \(\displaystyle{ n}\) z ciągu 1,2,...,n[/latex] mozna otrzymac \(\displaystyle{ n,1,2,...,n-1}\). dwa przypadki:
1. n jest parzyste czyli n=2k. w pierwszej turze zamieniamy \(\displaystyle{ i}\) z \(\displaystyle{ 2k+i-i}\) dla i=1,2,...,k otrzymując \(\displaystyle{ 2k,2k-1,...,1}\). teraz zamieniamy \(\displaystyle{ i}\) z \(\displaystyle{ 2k-i}\) dla i=1,2,...,k-1 i mamy to co mieliśmy otrzymać
2. n=2k+1 - podobnie:
zamieniamy najpierw 1 z 2 a oraz \(\displaystyle{ i}\) z \(\displaystyle{ 2k+4-i}\) dla i=3,4,...,k+1 otrzymując \(\displaystyle{ 2,1,2k+1,2k,...3}\) teraz zamieniamy 2k+1 z 2 i tak jak poprzednio odwracamy kolejność 2k,2k-1,...,3
Rozważmy wielomian \(\displaystyle{ f(z)=(z-z_1)...(z-z_n)}\), gdzie \(\displaystyle{ z_1,...,z_n}\) są naszymi punktami na okręgu jednostkowym (robię na zespolonych). Nasz warunek jest równoważny \(\displaystyle{ |f(z)|\leq 2}\) dla \(\displaystyle{ |z|=1}\). Łatwo zauważyć, że \(\displaystyle{ |\sum_{w^n=1}f(w)|=2n}\), ale jednocześnie ta suma po lewej stronie jest mniejsza bądź równa \(\displaystyle{ \sum_{w^n=1}|f(w)|\leq 2n}\), czyli \(\displaystyle{ |f(w)|=2}\) dla \(\displaystyle{ w^n=1}\), bo wartość tego nie może być większa od długości średnicy. Łatwo więc zauważyć, że \(\displaystyle{ f(z)=z^n+1}\), czyli te punkty są pierwiastkami z \(\displaystyle{ -1}\), co kończy dowód. Przepraszam, jak są jakieś literówki, ale kolega mnie cały czas łaskotał jak to pisałem;p
Można to zauważyć po rozpisaniu tego wielomianu. Wtedy patrzymy oddzielnie na sumy dla każdej potęgi od 0 do n. Punkty możemy też przesunąć w taki sposób, że \(\displaystyle{ f(0)=1}\) (bo to po prostu ich iloczyn). Widać również, że suma przy wykładniku n da n, a ta z wykładnikami mniejszymi (oprócz 0) się wyzeruje i otrzymamy właśnie \(\displaystyle{ 2n}\). Mam nadzieję, że teraz jasne
7 ciekawe znalazło się wśród \(\displaystyle{ 101}\) nierozwiązanych.
7. ciekawe Czy tak można? Proszę o sprawdzenie.:
Gra z takich, że ktoś ma strategię wygrywającą. Udowodnię, że strategię wygrywającą ma Joasia. Załóżmy nie wprost, że strategię wygrywającą ma drugi z graczy czyli Onufry. W pierwszym ruchu Joasia wykreśla liczbę \(\displaystyle{ 1}\). Od tej pory Joanna zapomina, że była pierwszym graczem i realizuje wygrywającą strategię Onufrego. Wykreślona jedynka nie ma żadnego znaczenia, bo w późniejszych ruchach i tak nie można by jej już wykreślić, a i ona nie przeszkadza w żaden sposób w wykreślaniu innych liczb, bo nie ma dzielników poza sobą samą. A zatem Joasia grając strategią wygrywającą gracza drugiego wygra z Onufry. Otrzymana sprzeczność dowodzi, że to Joanna ma strategię wygrywającą.
Idea dobra, ale kiepsko opisana. W sytuacji, którą opisujesz, jak Joasia wykreśla jedynkę, to, o co chodzi z podkradaniem strategii Onufremu, skoro, to przecież on teraz wygrywa? To znaczy, ja oczywiście wiem, o co chodzi, ale mówię, że jakby czytał to ktoś, kto by nie wiedział, to by był zapewne skonfundowany .
Ja bym to opisał tak - zdefiniujmy grę G, która jest grą opisaną w treści zadania, ale nie ma w niej jedynki. Jeżeli gracz rozpoczynający grę G ma w niej strategię wygrywającą, to Joasia stosuje pierwszy ruch z tej strategii wygrywającej z gry G i gra właściwa staje się tym samym, co gra G, bo nie ma już w niej jedynki. Natomiast, jeżeli to drugi gracz ma strategię wygrywającą w grze G, to Joasia wykreśla jedynkę i sprowadza właściwą grę, do gry G, którą będzie rozpoczynać Onufry, czyli Joasia, będąc w niej drugim graczem, ma w niej strategię wygrywającą.
Zakładam, że \(\displaystyle{ n \ge 3}\). Zakładam, że istnieje taki podział i dowodzę przez sprzeczność. Niech ten podział będzie realizowany przez zbiory \(\displaystyle{ A _{1},...,A _{n}}\). Weźmy sobie liczby \(\displaystyle{ a,b}\), gdzie \(\displaystyle{ a}\) większe od \(\displaystyle{ b}\) i \(\displaystyle{ a,b \in A _{1}}\). Niech \(\displaystyle{ d=a-b}\). Jeśli istnieją takie \(\displaystyle{ i \neq j, i,j \neq 1}\), że mogę sobie wybrać ze zbiorów \(\displaystyle{ A _{i}, A _{j}}\) różniące się o \(\displaystyle{ d}\). To wtedy mamy sprzeczność, bo mogę raz wybrać mniejszą z nich, \(\displaystyle{ a}\) oraz dowolny zestaw liczb z pozostałych zbiorów (różnych od \(\displaystyle{ A _{1}, A _{i}, A _{j}}\)) i otrzymać jakąś tam liczbę w jednym ze zbiorów z \(\displaystyle{ A _{i}, A _{j}}\). Oraz zamieniając \(\displaystyle{ a}\) na \(\displaystyle{ b}\) i mniejszą na większą dostaniemy tą samą sumę, ale w drugim ze zbiorów. Zatem taka para \(\displaystyle{ \left( i,j\right)}\) nie może istnieć. Jeśli, więc wezmę jakąś liczbę \(\displaystyle{ c}\) ze zbioru \(\displaystyle{ A _{i}, i \neq 1}\) to liczba \(\displaystyle{ c+d}\) musi znajdować się w \(\displaystyle{ A _{1}}\). No to weźmy sobie jakieś takie \(\displaystyle{ x,y}\) spoza tego zbioru i same, żeby były z różnych zbiorów. Wtedy liczby \(\displaystyle{ x+d, y+d}\) leżą w \(\displaystyle{ A _{1}}\), a ich różnica to \(\displaystyle{ \left| x-y\right|}\). Powtarzajamy powyższe rozumowanie dla \(\displaystyle{ a=max\left( x,y\right), b=min\left( x,y\right), d=\left| x-y\right|}\), a liczbami spoza \(\displaystyle{ A _{1}}\) są tym razem \(\displaystyle{ x,y}\). Otrzymana sprzeczność kończy dowód
Zakładam, że \(\displaystyle{ n \ge 3}\). Zakładam, że istnieje taki podział i dowodzę przez sprzeczność. Niech ten podział będzie realizowany przez zbiory \(\displaystyle{ A _{1},...,A _{n}}\). Weźmy sobie liczby \(\displaystyle{ a,b}\), gdzie \(\displaystyle{ a}\) większe od \(\displaystyle{ b}\) i \(\displaystyle{ a,b \in A _{1}}\). Niech \(\displaystyle{ d=a-b}\). Jeśli istnieją takie \(\displaystyle{ i \neq j, i,j \neq 1}\), że mogę sobie wybrać ze zbiorów \(\displaystyle{ A _{i}, A _{j}}\) różniące się o \(\displaystyle{ d}\). To wtedy mamy sprzeczność, bo mogę raz wybrać mniejszą z nich, \(\displaystyle{ a}\) oraz dowolny zestaw liczb z pozostałych zbiorów (różnych od \(\displaystyle{ A _{1}, A _{i}, A _{j}}\)) i otrzymać jakąś tam liczbę w jednym ze zbiorów z \(\displaystyle{ A _{i}, A _{j}}\). Oraz zamieniając \(\displaystyle{ a}\) na \(\displaystyle{ b}\) i mniejszą na większą dostaniemy tą samą sumę, ale w drugim ze zbiorów. Zatem taka para \(\displaystyle{ \left( i,j \right)}\) nie może istnieć. Jeśli, więc wezmę jakąś liczbę \(\displaystyle{ c}\) ze zbioru \(\displaystyle{ A _{i}, i \neq 1}\) to liczba \(\displaystyle{ c+d}\) musi znajdować się w \(\displaystyle{ A _{1}}\). No to weźmy sobie jakieś takie \(\displaystyle{ x,y}\) spoza tego zbioru i same, żeby były z różnych zbiorów. Wtedy liczby \(\displaystyle{ x+d, y+d}\) leżą w \(\displaystyle{ A _{1}}\), a ich różnica to \(\displaystyle{ \left| x-y\right|}\). Powtarzajamy powyższe rozumowanie dla \(\displaystyle{ a=max\left( x,y\right), b=min\left( x,y\right), d=\left| x-y\right|}\), a liczbami spoza \(\displaystyle{ A _{1}}\) są tym razem \(\displaystyle{ x,y}\). Otrzymana sprzeczność kończy dowód
Załóżmy, że \(\displaystyle{ d}\) jest najmniejsze możliwe.
Nie działa część, gdy mówie, że \(\displaystyle{ c+d}\) należy do \(\displaystyle{ A _{1}}\), bo może należeć do tego zbioru co \(\displaystyle{ c}\). Zatem jeśli z dwóch zbiorów mogę wybrać takie \(\displaystyle{ x,y}\), żeby \(\displaystyle{ x+d, y+d}\) leżało w \(\displaystyle{ A _{1}}\) to jest koniec. Zatem w co najmniej \(\displaystyle{ n-2}\) zbiorach od pewnego miejsca mam od pewnego miejsca ciąg arytmetyczny o rozstępie \(\displaystyle{ d}\) i nie może być między elementami żadnego innego, bo przeczy to minimalności \(\displaystyle{ d}\). Powtarzając to rozumowanie dla wyróżnionego innego zbioru niż \(\displaystyle{ A _{1}}\) dostaję co najmniej \(\displaystyle{ n-1}\) zbiorów, które od pewnego miejsca zawierają ciąg arytmetyczny. Te ciągi są różne, więc \(\displaystyle{ d>n-1}\).
Zatem \(\displaystyle{ d=n}\), łatwo sprawdzić, że tak nie działa.
