jak już pewnie wiele osób wie, niedawno zakończyła się Trzecia Środkowoeuropejska Olimpiada Matematyczna. z tego miejsca wielkie gratulacje dla limesa123, który z Polaków wypadł najlepiej zdobywając złoty medal
w zawodach drużynowych Polska z prawie kompletem punktów zajęła I miejsce.
ale co tu się będę rozpisywał, oficjalne wyniki znajdziecie na stronie:
.
Zadania patrząc na wyniki w tym roku były znacznie trudniejsze niż w poprzednich edycjach. W tym miejscu warto wspomnieć, że zad. 4. z zawodów indywidualnych zrobił tylko zwycięzca (pewnie jakiś niedorobiony IMOer )
Rozwiązać w liczbach całkowitych dodatnich rownanie: \(\displaystyle{ 2^{x}+2009=3^{y}5^{z}}\)
Ukryta treść:
Rozpatrując dane równanie modulo \(\displaystyle{ 5}\) otrzymujemy, że \(\displaystyle{ x}\) musi być podzielny przez \(\displaystyle{ 4}\). Następnie modulo \(\displaystyle{ 10}\) dostajemy, że \(\displaystyle{ y}\) jest podzielne przez\(\displaystyle{ 4}\). Jeszcze szybkie sprawdzenie modulo \(\displaystyle{ 6}\) pokazuje, że \(\displaystyle{ z}\) jest parzyste. (Oczywiście na inne moduły też idzie).
Oznaczając \(\displaystyle{ x=4a, \ y=4b, \ z=2c}\) i podstawiając do naszego rownania otrzymamy: \(\displaystyle{ (2^{2a})^{2}+2009=(3^{2b}5^{c})^{2} \\ (3^{2b}5^{c}-2^{2a})(3^{2b}5^{c}+2^{2a})=2009}\)
Drugi czynnik jest dodatni, zatem pierwszy też. Jedyne dwa dzielniki liczby 2009 różniące się o liczbę będącą potęgą dwójki to \(\displaystyle{ 41}\) i \(\displaystyle{ 49}\), skąd mamy \(\displaystyle{ a=b=c=1}\), czyli ostatecznie otrzymujemy jedną trójkę rozwiązań: \(\displaystyle{ (x,y,z)=(4,4,2)}\). Bezpośrednio sprawdzamy, że otrzymane wartości spełniają wyjściowe rownanie.
Gratulacje dla polskiej drużyny - całej i każdego z osobna. Złośliwi mogą mówić, że zwycięstwo w zawodach drużynowych zawdzięczamy temu, że 3 zadania z 8 były autorstwa Polaków (każde innego), jednak to nie polskie zadania podzieliły czołówkę. I dobrze.
Osobiście najbardziej podobały mi się zadania I-4 oraz T-2. I to wcale nie dlatego że były trudne.
jak dotąd udało mi się zrobić z zawodów indywidualnych zad. 1, oraz z drużynowych 1,3,8. bardzo podoba mi się kombinatoryka (IMO dużo ciekawsza i trudniejsza niż w poprzednich latach), szkoda że póki co zrobiłem z niej tylko jedno zadanie
Oznaczmy sobie \(\displaystyle{ f(x) = x^{x-1} \mod k}\). Musimy znaleźć takie \(\displaystyle{ k}\), dla których \(\displaystyle{ f(1), \ldots, f(k)}\) są różne, czyli \(\displaystyle{ f}\) musi być bijekcją na zbiorze \(\displaystyle{ \{1,\ldots,k-1\}}\). Załóżmy od razu, że \(\displaystyle{ k > 3}\)- liczby 2 i 3 spełniają warunek zadania.
Przede wszystkim widać, że \(\displaystyle{ k}\) jest nieparzyste, inaczej byłoby \(\displaystyle{ f(1) = f(k-1) = 1}\). Niech \(\displaystyle{ p}\) będzie jakimś dzielnikiem pierwszym \(\displaystyle{ k}\) i niech \(\displaystyle{ S}\) będzie zbiorem tych reszt modulo \(\displaystyle{ k}\), które dają resztę \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ p}\). Zauważmy, że podniesienie do dowolnej potęgi i wzięcie reszty modulo \(\displaystyle{ k}\) zachowuje resztę \(\displaystyle{ 1}\) modulo \(\displaystyle{ p}\), a to znaczy, że \(\displaystyle{ f(S) = S}\), czyli \(\displaystyle{ f}\) jest bijekcją na \(\displaystyle{ S}\).
Jeśli teraz \(\displaystyle{ k \neq p}\), to wśród reszt modulo \(\displaystyle{ k}\) znajduje się \(\displaystyle{ 2p-1}\). Ale \(\displaystyle{ (2p-1)^{2p-2}}\) daje resztę \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ p}\), a zatem \(\displaystyle{ f(2p-1) \in S}\). A skoro \(\displaystyle{ f}\) była bijekcją na \(\displaystyle{ S}\), to istnieje też jakaś liczba \(\displaystyle{ s \in S}\) (czyli różna od \(\displaystyle{ 2p-1}\)), dla której \(\displaystyle{ f(s) = f(2p-1)}\). Sprzeczność.
Musi być zatem \(\displaystyle{ k = p}\), czyli k jest nieparzystą liczbą pierwszą. Niech \(\displaystyle{ u = f(\frac{k+1}{2}) = (\frac{k+1}{2})^{\frac{k-1}{2}} \mod k}\). Z małego twierdzenia Fermata \(\displaystyle{ u^2 = 1}\) modulo \(\displaystyle{ k}\). Ale dla \(\displaystyle{ k>3}\), \(\displaystyle{ u}\) nie jest równe \(\displaystyle{ 1}\) ani \(\displaystyle{ k-1}\), bo \(\displaystyle{ f}\) nie byłaby bijekcją. Możemy bez straty ogólności założyć, że \(\displaystyle{ u}\) jest nieparzyste - jeśli jest parzyste, zastępujemy je przez nieparzystą resztę \(\displaystyle{ k-u}\). W takim razie \(\displaystyle{ u-1}\) jest parzyste i \(\displaystyle{ u^{u-1} = 1}\) modulo \(\displaystyle{ k}\). Sprzeczność.
2 i 3 są zatem jedynymi możliwymi k.
zdecydowanie najprostsze z indywidualnych
załóżmy, że punkt P przecięcia się prostych AB z CD leży bliżej punktu A niż B
oznaczmy przez M środek AD, z tw. o odcinku łączącym środki boków trójkąta, mamy, że: \(\displaystyle{ MF= \frac{1}{2}AB= \frac{1}{2}CD=ME}\)
co za tym idzie trójkąt MEF jest równoramienny, oraz trójkąt PGH jest też równoramienny, bo ma boki równoległe do boków trójkąta MEF, z czego wyniki teza
wie ktoś ile punktów dostawało się, ze udowodnienie w drugim \(\displaystyle{ f(n) \le (n-1)^2}\) bez uzasadnienia, że równość zachodzi dla nieskończenie wielu wartości \(\displaystyle{ n}\)?
Przecięcie prostej EF z prostą AD (możemy bez zmniejszenia ogólności założyć, że to przecina się z prostą AD, a przecina się, bo gdyby EF było równoległe do AD, to ABCD byłby równoległobokiem) oznaczmy przez I. Rozpisujemy Menelaosy dla trójkątów BAD i ACD i prostej EF i otrzymujemy w końcu, że \(\displaystyle{ \frac{AG}{GB}=\frac{HC}{DH}}\), a wiemy, że \(\displaystyle{ AG+GB=HC+DH}\), więc \(\displaystyle{ AG=HC}\) i \(\displaystyle{ GB=DH}\). Rozpatrujemy teraz twierdzenie sinusów, dla trójkątów AGE i EHC. \(\displaystyle{ AG=HC \ \ AE=EC \ \ \sphericalangle AEG= \sphericalangle CEH \Rightarrow sin \sphericalangle AGE=sin \sphericalangle CHE \Rightarrow DHE=AGE}\) (trzeba pamiętać, że AB nie jest równoległe d DC, bo wtedy mogłoby być, ze suma tych dwóch kątów, to 180 stopni). c.b.d.u.
Równanie funkcyjne wygląda jakoś syfnie i mi nie idzie podstawowymi metodami .
siedziałem nad tym całą sobote, głównie dlatego, że odpowiedź jest (przynajmniej dla mnie) bardzo zaskakująca i sporo czasu minęło zanim obaliłem wszystkie moje hipotezy
T3:
oczywiste jest że \(\displaystyle{ g(n) \ge 2}\) bo nie możemy wymazać dwóch skrajnych liczb.
teraz udowadniam że dla \(\displaystyle{ n=2^k}\) można dojść do 2 liczb. wymazujemy najpierw wszystkie liczby nieparzyste. zostały tylko parzyste więc sobie możemy je podzielić przez 2 bo nic to nie zmienia, znowu wykreślamy nieparzyste, dzielimy przez 2 itd. jak ktoś lubi formalizmy może to indukcją udowodnić.
jeżeli n jest liczbą nieparzystą, to \(\displaystyle{ g(n) \ge 3}\). jeśli bowiem moglibyśmy dojść do dwóch liczb, to ostatnia wykreślona liczba byłaby równa \(\displaystyle{ \frac{n+0}{2}}\) a ta nie jest całkowita. \(\displaystyle{ n=2k+1}\). wybierzmy największą liczbę l taką że \(\displaystyle{ 2^l<2k+1}\)
mamy więc na tablicy liczby \(\displaystyle{ 0,1,2,...,2^l, 2^l+1,...,2k+1}\). najpierw wykreślamy liczby od \(\displaystyle{ 2^l+1}\) do \(\displaystyle{ 2k+1}\), a potem liczby od \(\displaystyle{ 0}\) do \(\displaystyle{ 2^l}\) załatwiamy tak jak w pierwszym przypadku.
został przypadek w którym n jest liczbą parzystą mającą dzielnik nieparzysty >1. przez wykreślanie liczb nieparzystych, dzielenie itd możemy to sprowadzić do przypadku z liczbą nieparzystą, więc możemy dojść do trzech liczb. ale czy możemy dojść do dwóch? nie. niech \(\displaystyle{ n=2^lk}\) gdzie k jest nieparzysta. załóżmy że udało nam się wykreślić wszystkie z wyjątkiem skrajnych liczb. odwróćmy teraz kolejność. zamiast z pełnej tablicy dochodzić do prawie pustej, będziemy z prawie pustej (czyli początkowo z dwoma skrajnymi liczbami) dochodzili do pełnej. nasz ruch polega na dopisaniu liczby będącej sumą liczb które już są na tablicy. oczywiste jest że istnieje wzajemna jednoznaczność między ciągiem ruchów "zwykłych" i "odwróconych". ponadto, w przeciwieństwie do ruchów "zwykłych", "odwrócone" możemy wykonywać w dowolnej kolejności (dopisanie liczby nie "blokuje" możliwości dopisania jakiejś innej liczby). wystarczy zauważyć że z tablicy \(\displaystyle{ 0, n}\) możemy dojść do tablicy \(\displaystyle{ 0,k,2k,...,n}\), na której już nic nie możemy dopisać. jeżeli k>1 mamy sprzeczność (przypominam że k jest nieparzyste).
podsumowując: \(\displaystyle{ g(2^n)=2}\) dla \(\displaystyle{ n \ge 1}\) \(\displaystyle{ g(2^n(2k+3))=3}\) dla \(\displaystyle{ n,k \ge 0}\)
-- 7 października 2009, 22:35 --
funkcja wcale syfna nie jest
to może jeszcze szkic nierówności wrzuce:
T1:
wstawiamy x=y=z do danego warunku i dostajemy poszlake: x=1 lub x=3. rozważmy więc nierówność \(\displaystyle{ (x-1)^2(x-3)^2 \ge 0}\). dodajemy trzy takie nierówności. jak się okazuje dostaniemy nierówność równoważną z tą, którą mamy udowodnić (wystarczy w sugestywny sposób przekształcić daną równość i dodać stronami). wszystkie ciągi złożone z jedynek i trójek spełniają daną równość, więc też i nierówność.
-- 8 października 2009, 10:20 --
rozwiązania z mathlinksa:
I-1:
I-2 (pierwsza część):
w sumie to o złoty medal nie było bardzo ciężko, bo 1. i 3. nie są bardzo trudne, ale wiadomo- co innego w domu a co innego na zawodach.
Oczywiscie aby takie k istnialo to wszystkie liczby postaci \(\displaystyle{ a^{a-1}}\) musza dawac rozne reszty z dzielenia przez k. Zauwazmy ze reszta kwadratowa modulo k podniesiona do dowolnej potegi, nadal jest reszta kwadratowa modulo k. A wiec jezeli a, nie jest liczba kwadratowa modulo k to \(\displaystyle{ a^{a-1}}\) tez nie jest, a wiec wszystkie reszty kwadratowe musza byc liczbami nieparzystymi. Ale dla k>3, a=4 jest reszta kwadratowa. KONIEC