Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
Zauważmy, że spośród naszych liczb jest tylko jedna postaci \(\displaystyle{ x2^y}\) dla \(\displaystyle{ x}\) nieparzystego. Teraz załóżmy, że \(\displaystyle{ t2^u=a_1\le \frac{2n}3}\). Bierzemy wtedy liczbę postaci \(\displaystyle{ 3t2^v}\) spośród tych naszych liczb i dostajemy, że \(\displaystyle{ NWW(t2^u,3t2^v)\le 2n}\).
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 19 lut 2013, o 22:30
autor: Burii
Ukryta treść:
Wskazówka: Powtórzyć dowód Twierdzenia Jacobiego dla trójkąta DEF i punktów \(\displaystyle{ I_{D}}\), \(\displaystyle{ I_{E}}\) i \(\displaystyle{ I_{F}}\) ( Trygonometryczny Ceva).
Następny problem
Ukryta treść:
Graf \(\displaystyle{ G}\) ma \(\displaystyle{ 2d+1}\) wierzchołków. Stopień każdego z nich wynosi \(\displaystyle{ d}\). Pokazać, że \(\displaystyle{ G}\) jest \(\displaystyle{ Hamiltonowski}\).
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 22 lut 2013, o 21:59
autor: Oildale
Ukryta treść:
Nash-Williams theorem.
Zadanie ode mnie podam jutro.
-- 23 lut 2013, o 07:46 --
Mamy tablice \(\displaystyle{ n \times n}\) i wpisujemy w nią liczby od \(\displaystyle{ 1}\) do \(\displaystyle{ n ^{2}}\). Wykaż, że istnieją dwa pola sąsiadujące krawędzią takie, że liczby na tych polach różnią się o co najmniej \(\displaystyle{ n}\).
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 31 mar 2013, o 03:59
autor: Ponewor
Ukryta treść:
Żeby zadanie miało sens musi być \(\displaystyle{ n \neq 1}\). W dalszej części rozwiązania przyjmę, że \(\displaystyle{ n \ge 2}\). Załóżmy nie wprost, że liczby na dowolnych dwóch polach o wspólnej krawędzi różnią się o mniej niż \(\displaystyle{ n}\). Popatrzmy na zbiory \(\displaystyle{ A_{i}=\left\{ 1, \ 2, \ \ldots, \ i \right\}}\) i \(\displaystyle{ B_{i}=\left\{ i+n, \ i+n+1, \ \ldots, \ \ n^{2}\right\}}\), przy czym z racji przyzwoitości niech \(\displaystyle{ i=1, \ 2, \ \ldots , \ n^{2}-n}\). Oczywiście nie istnieją dwa pola o wspólnej krawędzi z liczbami należącymi do obu tych zbiorów. Załóżmy, że w każdej kolumnie istnieją pola z liczbami i ze zbioru \(\displaystyle{ A_{i}}\) i z \(\displaystyle{ B_{i}}\). Wobec tego w każdej kolumnie musi być choć jedno pól nienależących do tamtych zbiorów (bo jakoś trzeba je rozdzielić), których jest: \(\displaystyle{ \left| \left(A_{i} \cup B_{i}\right)'\right|=n^{2}-\left(i+\left(n^{2}-\left(i+n\right)+1\right)\right)=n-1 <n}\) czyli sprzeczność, bo kolumn jest \(\displaystyle{ n}\). Zatem istnieje kolumna w której są pola z liczbami z tylko jednego zbioru. Analogicznie istnieje wiersz z polami z liczbami z tylko jednego zbioru. Z uwagi na fakt, że każdy wiersz i każda kolumna mają wspólne pole i \(\displaystyle{ A_{i} \cap B_{i} = \emptyset}\) to istnieją wiersz i kolumna z polami z liczbami z tylko jednego z tych zbiorów, który będziemy zwać wyróżnionym. Istnieją i takie konfiguracje w których jest to zbiór \(\displaystyle{ A_{i}}\) (wystarczy położyć \(\displaystyle{ i=n^{2}-n}\)), oraz takie w których jest to zbiór \(\displaystyle{ C_{i}}\) (wystarczy położyć \(\displaystyle{ i=1}\)). Teraz już łatwo, bo skoro istnieją takie naturalne \(\displaystyle{ i}\) dla których wyróżniony jest zbiór \(\displaystyle{ A_{i}}\), to jak to bywa wśród liczb naturalnych istnieje najmniejsze \(\displaystyle{ i}\), dla którego \(\displaystyle{ A_{i}}\) jest wyróżniony. Nie jest to oczywiście \(\displaystyle{ i=1}\). Skoro tak, to \(\displaystyle{ A_{i-1}}\) nie jest zbiorem wyróżnionym, ale dla każdego \(\displaystyle{ i}\) musi istnieć zbiór wyróżniony, więc \(\displaystyle{ B_{i-1}}\) jest zbiorem wyróżnionym. Kolumna w której są pola z liczbami jedynie ze zbioru \(\displaystyle{ A_{i}}\) tnie wiersz z polami w których są liczby jedynie ze zbioru \(\displaystyle{ B_{i-1}}\). Istnieje więc pole z liczbą należącą do \(\displaystyle{ A_{i}}\) i jednocześnie \(\displaystyle{ B_{i-1}}\), ale \(\displaystyle{ A_{i} \cap B_{i-1} = \emptyset}\), bo najmniejsza liczba ze zbioru \(\displaystyle{ B_{i-1}}\) równa \(\displaystyle{ n+i-1}\) jest dla \(\displaystyle{ n \ge 2}\) większa od największej liczby ze zbioru \(\displaystyle{ A_{i}}\) równej \(\displaystyle{ i}\). Otrzymana sprzeczność dowodzi tezy.
Nowe:
Z okazji Wielkanocy Ponewor w ramach życzeń łatwe zadanie pisze:Mamy \(\displaystyle{ 52}\) karty tradycyjnie o \(\displaystyle{ 13}\) wartościach. Rozłożono jest na \(\displaystyle{ 13}\) równych kupek. Czy dla każdego rozłożenia możemy z każdej kupki wziąć po jednej karcie, tak by mieć w ręku \(\displaystyle{ 13}\) kart o różnych wartościach?
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 31 mar 2013, o 20:49
autor: porfirion
Proponuje takie coś:
Intuicyjnie dzielenie na kupki wygląda w ten sposób, że tasujemy całą talię i wykładamy po cztery kolenje. Ale można podzielić na kupki też w inny sposób. Bierzemy z całej tali tylko kiery, tasujemy je i wykładamy: pierwszy kier do pierwszej kupki, drugi kier do drugiej itd. To samo robimy z pikami, treflami i karami. Dostajemy 13 kupek w których w każdej są cztery karty różnych kolorów. Kolory jednka w zadaniu nas nie interesują, a między wynikami dwóch podziałów jest bijekcja (wynikiem podziału jest oczywiście rodzina 13 zbiorów wartości kart). Istnienie owej bijekcji kończy dowód zadania.
Nowe: Było kiedyś na forum, ale wątpie w to, że je pamiętacie (a jest super!):
Wykaż, że z odcinków długości \(\displaystyle{ a,b,c}\) można zbudować trójkąt wtedy i tylko wtedy, gdy dla dowolnych liczb \(\displaystyle{ p}\) i \(\displaystyle{ q}\) spełniających warunek \(\displaystyle{ p+q=1}\) zachodzi nierówność \(\displaystyle{ p a^{2}+q b^{2}>pq c^{2}}\).
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 31 mar 2013, o 21:49
autor: Zordon
porfirion pisze:Proponuje takie coś:
Intuicyjnie dzielenie na kupki wygląda w ten sposób, że tasujemy całą talię i wykładamy po cztery kolenje. Ale można podzielić na kupki też w inny sposób. Bierzemy z całej tali tylko kiery, tasujemy je i wykładamy: pierwszy kier do pierwszej kupki, drugi kier do drugiej itd. To samo robimy z pikami, treflami i karami. Dostajemy 13 kupek w których w każdej są cztery karty różnych kolorów. Kolory jednka w zadaniu nas nie interesują, a między wynikami dwóch podziałów jest bijekcja (wynikiem podziału jest oczywiście rodzina 13 zbiorów wartości kart). Istnienie owej bijekcji kończy dowód zadania.
Nie wygląda to jak rozwiązanie, a nawet jeśli nim jest to bardzo kiepsko opisane. Uzupełnię to może moim komentarzem. Rozważmy graf dwudzielny, z lewej strony kupki z prawej wartości kart. Tw. Halla zastosowane do tego grafu (który jest 4-regularny jeśli liczyć krawędzie wielokrotnie) daje nam rozwiązanie.
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 31 mar 2013, o 23:01
autor: Ponewor
Zordon pisze: Nie wygląda to jak rozwiązanie, a nawet jeśli nim jest to bardzo kiepsko opisane. Uzupełnię to może moim komentarzem. Rozważmy graf dwudzielny, z lewej strony kupki z prawej wartości kart. Tw. Halla zastosowane do tego grafu (który jest 4-regularny jeśli liczyć krawędzie wielokrotnie) daje nam rozwiązanie.
Wstrzeliłeś się we wzorcówkę. + miałem właśnie pisać to samo o poprzednim rozwiązaniu.
Aktualne zadanie:
porfirion pisze:Było kiedyś na forum, ale wątpie w to, że je pamiętacie (a jest super!):
Wykaż, że z odcinków długości \(\displaystyle{ a,b,c}\) można zbudować trójkąt wtedy i tylko wtedy, gdy dla dowolnych liczb \(\displaystyle{ p}\) i \(\displaystyle{ q}\) spełniających warunek \(\displaystyle{ p+q=1}\) zachodzi nierówność \(\displaystyle{ p a^{2}+q b^{2}>pq c^{2}}\).
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 31 mar 2013, o 23:35
autor: KPR
Ukryta treść:
Jeżeli \(\displaystyle{ a,b,c}\) są bokami trójkąta, to \(\displaystyle{ pa^2+qb^2=(pa^2+qb^2)(p+q)=pq(a^2+b^2)+p^2a^2+q^2b^2\ge pq(a^2+b^2+2ab)=pq(a+b)^2>pqc^2}\) dla \(\displaystyle{ p,q}\) dodatnich oraz \(\displaystyle{ pa^2+qb^2=(pa^2+qb^2)(p+q)=pq(a^2+b^2)+p^2a^2+q^2b^2=\ge pq(a^2+b^2-2ab)=pq(a-b)^2>pqc^2}\), jeśli jedno z \(\displaystyle{ p,q}\) jest ujemne. Wszystkie nierówności wyżej zastosowane to \(\displaystyle{ AM-GM}\) i nierówność trójkąta (w postaci \(\displaystyle{ (a-b)^2<c^2<(a+b)^2}\)).
Aby pokazać w drugą stronę, załóżmy, że któraś z tych nierówności trójkąta nie zachodzi. Wtedy dobieramy sobie \(\displaystyle{ p}\) i \(\displaystyle{ q}\), żeby stosunek był odpowiedni, żeby w \(\displaystyle{ AM-GM}\) zachodziła równość w tym łańcuchu nierówności powyżej, w którym się sypie i wtedy wszystko się sypie (tu są jakieś szczegóły jak to, że dla \(\displaystyle{ a=b}\) nie da się znaleźć odpowiednich \(\displaystyle{ p,q}\) z jednym ujemnym, ale ten przypadek, kiedy jest taka potrzeba, nie zajdzie).
Nowe:
Mamy sobie taką grę: na początku na tablicy są napisane w rzędzie liczby \(\displaystyle{ 1,2,\dots,20}\). Wolfgang i Ludwig na przemian stawiają znaki \(\displaystyle{ +}\) lub \(\displaystyle{ -}\) przed dowolnie wybranymi liczbami, przed którymi nie ma jeszcze żadnego znaku. Po dwudziestu ruchach Ludwig wygrywa moduł wyliczonej w ten sposób sumy. Ile wygra przy optymalnej strategii obu graczy (oczywiście obaj chcą mieć jak najwięcej pieniędzy)?-- 3 kwi 2013, o 23:16 --Oczywiście Wolfgang zaczyna.
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 6 kwie 2013, o 09:16
autor: Oildale
Najpierw pokażemy strategie dla Ludwiga na osiągnięcie co najmniej \(\displaystyle{ 30}\). Wystarczy, że połączyć w pary \(\displaystyle{ \left[ 1,2\right], \left[ 3,4\right] ... \left[ 19,20\right]}\) i w momencie gdy Wolfgang wybiera, którąś liczbę to Ludwig dobiera drugą z tej pary, ale z przeciwnym znakiem (za wyjątkiem ostatniej pary gdzie dobiera liczbę z tym samym znakiem). Widać, że ta strategia zapewnia nam otrzymanie co najmniej \(\displaystyle{ 30}\) monet. pokażmy teraz strategie dla Wolfganga na to aby wynik był co najwyżej \(\displaystyle{ 30}\). Jego strategia polega na tym, że wybiera największą dostępną liczbę ze znakiem przeciwnym do znaku sumy częściowej (gdy suma wynosi \(\displaystyle{ 0}\) mogę wybrać dowolny znak). No dobra to teraz pokażemy dlaczego ta strategia działa. Załóżmy, że ostatnia zmiana znaku sumy częściowej wystąpiła w \(\displaystyle{ i}\) tej rundzie, \(\displaystyle{ 1 \le i \le 10}\). Zauważmy, że do tej rundy zostały już na pewno zużyte liczby \(\displaystyle{ 20, 19, ..., 22-i}\). Zatem po \(\displaystyle{ i}\) tej rundzie moduł sumy częściowej będzie wynosić co najwyżej \(\displaystyle{ 41-2i}\). Zauważmy jeszcze, że w każdej następnej rundzie moduł zmniejszy się o co najmniej \(\displaystyle{ 1}\). Zatem na koniec gry będzie wynosić co najwyżej \(\displaystyle{ (41-2i) - (10-i) = 31 - i \le 30}\). Zatem ta liczba to \(\displaystyle{ 30}\).-- 6 kwi 2013, o 09:21 --Zadanie ode mnie:
Mamy sobie tr. \(\displaystyle{ ABC}\), \(\displaystyle{ M}\) to środek \(\displaystyle{ AB}\). \(\displaystyle{ D,E,F}\) to punkty styczności okręgu wpisanego (wiadomo jak). Niech \(\displaystyle{ P}\) będzie przecięciem \(\displaystyle{ CM}\) i \(\displaystyle{ DE}\). Wykaż, że \(\displaystyle{ PF}\) jest prostopadłe do \(\displaystyle{ AB}\).
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 6 kwie 2013, o 13:58
autor: jakub_jabulko
nie wiem, czy z konfiguracją wszystko ok, więc proszę o sprawdzenie pod tym kątem.
Ukryta treść:
istnieje dokładnie jeden punkt X należący do ED, taki że XF jest prostopadłe do AB. Wykażemy, że X=P, czyli, że CX jest środkową w trójkącie ABC. Oczywiście X, I, F leżą na jednej prostej (I=środek okręgu wpisanego).
Poprowadźmy prostą równoległą do AB przechodzącą przez X, nazwijmy ją k. Niech k tnie odcinki BC i AC odpowiednio w punktach odpowiednio M i N. Trzeba teraz wykazać, że MX=NX, bo równoległość.
Mamy tam fajne kąty proste (z założeń i ze styczności okręgu w punktach D i E). Mamy więc okrąg opisany na czworokątach IMXD i INXE. Stąd kąt DIM jest równy kątowi NIE. Stąd trójkąty prostokątne DIM i NIE są podobne, a nawet przystające, bo DI = EI. Stąd mamy NI = MI, a więc MX=NX, c.b.d.u.
Zaraz wrzucę jakieś fajne.
-- 6 kwi 2013, o 15:05 --
ok, już mam.
Niech \(\displaystyle{ S _{n}}\) oznacza zbiór kół leżących na jednej płaszczyźnie o parami rozłącznych wnętrzach, z których każde jest styczne dokładnie do n innych.
a) udowodnić, że dla \(\displaystyle{ n \ge 6}\) , \(\displaystyle{ S _{n}}\) nie może być skończony
b) podać konstrukcję przykładowego zbioru skończonego \(\displaystyle{ S _{n}}\) dla każdego \(\displaystyle{ n \le 4}\)
c) rozstrzygnąć, czy \(\displaystyle{ S _{5}}\) może być skończony
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 6 kwie 2013, o 15:10
autor: Oildale
Może drobna uwaga do powyższego rozwiązania (?):
Ukryta treść:
Nie działa!!! (dlaczego DIM = NIM ?)
-- 6 kwi 2013, o 15:22 --
Przy okazji rozwiązania twojego zadania.
a) Nie wprost + zasada ekstremum (biorę najmniejszy okrąg)
b) Rzut stereograficzny sfery stycznej do krawędzi sześcianu
c) Rzut stereograficzny sfery stycznej do krawędzi dwunastościanu foremnego-- 6 kwi 2013, o 15:23 --Wraca moje zadanie.
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 6 kwie 2013, o 15:54
autor: jakub_jabulko
Nie wiem, o co ci chodzi, chyba masz literówkę. Jeśli chodzi ci o przystawanie trójkątów DIM i NIE, to wydaje mi się, że jest jasne: kąt DIM = kąt MXD = kąt EXN = kąt EIN. Wspomniane trójkąty są przy okazji prostokątne, oraz mają równe odpowiednie boki.
Te równości wynikają z tego, że czworokąty DMXI i ENXI są wpisane w okrąg. Jest tak, gdyż kąty CDI, MXF, NXF i AEI są proste.
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 6 kwie 2013, o 16:01
autor: Oildale
Tak myślałem. Zauważ, że zakładasz to, że \(\displaystyle{ D, X, E}\) leżą na jednej prostej, a to jest właśnie nasza teza ...
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 6 kwie 2013, o 16:55
autor: jakub_jabulko
Nie, punkt X przecież oznaczyłem sam. To, że istnieje, jest oczywiste. Ja dowodziłem, że X=P. Nie wiem więc, o co chodzi... Nie twierdzę, że nie mam tam błędu, ale nie potrafię zrozumieć twojej argumentacji.
[Rozgrzewka OM][MIX] Łańcuszek olimpijski
: 6 kwie 2013, o 17:00
autor: Oildale
jakub_jabulko pisze:nie wiem, czy z konfiguracją wszystko ok, więc proszę o sprawdzenie pod tym kątem.
Ukryta treść:
istnieje dokładnie jeden punkt X należący do AD, taki że XF jest prostopadłe do AB. Wykażemy, że X=P, czyli, że CX jest środkową w trójkącie ABC. Oczywiście X, I, F leżą na jednej prostej (I=środek okręgu wpisanego).
Poprowadźmy prostą równoległą do AB przechodzącą przez X, nazwijmy ją k. Niech k tnie odcinki BC i AC odpowiednio w punktach odpowiednio M i N. Trzeba teraz wykazać, że MX=NX, bo równoległość.
Mamy tam fajne kąty proste (z założeń i ze styczności okręgu w punktach D i E). Mamy więc okrąg opisany na czworokątach IMXD i INXE. Stąd kąt DIM jest równy kątowi NIE. Stąd trójkąty prostokątne DIM i NIE są podobne, a nawet przystające, bo DI = EI. Stąd mamy NI = MI, a więc MX=NX, c.b.d.u.
X definiujesz jako przeciecie prostej prostopadlej do AB przechodzacej przez F i AD (tu chyba jest jakis blad w definiowaniu tego X) Napisz jak chcesz definiowac X.