Widzę, że nikt nie rozpoczął tematu, więc zacznę. Jak pierwszy dzień? Wrzuci ktoś zadanka?
LXVII (67) OM - finał
: 6 kwie 2016, o 18:13
autor: Vax
\(\displaystyle{ 1}\). Niech \(\displaystyle{ p}\) będzie ustaloną liczbą pierwszą. Znaleźć wszystkie nieujemne liczby całkowite \(\displaystyle{ n}\), dla których wielomian
może być zapisany w postaci iloczynu dwóch trójmianów kwadratowych o współczynnikach całkowitych.
\(\displaystyle{ 2}\). Okrąg \(\displaystyle{ \omega}\) o środku \(\displaystyle{ I}\) wpisany w czworokąt wypukły \(\displaystyle{ ABCD}\) jest styczny do boku \(\displaystyle{ AB}\) w punkcie \(\displaystyle{ M}\), a do boku \(\displaystyle{ CD}\) w punkcie \(\displaystyle{ N}\), przy czym \(\displaystyle{ \angle BAD + \angle ADC < 180^{\circ}}\). Na prostej \(\displaystyle{ MN}\) wybrano taki punkt \(\displaystyle{ K \neq M}\), że \(\displaystyle{ AK = AM}\). Dowieść, że prosta \(\displaystyle{ ID}\) przechodzi przez środek odcinka \(\displaystyle{ KN}\).
\(\displaystyle{ 3}\). Dane są dodatnie liczby całkowite \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Przez \(\displaystyle{ f(a, b)}\) oznaczamy liczbę takich \(\displaystyle{ a}\)-wyrazowych ciągów liczb całkowitych, że suma wartości bezwzględnych wyrazów ciągu nie przekracza \(\displaystyle{ b}\). Udowodnić, że \(\displaystyle{ f(a, b) = f(b, a)}\)
3:
Po prostu policzmy, ile to jest \(\displaystyle{ f(a,b)}\). Jest tylko jeden ciąg, którego suma wartości bezwzględnych wyrazów wynosi 0. Będziemy teraz sumować liczbę ciągów, których suma modułów wyrazów wynosi \(\displaystyle{ i \in [1; b]}\), oraz w ciągu tym jest \(\displaystyle{ j \in [0; a-1]}\) zer. Zauważmy, że wystarczy policzyć liczbę takich ciągów o wyrazach nieujemnych, a następnie wynik przemnożyć przez \(\displaystyle{ 2^t}\) gdzie \(\displaystyle{ t}\) to liczba dodatnich wyrazów ciągu (albo bierzemy jakiś wyraz dodatni albo ujemny, suma modułów wychodzi ta sama). Ustalając sumę wyrazów ciągu i liczbę elementów zerowych, zostaje nam jeszcze znaleźć liczbę rozwiązań równania \(\displaystyle{ c_1+c_2+...+c_{k} = n}\) gdzie \(\displaystyle{ c_i > 0}\) (u nas \(\displaystyle{ k = a-j}\), \(\displaystyle{ n = i}\)). To jest jednak dość znany problem i łatwo pokazać (np z funkcji tworzących), że wynik to \(\displaystyle{ {n-1 \choose k-1}}\). Wiedząc to wszystko dostajemy:
Ale widzimy, że tak naprawdę sumujemy j do \(\displaystyle{ \min(a, b)}\) (dla większych sumujemy zera), skąd już wynika \(\displaystyle{ f(a, b) = f(b, a)}\)
LXVII (67) OM - finał
: 7 kwie 2016, o 00:31
autor: Swistak
@Vax:
Ukryta treść:
Mniej sumowania wyjdzie, jeżeli zauważymy, że liczba rozwiązań nierówności \(\displaystyle{ c_1 + \ldots + c_k \le n}\) w liczbach całkowitych dodatnich, to liczba rozwiązań równania \(\displaystyle{ c_1 + \ldots c_{k+1} = n+1}\), wtedy eliminujemy całe liczenie, bo od razu wychodzi \(\displaystyle{ f(a, b) = \sum_{j=0}{a \choose j}{b \choose j}2^j}\)
LXVII (67) OM - finał
: 7 kwie 2016, o 19:19
autor: Pinionrzek
Dzisiejsze zadania. 4. Niech \(\displaystyle{ k, \ n}\) będą liczbami nieparzystymi większymi od \(\displaystyle{ 1}\). Wykazać, że jeśli istnieje taka liczba naturalna \(\displaystyle{ a}\), że \(\displaystyle{ k | 2^a+1}\) oraz \(\displaystyle{ n | 2^a-1}\), to wtedy nie istnieje taka liczba naturalna \(\displaystyle{ b}\), że \(\displaystyle{ n | 2^b+1}\) oraz \(\displaystyle{ k | 2^b-1}\). 5. Dane są dodatnie liczby rzeczywiste \(\displaystyle{ a<b}\). Dowieść, że istnieją takie dodatnie liczby całkowite \(\displaystyle{ p, \ q, \ r, \s}\), że \(\displaystyle{ a< \frac{p}{q} < \frac{r}{s} < b}\) oraz \(\displaystyle{ p^2+q^2=r^2+s^2}\). 6. Punkt \(\displaystyle{ I}\) jest środkiem okręgu wpisanego w \(\displaystyle{ \triangle ABC}\). Prosta \(\displaystyle{ AI}\) przecina prostą \(\displaystyle{ BC}\) w punkcie \(\displaystyle{ D}\) oraz okrąg opisany na \(\displaystyle{ \triangle ABC}\) w punkcie \(\displaystyle{ S \neq A}\). Punkt \(\displaystyle{ K}\) jest środkiem okręgu wpisanego w \(\displaystyle{ \triangle DSB}\), a punkt \(\displaystyle{ L}\)- w \(\displaystyle{ \triangle DSC}\). Punkt \(\displaystyle{ P}\) jest odbiciem symetrycznym punktu \(\displaystyle{ I}\) względem prostej \(\displaystyle{ KL}\). Wykazać, że kąt \(\displaystyle{ BPC}\) jest prosty.
LXVII (67) OM - finał
: 7 kwie 2016, o 20:30
autor: TomciO
Zadanie 4.
Ukryta treść:
Załóżmy, że istnieje taka liczba naturalna \(\displaystyle{ b}\). Niech \(\displaystyle{ x}\) będzie najmniejszą liczbą całkowitą dodatnią taką, że \(\displaystyle{ k | 2^x - 1}\). Wówczas \(\displaystyle{ x|2a}\), ale \(\displaystyle{ x}\) nie dzieli \(\displaystyle{ a}\). Co więcej, \(\displaystyle{ x|b}\). A zatem, potęga, w której liczba \(\displaystyle{ 2}\) dzieli \(\displaystyle{ b}\) jest większa niż ta, w której dzieli \(\displaystyle{ a}\). Argumentując w ten sam sposób, możemy uzasadnić przeciwną nierówność i stąd sprzeczność.
LXVII (67) OM - finał
: 7 kwie 2016, o 22:00
autor: Pinionrzek
6.
Ukryta treść:
Lemat:
Dany jest \(\displaystyle{ \triangle ABC}\). Niech \(\displaystyle{ P}\) będzie dowolnym punktem na odcinku \(\displaystyle{ BC}\). Oznaczmy przez \(\displaystyle{ D}\) punkt styczności okręgu wpisanego w \(\displaystyle{ \triangle ABC}\) z \(\displaystyle{ BC}\). Niech \(\displaystyle{ I_1, \ I_2}\) będą kolejno środkami okręgów wpisanych w \(\displaystyle{ \triangle APB, \ \triangle APC}\). Wtedy punkty \(\displaystyle{ I_1, \ I_2, \ P, \ D}\) leżą na jednym okręgu. Ponadto punkt symetryczny do \(\displaystyle{ D}\) względem \(\displaystyle{ I_1I_2}\) to przecięcie \(\displaystyle{ AP}\) z tym okręgiem.
Dowód: Ta cykliczność to zadanie- Zwardoń 2006, zadanie 6. Druga część jest prostym rachunkiem na kątach.
Przejdźmy do rozwiązania zadania.
Niech \(\displaystyle{ M}\) będzie środkiem \(\displaystyle{ BC}\). Oczywiście \(\displaystyle{ M}\) jest punktem styczności okręgu wpisanego w \(\displaystyle{ \triangle BSC}\) do \(\displaystyle{ BC}\). Zauważmy, że \(\displaystyle{ \angle KDL=\frac{\pi}{2}}\), a skoro na mocy naszego lematu punkty \(\displaystyle{ K, \ D, \ M, \ L}\) są współokręgowe, zatem \(\displaystyle{ \angle KML= \frac{\pi}{2}}\). Stosując teraz twierdzenie o trójliściu widzimy, że \(\displaystyle{ PK=IK=BK}\), czyli wystarczy pokazać, że \(\displaystyle{ KM}\) jest symetralną odcinka \(\displaystyle{ BP}\). Z naszego lematu wynika również, że jeżeli \(\displaystyle{ E=KL \cap AD}\), to punkty \(\displaystyle{ P, \ E, \ M}\) są współliniowe. Jeżeli teraz \(\displaystyle{ F}\) jest drugim przecięciem \(\displaystyle{ PM}\) z okręgiem opisanym na \(\displaystyle{ \triangle DKL}\), to \(\displaystyle{ F}\) jest punktem symetrycznym do \(\displaystyle{ D}\) względem \(\displaystyle{ KL}\), zatem \(\displaystyle{ \angle DMK= \angle FMK}\), czyli istotnie zachodzi \(\displaystyle{ PM=BM}\), co implikuje, że \(\displaystyle{ \triangle BPC}\) jest prostokątny.
3.
Ukryta treść:
Pokażemy, że \(\displaystyle{ f(a, b)=f(a, b-1)+f(a-1, b-1)+f(a-1, b)}\) i to rozwiąże zadanie, gdy skorzystamy z indukcji. Zauważmy, że wystarczy pokazać, że \(\displaystyle{ f(a-1, b-1)+f(a-1, b)}\) jest liczbą ciągów długości \(\displaystyle{ a}\), których moduły wyrazów sumują się dokładnie do \(\displaystyle{ b}\). Takie ciągi możemy podzielić na dwie kategorie. Pierwsza z nich, to takie, których moduły pierwszych \(\displaystyle{ a-1}\) wyrazów sumują się do liczby mniejszej niż \(\displaystyle{ b}\), a druga to takie, których moduły pierwszych \(\displaystyle{ a-1}\) wyrazów sumują się dokładnie do \(\displaystyle{ b}\). Zauważmy, że dla dowolnego ciągy z pierwszej kategorii możemy jednoznacznie co do modułu określić wyraz, którego moduł dodany do sumy poprzednich wyrazów tego ciągu spowoduje, że wynosić będzie \(\displaystyle{ b}\). W drugiej kategorii jedynym wyrazem, jaki możemy dodać jest \(\displaystyle{ 0}\). Musimy zliczyć więc podwójnie ciągi długości \(\displaystyle{ a-1}\), sumujące się do liczby mniejszej niż \(\displaystyle{ b}\) i raz te ciągi z drugiej kategorii. \(\displaystyle{ f(a-1, b-1)+f(a-1, b)}\) realizuje nam oczywiście oba te warunki.
LXVII (67) OM - finał
: 8 kwie 2016, o 12:01
autor: asdffdsa
5.
Ukryta treść:
BSO \(\displaystyle{ a = k/n, b = (k+1)/n}\).
Weźmy duże \(\displaystyle{ N}\). Ile jest ułamków o mianowniku \(\displaystyle{ n \leq m\leq N}\) w przedziale \(\displaystyle{ (a,b)}\)? jakieś \(\displaystyle{ m/n \pm 1}\).
Czyli wszystkich ułamków o takim mianowniku jest \(\displaystyle{ n/n+(n+1)/n + ... + (N/n) + O(N) = \frac{1}{2n} N^2 + O(N) \geq c_1N^2}\).
Dla takich ułamków suma kwadratów
licznika i mianownika jest ograniczona przez \(\displaystyle{ N^2+[(k+1)/n]^2N^2 = c_2N^2}\).
Teraz wystarczy taki fakcik (tw. Landau): niech \(\displaystyle{ S(n)}\) to liczba liczb \(\displaystyle{ \leq n}\) które dają się przedstawić w postaci sumy dwóch kwadratów. Wtedy \(\displaystyle{ S(n)/n \to 0.}\)
Dobieramy \(\displaystyle{ N}\) tak aby \(\displaystyle{ S(c_2N^2) < c_1N^2}\)
dalej zasada szufladkowa i teza.
Jaka jest firmówka?
LXVII (67) OM - finał
: 8 kwie 2016, o 22:50
autor: Ponewor
asdffdsa pisze:Jaka jest firmówka?
Warta sześć punktów w przeciwieństwie do Twojego rozwiązania.
LXVII (67) OM - finał
: 9 kwie 2016, o 10:11
autor: asdffdsa
Cóż za niegrzeczna odpowiedź.
Olimpiada uznaje twierdzenie Mihailescu z 2002(kosmicznie trudne), ale nie uznaje twierdzenia Landau z 1908 (dowód wymaga minimalnej wiedzy z analitycznej teorii liczb) - jestem zaskoczona. Rozumiem, jak ktoś nie podaje nazwiska, ani źródła...
A jakbym to sprowadziła do prime number theorem, albo \(\displaystyle{ \sum_{p \equiv 3 \pmod 4} \frac{1}{p} = \infty}\) to już ok?
LXVII (67) OM - finał
: 9 kwie 2016, o 12:19
autor: kaszubki
7 osób ma 36 punktów.
To jest jakieś nieporozumienie. Jeśli tyle dla Was znaczy, ludzie, takie zaangażowanie Jakuba Ochnika w olimpiadę, on poświęcił swoją edukację, pieniądze i wszystko inne, to Was nie powinno się szanować. Świstaki, Cieśle, komisje zadaniowe będą wam odbierały smak życia.
Tylko to się na tej olimpiadzie nadaje, powiedzieć Wam "niech drugi etap zdecyduje o IMO". A, szkoda gadać, szkoda strzępić ryja, naprawdę.
LXVII (67) OM - finał
: 9 kwie 2016, o 12:26
autor: JanRaj
To jaka ekipa na IMO?
LXVII (67) OM - finał
: 9 kwie 2016, o 12:27
autor: kaszubki
Najlepsza.
LXVII (67) OM - finał
: 9 kwie 2016, o 12:57
autor: michalkieza
Kaszubki, trochę nie masz racji. Drugi etap bardzo często decydował o IMO (zdarzało się, że 5-7 miejsce miało tyle samo punktów i patrzyło się na drugi etap), więc nie należy go lekceważyć i na nim też należy walczyć o jak najlepszy wynik.
Natomiast w 100% zgadzam się, że komisja zadaniowa dała w tym roku ciała na finale i wręcz zaledwie 7 osób z maksem to tylko efekt tego, że paru mocnym uczestnikom podwinęła się noga, bo swobodnie mogło być i 10 (całe szczęście, że przynajmniej drugi etap różnicował ludzi, bo dopiero wtedy byłby problem z ekipą na IMO). Zadania były zdecydowanie za proste, bardzo standardowe (no poza 5), a przede wszystkim nie było ani jednego zadania z kategorii trudne. Podobno tę rolę miało pełnić 6, ale ono jest naprawdę proste i sztampowe (jeden trójliść, a potem rachunki na kątach) - zrobiło je 25-30 osób (na co najmniej 5pkt). Zbliżoną trudność miało 5, resztę zadań robiło już dużo więcej ludzi (1 i 2 to prawie wszyscy).
LXVII (67) OM - finał
: 9 kwie 2016, o 13:03
autor: ElEski
Gratki dla wszystkich finalistów, bo bycie w finale to już zwycięstwo!
Ja się pochwalę swoim skrótowym rozwiazaniem zadania 5, które w dużej części przyczyniło się do mojego wysokiego wyniku punktowego w tym roku
Ukryta treść:
Lemat: istnieją \(\displaystyle{ p,q: \frac{p}{q} \in (a,b)}\) i \(\displaystyle{ p^{2}+q^{2}}\) jest kwadratem
Dowód: wystarczy pokazać, że \(\displaystyle{ \frac{m^{2}-n^{2}}{2mn}}\) przyjmuje gęste wartości. W tym celu weźmy duże m i zauważmy, że \(\displaystyle{ f(x)=\frac{m^{2}-x^{2}}{2mx}}\) jest duża w punkcie \(\displaystyle{ x=m^{1/3}}\), mała w punkcie \(\displaystyle{ x=m-m^{1/3}}\), a jej pochodna w przedziale \(\displaystyle{ (m^{1/3},m-m^{1/3})}\) jest właściwie 0. Stąd wniosek, że dla pewnego \(\displaystyle{ n}\) całkowitego \(\displaystyle{ f(n)}\) wpada w \(\displaystyle{ (a,b)}\)
Weźmy więc \(\displaystyle{ p,q: p^{2}+q^{2}=c^{2}.}\)
Udowodnię, że w przedziale \(\displaystyle{ ((1- \alpha )q,q)}\) istnieje wymierna \(\displaystyle{ w}\) t. że \(\displaystyle{ p^{2}+q^{2}-w^{2}}\) jest kwadratem liczby wymiernej i to będzie koniec. Wystarczy, by dla \(\displaystyle{ d}\) wymiernego \(\displaystyle{ d^{2}(c-w)=c+w}\), czyli by \(\displaystyle{ \frac{d^{2}-1}{d^{2}+1}c=w}\), a oczywiście takie d da się dobrać.
A geo wcale nie było takie łatwe, ja robiłem je 3.5h i nie udało mi się go pokonać mimo wielu sprytnych prób
LXVII (67) OM - finał
: 9 kwie 2016, o 13:15
autor: kaszubki
michalkieza pisze:Kaszubki, trochę nie masz racji. Drugi etap bardzo często decydował o IMO (zdarzało się, że 5-7 miejsce miało tyle samo punktów i patrzyło się na drugi etap), więc nie należy go lekceważyć i na nim też należy walczyć o jak najlepszy wynik.
Natomiast w 100% zgadzam się, że komisja zadaniowa dała w tym roku ciała na finale i wręcz zaledwie 7 osób z maksem to tylko efekt tego, że paru mocnym uczestnikom podwinęła się noga, bo swobodnie mogło być i 10 (całe szczęście, że przynajmniej drugi etap różnicował ludzi, bo dopiero wtedy byłby problem z ekipą na IMO).
Być może mam złe podejście do tematu, ale to nie jest przypadkiem tak, że ekipę na IMO jest bardzo łatwo wybrać? Można przecież losować, nie trzeba będzie nawet finału przeprowadzać. Zresztą plotka głosi, że zadania w tym roku to był jakiś żart nie tylko pod kątem trudności: zadanie 1 to "utrudniona" wersja A3 z putnama 2001, zadanie 3 to explicite B4 z putnama 2005.
Niewątpliwie jeśli ułożenie 6 zadań na finał jest problemem, to nie ma sensu podejmować tematu TST.
(żeby nie było że prowadzę niekonstruktywną krytykę, to chętnie się zaangnażuję w komisję zadaniową)