Wczoraj zakończył się obóz organizowany przez KGOM, z założeń trening przed IMO (które jest już za niecałe 3 tygodnie)
Zadania były w moim odczuciu ciekawe, więc wrzucę, miłej kminy:
Każdego dnia po trzy zadania, uszeregowane trudnością (z grubsza jak na IMO)
Dzień pierwszy
1.
Niech \(\displaystyle{ S}\) będzie zbiorem n-elementowym, a \(\displaystyle{ P(S)}\) niech oznacza rodzinę podzbiorów \(\displaystyle{ S}\). Funkcja \(\displaystyle{ f:P(S) \rightarrow R}\) spełnia warunek \(\displaystyle{ f(X \cap Y) = min(f(X),f(Y))}\) dla dowolnych \(\displaystyle{ X,Y \subset S}\). Wyznaczyć największą możliwą moc zbioru wartości funkcji \(\displaystyle{ f}\).
2.
Wyznaczyć wszystkie skończone zbiory \(\displaystyle{ S}\) punktów na płaszczyźnie, spełniające następujące warunki:
(i) nie wszystkie punkty ze zbioru \(\displaystyle{ S}\) leżą na jednej prostej
(ii) dla dowolnych różnych punktów \(\displaystyle{ A,B,C \in S}\) istnieje taki punkt \(\displaystyle{ D \in S}\), że \(\displaystyle{ A,B,C,D}\) są w pewnej kolejności wierzchołkami równoległoboku.
3.
Dany jest ciąg (\(\displaystyle{ a_n}\)) spełniający warunki \(\displaystyle{ a_0 = 4}\) \(\displaystyle{ a_{n+1} = a_n^2 - 2}\).
Udowodnić, że \(\displaystyle{ a_{n+1} > 2 \sqrt{3} a_n...a_1a_0}\).
Dzień drugi
4.
Wyznaczyć wszystkie liczby naturalne n takie, dla których istnieją \(\displaystyle{ a,b \in Q-Z}\), że \(\displaystyle{ a+b \in Z}\) oraz \(\displaystyle{ a^n + b^n \in Z}\)
5.
Dany jest nierównoramienny ostrokątny trójkąt ABC. D,E - spodki wysokości opuszczonych odpowiednio z B i C, H-ortocentrum. Prosta zawierająca dwusieczną kąta EHB przecina boki AB i AC odpowiednio w punktach P,Q. N - środek odcinka BC. R - przecięcie dwusiecznej kąta BAC z prostą HN. Udowodnić, że A,P,R,Q leżą na jednym okręgu.
6.
Dana jest grupa \(\displaystyle{ n}\) osób, wśród których niektóre się znają. Niech \(\displaystyle{ k \ge 2}\) będzie ustaloną liczbą naturalną. Wiadomo, że wśród dowolnych \(\displaystyle{ k}\) osób pewne dwie się znają. Udowodnić, że można posadzić wszystkich przy nie więcej niż \(\displaystyle{ k-1}\) okrągłych stolikach tak, aby każdy siedział obok swoich znajomych. Uwaga: przy stoliku może też siedzieć jedna lub dwie osoby.
Dzień trzeci
7.
Dane są liczby całkowite \(\displaystyle{ a,b,x,y}\) takie, że \(\displaystyle{ a^2 + b^2 | ax+by}\). Udowodnić, że liczby \(\displaystyle{ a^2 + b^2}\) i \(\displaystyle{ x^2+y^2}\) nie są względnie pierwsze.
8.
W trójkącie ostrokątnym ABC obrano taki punkt P, że \(\displaystyle{ \sphericalangle PCA = \sphericalangle PAB}\) oraz \(\displaystyle{ \sphericalangle PCB = \sphericalangle PBA}\). Punkt Q leży na prostej AB i spełnia warunek QP=QC. O - środek okręgu opisanego na ABC. Wykazać, że \(\displaystyle{ \sphericalangle CQP = 2 \sphericalangle OQA}\).
9.
Wyznaczyć wszystkie liczby naturalne n, dla których istnieją dwa różne niemalejące ciągi liczb całkowitych (można rozwiązać trudniejszą wersję - rzeczywistych) \(\displaystyle{ a_1, a_2, ..., a_n}\) i \(\displaystyle{ b_1, b_2, ..., b_n}\) dla których ciąg \(\displaystyle{ a_1+a_2,a_1+a_3,...a_1+a_n, a_2+a_3,... a_2+a_n,...a_{n-1}+a_{n}}\) jest permutacją ciągu \(\displaystyle{ b_1+b_2,b_1+b_3,...b_1+b_n, b_2+b_3,... b_2+b_n,...b_{n-1}+b_{n}}\).
Dzień czwarty, próbne IMO
IMO1.
Dany jest czworokąt wypukły ABCD. Na boku AB wybrano dwa różne punkty P,Q takie, że AP=BQ. Okręgi opisane na trójkątach APD i QBD przecinają się w punktach D i K, a okręgi opisane na trójkątach APC i QBC przecinają się w punktach C i L. Udowodnić, że C,D,K,L leżą na jednym okręgu.
IMO2.
Wyznacz wszystkie funkcje \(\displaystyle{ f:Z \rightarrow Z}\) spełniające dla dowolnych \(\displaystyle{ m,n \in Z}\)
równość
f(m-n+f(n)) = f(m) + f(n).
IMO3.
Dana jest liczba pierwsza \(\displaystyle{ p>3}\). Udowodnij, że liczba \(\displaystyle{ x^{p-1} + x^{p-2} + ... + x + 2}\) nie jest kwadratem liczby całkowitej dla żadnego \(\displaystyle{ x \in Z}\).
Dzień piąty, próbne IMO
IMO4.
W pola tablicy nxn wpisano liczby rzeczywiste. Niech \(\displaystyle{ a_{ij}}\) oznacza liczbę stojącą na przecięciu i-tego wiersza i j-tej kolumny. Udowodnić, że \(\displaystyle{ n \left( \sum_{i=1}^{n} \left( \sum_{j=1}^{n}a_{ij} \right)^2 + \sum_{j=1}^{n} \left( \sum_{i=1}^{n}a_{ij} \right)^2 \right) \le \left( \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} \right) ^2 + n^2 \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} ^2}\)
IMO5.
W turnieju ping-ponga każdy gracz rozegrał z każdym innym dokładnie jeden mecz, nie było remisów. Czwórkę graczy nazwiemy nierozstrzygniętą, gdy w meczach pomiędzy tą czwórką pewnych trzech graczy wygrało po dwa mecze. Niech \(\displaystyle{ w_i}\) oznacza liczbę wygranych i-tego gracza, a \(\displaystyle{ l_i}\) liczbę przegranych i-tego gracza. Przypuśćmy, że żadna czwórka nie jest nierozstrzygnięta. Udowodnić, że \(\displaystyle{ \sum_{i}^{} (w_i - l_i)^3 \ge 0}\).
IMO6.
Dany jest okrąg o środku I i dwa punkty A,B na tym okręgu. Styczne w punktach A i B przecinają się w punkcie X. Punkt C leży na łuku AB zawartym w trójkącie ABX, przy czym AC \(\displaystyle{ \neq}\) BC. Prosta AC przecina BX w punkcie D, a prosta BC przecina AX w punkcie E. Wykazać, że środki okręgów opisanych na trójkątach AEC, DBC i CXI leżą na jednej prostej.
Powodzenia.
[MIX] Obóz przygotowujący do IMO
: 27 cze 2011, o 15:39
autor: Burii
5
Ukryta treść:
Łatwo pokazać iż dwusieczna \(\displaystyle{ l \ \sphericalangle BAC}\) jest prostopadła do \(\displaystyle{ PQ}\)( przeliczenia na kątach.
Wybierzmy na prostej l taki punkt \(\displaystyle{ R'}\)że na czworokącie \(\displaystyle{ APQR'}\)można opisać okrąg. Wówczas \(\displaystyle{ PR'||HC i QR'||BH}\). Niech \(\displaystyle{ PR'}\) przecina \(\displaystyle{ BH}\)w \(\displaystyle{ X}\) a\(\displaystyle{ QR'}\) przecina \(\displaystyle{ CH}\) w\(\displaystyle{ Y}\). Łatwo zauważyć iz czworokąt \(\displaystyle{ HXYR'}\) to równoległobok oraz ze zachodzą równości \(\displaystyle{ PX=XH i HY=YQ}\). Mamy teraz; \(\displaystyle{ \frac{HX}{BX}= \frac{PX}{BX}= \frac{QX}{XC}= \frac{HX}{YC}}\) ( trójkąty \(\displaystyle{ QYC}\) i \(\displaystyle{ PXB}\) są podobne) stąd \(\displaystyle{ XY||BC}\) a zatem prosta \(\displaystyle{ HR'}\) jako prosta przechodząca przez środek odcinka \(\displaystyle{ XY}\) przecina \(\displaystyle{ BC}\) w \(\displaystyle{ N}\). Stąd teza.
[MIX] Obóz przygotowujący do IMO
: 27 cze 2011, o 15:46
autor: timon92
fajne, szkic mojego:
Ukryta treść:
wpierw można pokazać, że jak odbije się H względem N do otrzymamy punkt X leżący na okręgu opisanym i to taki, że BX jest średnicą no i można też pokazać, że BR jest dwusieczną kąta XBH
jeśli AD jest wysokością, O środkiem okręgu opisanego, S rzutem R na BC to Talesy, dwusieczne i podobieństwa dają nam \(\displaystyle{ \frac{DS}{SC} = \frac{HR}{RX} = \frac{HB}{BX} = \frac{NO}{OX} = \frac{NO}{OC} = \frac{DH}{HC}}\) więc S=Q, tzn \(\displaystyle{ \angle RQB = \frac \pi 2}\) i analogicznie robimy z punktem P
[MIX] Obóz przygotowujący do IMO
: 27 cze 2011, o 15:48
autor: Burii
8
Ukryta treść:
Odbijmy symetrycznie punkt\(\displaystyle{ P}\) względem prostej\(\displaystyle{ BC}\). Otzrymamy punkt \(\displaystyle{ X}\). Z równości kątów danych w zadaniu łatwo pokazać iż \(\displaystyle{ X}\) nalezy do okręgu opisanego na \(\displaystyle{ ABC}\). stąd skoro \(\displaystyle{ BPC}\) i \(\displaystyle{ BXC}\) są są symetryczne to \(\displaystyle{ QA=QP=QX}\). Zatem punkty \(\displaystyle{ A, P , X}\) leżą na okręgu o promieniu \(\displaystyle{ QA}\) i środku w \(\displaystyle{ Q}\). Osią potęgową tego okręgu i okręgu opisanego na \(\displaystyle{ ABC}\) jest prosta \(\displaystyle{ AX}\) zatez \(\displaystyle{ QO}\) i \(\displaystyle{ AX}\) są do siebie prostopadłe czyli \(\displaystyle{ OQ}\)jest wysokością w trójkącie równoramiennym \(\displaystyle{ AQX}\) stąd; \(\displaystyle{ 2 \sphericalangle OQB=2( \frac{1}{2} \sphericalangle AQX - \sphericalangle XQB) = \sphericalangle AQX- 2 \sphericalangle XQB= \sphericalangle APQ}\).
-- 27 cze 2011, o 15:50 --
2
Ukryta treść:
Wybieramy trójkąt ABC o maksymalnym polu. Z warunków zadania i mojego fajnego wyboru trójkąta szybko dochodzimy że żaden inny punkt nie nalezy na zewnątrz równoległoboku ABCD. No ale wewnątrz tez nie moze być bo czwarty wierzchołek bedzie na zewnątrz. Sprzeczność
-- 27 cze 2011, o 15:54 --
IMO 1
Ukryta treść:
Niech prosta DK przecina AB w punkcie X wówczas korzystając z tego że prosta DK to oś potęgowa okręgów opisanych na trójkątach ADK i DKB oraz równości danej w zadaniu uzyskujemy iż X to środek AB. Analogicznie GL przechodzi przez ten środek. ABy dokończyć rozwiąznie wystarczy skorzystać z potęgi punktu X względem odpowiednich okręgów. Można pokazać ( robiąc to jak wyżej) iż założenie równości tych odcinków w zadaniu jest niepotrzebne gdyż proste DK i GL zawsze przecinają sie na prostej AB ( niech DK przetnie w X a GL w Y wówczas robimy te same obliczenia jak wyżej lecz uwzględniając k=XY dochodzimy wówczas iż k=0)
.
-- 27 cze 2011, o 16:17 --
Imo 6
Ukryta treść:
Niech \(\displaystyle{ H}\) to punkt przecięcia okręgów opisanych na \(\displaystyle{ AEC}\) i \(\displaystyle{ BCD}\). \(\displaystyle{ H}\) to tzw punkt Miguela dla czworokąta\(\displaystyle{ ECDO}\) ( Warto przemyśleć to). Ten punkt jest o tyle fajny że leży on również na okregach opisanych na \(\displaystyle{ BEO}\) i \(\displaystyle{ ADO}\). Aby wykazać teze wystarczy pokazać iż punkty \(\displaystyle{ IHCO}\) leża na okręgu czyli że zachodzi równość \(\displaystyle{ \sphericalangle CHO= \sphericalangle CIO}\). Istotnie \(\displaystyle{ \sphericalangle CHO=\sphericalangle AHO- \sphericalangle AHC= \sphericalangle ADO- \sphericalangle CEO}\). Lecz po prostych przeliczeniach na kątach uzaskamy ten sam wynik dla\(\displaystyle{ \sphericalangle CIO}\) ( korzystamy z tego że \(\displaystyle{ \sphericalangle CEA= \frac{1}{2}AIC}\) i styczności \(\displaystyle{ OI}\)do okręgu \(\displaystyle{ o}\)).
[MIX] Obóz przygotowujący do IMO
: 27 cze 2011, o 16:23
autor: pyzol
Jak dla mnie to pierwsze by szło jakoś tak:
Ukryta treść:
Dla uproszczenia zapisu weźmiemy zbiór \(\displaystyle{ S=\{1,2,...,n\}}\).
Zauważmy że najmniejszą wartością takiej funkcji jest \(\displaystyle{ f\left(\emptyset \right)}\). Tutaj również uprościmy zapis i założymy, że \(\displaystyle{ f\left(\emptyset \right)=0}\). Weźmy sobie teraz dwa rozłączne jednoelementowe zbiory. Mamy wtedy \(\displaystyle{ f(\{ i\} \cap \{ j\} )=f\left(\emptyset \right)=\min(f(\{ i\}), f(\{ j\})=0}\), wynika z tego, że istnieje tylko jeden jednoelementowy zbiór, taki, że \(\displaystyle{ f(\{i \})>0}\). I znów dla uproszczenia załóżmy, że to \(\displaystyle{ \{1 \},f(\{1 \})=1}\). Teraz weźmiemy zbiory dwuelementowe. \(\displaystyle{ f(\{1; i\} \cap \{1; j\} )=\min(f(\{1; i\}), f(\{1; j\})=1}\). Tutaj należałoby pokazać co z pozostałymi zbiorami mającymi 2 elementy. Wynika z tego, że może być tylko jeden zbiór, którego wartość funkcji będzie większa od \(\displaystyle{ 1}\). No i tu znowu ułatwienie zapisu: \(\displaystyle{ f(\{1;2\})=2}\) Dalej ciągniemy tę procedurę. Konstruując taką funkcję możemy uzyskać maksymalnie \(\displaystyle{ n+1}\) wartości.
[MIX] Obóz przygotowujący do IMO
: 27 cze 2011, o 17:43
autor: jerzozwierz
@pyzol, intuicja dobra, ale to jest cholernie trudno sformalizować. Lepiej pomyśleć nad zgrabniejszym i bardziej ścisłym rozwiązaniem.
@Burii, w IMO1 zostałeś ścięty do sześciu za konfiguracje trzeba pokazać, że K i L nie mogą leżeć po różnych stronach prostej AB.
IMO6 - może zrób po ludzku oO (i właściwie nigdzie nie napisałeś co to jest punkt O)
[MIX] Obóz przygotowujący do IMO
: 27 cze 2011, o 20:38
autor: Burii
O to ten punkt w zadaniu:D
[MIX] Obóz przygotowujący do IMO
: 28 cze 2011, o 12:54
autor: xiikzodz
1. Sformalizuję może to, co napisał pyzol:
Ukryta treść:
Funkcję \(\displaystyle{ f:P(S)\to R}\), składając ją ewentualnie ze stosowną bijekcją, możemy zastąpić funkcją przyjmującą warości będące kolejnymi liczbami naturalnymi począwszy od zera. Zachodzi wówczas\(\displaystyle{ f(X)\le|X|}\), gdzie \(\displaystyle{ |X|}\) to moc podzbioru \(\displaystyle{ X\subseteq S}\). Można to nie wprost pokazać. Funkcja \(\displaystyle{ f}\) jest monotoniczna w sensie \(\displaystyle{ X\subseteq Y \Rightarrow f(X)\le f(Y)}\), w szczególności \(\displaystyle{ f(\emptyset)=0}\). Niech \(\displaystyle{ k\in\mathbb{N}}\) będzie najmniejszą liczbą o tej własności, że istnieje \(\displaystyle{ \emptyset\neq X\subseteq S}\) taki, że \(\displaystyle{ k=f(X)>|X|}\) oraz niech \(\displaystyle{ Y\subseteq S}\) będzie taki, że \(\displaystyle{ f(Y)=k-1}\). Wówczas \(\displaystyle{ k-1=f(X\cap Y)}\) oraz \(\displaystyle{ |X\cap Y|<|X|}\) (monotoniczność \(\displaystyle{ f}\)) co przeczy minimalności liczby \(\displaystyle{ k}\).
Pozostaje więc wskazać funkcję przyjmującą wartości \(\displaystyle{ 0,1,2,\ldots n}\). Do tego wystarczy wziąć dowolny n+1-elementowy łańcuch \(\displaystyle{ \{S_i:i=0,1,\ldots n\}}\) różnych podzbiorów \(\displaystyle{ S}\) to znaczy rodzinę daną warunkami: \(\displaystyle{ S_0=\emptyset, S_i\subseteq S_{i+1}, |S_i|=i}\) i położyć \(\displaystyle{ f(X)=\max\{i:S_i\subseteq X\}}\) dla dowolnego \(\displaystyle{ X\subseteq S}\).
[MIX] Obóz przygotowujący do IMO
: 28 cze 2011, o 19:05
autor: jgarnek
W siódmym a oraz b nie mogą być zerowe, nie? (kontrprzykład: a=3, b=0, x=3, y=1)
7:
\(\displaystyle{ ax+by \equiv 0 \pmod{a^2+b^2}}\)
Mamy: \(\displaystyle{ ab(x^2+y^2) = ax \cdot bx + ay \cdot by \equiv (-by) \cdot bx + (-ax) \cdot ay \equiv -xy (a^2+b^2) \equiv 0 \pmod{a^2+b^2}}\)
czyli \(\displaystyle{ a^2+b^2|ab(x^2+y^2)}\)
gdyby te liczby były względnie pierwsze, to \(\displaystyle{ a^2+b^2|ab}\), a to jest niemożliwe, bo \(\displaystyle{ 0<|ab|<a^2+b^2=(|a|-|b|)^2+2|ab|}\)
dla \(\displaystyle{ a, b \neq 0}\)
IMO3:
Załóżmy nie wprost, że \(\displaystyle{ \frac{x^p-1}{x-1}=y^2-1}\).
Niech q będzie dowolnym dzielnikiem pierwszym \(\displaystyle{ \frac{x^p-1}{x-1}}\), różnym od
p. Wtedy \(\displaystyle{ x^p \equiv 1 \pmod{q}}\), więc rzędem x mod q jest 1 lub p. Jeżeli jednak
rzędem byłoby 1, to \(\displaystyle{ x \equiv 1 \pmod q \Rightarrow \frac{x^p-1}{x-1} = 1+x+x^2+...+x^{p-1}\equiv 1+1+...+1 \equiv p \equiv 0 \pmod{q}}\)
czyli \(\displaystyle{ q|p \Rightarrow p=q}\) -sprzeczność.
Stąd rzędem x mod q jest p. Stąd (jako że \(\displaystyle{ x^{q-1} \equiv 1 \pmod q}\)) mamy \(\displaystyle{ p|q-1}\).
Stąd dowolny dzielnik \(\displaystyle{ y^2-1=(y-1)(y+1)}\) jest równy p lub przystaje do 1 mod p.
Liczba p dzieli najwyżej jedną z liczb y-1, y+1 (\(\displaystyle{ NWD(y-1, y+1)=NWD(y-1, 2) \le 2<p}\)).
Rozważmy takie przypadki:
1. p nie dzieli ani y-1, ani y+1
wtedy obydwie liczby przystają do 1 mod p (niech \(\displaystyle{ y-1= \prod q_i^{a_i}}\) - wtedy \(\displaystyle{ q_i \equiv 1 \pmod p}\) dla każdego i, więc \(\displaystyle{ y-1 \equiv 1 \pmod p}\), analogicznie dla y+1), więc \(\displaystyle{ y +1 \equiv y-1 \pmod p \Rightarrow 2 \equiv 0 \pmod p}\) - sprzeczność
2. p dzieli y-1 - wtedy \(\displaystyle{ y+1 \equiv 1 \pmod p}\) -sprzeczność
3. p dzieli y+1 - wtedy \(\displaystyle{ y-1 \equiv 1 \pmod p}\) -sprzeczność (bo \(\displaystyle{ p \neq 3}\))
[MIX] Obóz przygotowujący do IMO
: 6 lip 2011, o 00:10
autor: Swistak
Zarówno do zad.7 i zad.8 już zostały napisane rozwiązania, ale moje sposoby wydają mi się dość interesujące, zatem też je napiszę.
zad. 8:
Opiszmy okręgi na trójkątach PCA i PCB. Z równości kątów danych w zadaniu wiemy, że te okręgi są styczne do prostej AB. Wiemy, że punkt Q leży na symetralnej odcinka PC, a punkty P i C są to punkty przecięcia tych okręgów. Ponadto Q leży na wspólnej stycznej tych okręgów, zatem punkt Q jest ich środkiem jednokładności. Niech D oznacza drugie przecięcia QC z okręgiem opisanym na PCB. Z tego, że te okręgi są jednokładne względem Q wynika, że \(\displaystyle{ \sphericalangle QCA= \sphericalangle QDB}\), a z tego, że okrąg opisany na PCB jest styczny do AB wynika \(\displaystyle{ \sphericalangle QDB= \sphericalangle CBA= \sphericalangle CBQ}\), zatem \(\displaystyle{ \sphericalangle QCA= \sphericalangle CBQ}\). Z prostych rachunków na kątach wynika, że \(\displaystyle{ \sphericalangle ACO=90^o - \sphericalangle CBA}\), zatem \(\displaystyle{ \sphericalangle ACO=90^o}\). Niech E oznacza środek AB. CP jest osią potęgową tych dwóch okręgów, zatem przechodzi przez E. \(\displaystyle{ \sphericalangle QEO=90^o}\), zatem na ACOE da się opisać okrąg, zatem \(\displaystyle{ \sphericalangle QCB= \sphericalangle QCE= \sphericalangle QOE}\), zatem trójkąty QCB i QOE są podobne, z czego wynika teza.
zad. 7:
Niech para liczb (a, b) będzie taka, że istnieją takie liczby całkowite (być może ujemne) x i y, że \(\displaystyle{ a^2+b^2|ax+by}\), \(\displaystyle{ a^2+b^2}\) i \(\displaystyle{ x^2+y^2}\) są względnie pierwsze oraz a+b jest najmniejsze z możliwych (a i b są nieujemne, zatem jeżeli teza by nie zachodziła, to taka para na pewno istnieje). Aby a+b było najmniejsze z możliwych musi oczywiście zachodzić to, że a i b są względnie pierwsze, bo dzieląc je przez ich NWD otrzymamy inną dobrą parę. \(\displaystyle{ (a^2+b^2)^2|(ax+by)^2=a^2x^2+2abxy+b^2y^2}\). Jeżeli pewna liczba pierwsza p dzieli \(\displaystyle{ a^2+b^2}\) w potędze k \(\displaystyle{ (k>0)}\), to dzieli \(\displaystyle{ (ax+by)^2}\) w potędze 2k, czyli większej od k.
Skoro \(\displaystyle{ a^2+b^2}\) i \(\displaystyle{ x^2+y^2}\) są względnie pierwsze, to jeżeli pewna liczba pierwsza p dzieli \(\displaystyle{ a^2+b^2}\) w potędze k, to dzieli \(\displaystyle{ (a^2+b^2)(x^2+y^2)=a^2x^2+a^2y^2+b^2x^2+b^2y^2}\) w potędze dokładnie k.
Jeżeli dodajemy dwie liczby i jedna z nich jest podzielna przez p w większej potędze niż ta druga, to suma jest podzielna przez potęgę p równą dokładnie tyle ile wynosi ta mniejsza z tych dwóch potęg, zatem dla każdej liczby pierwszej p, która dzieli \(\displaystyle{ a^2+b^2}\) w niezerowej potędze zachodzi, że dzieli ona w takiej samej potędze sumę liczb \(\displaystyle{ -(ax+by)^2}\) i \(\displaystyle{ (a^2+b^2)(x^2+y^2)}\), a wynosi ona \(\displaystyle{ a^2y^2-2abxy+b^2x^2=(ay-bx)^2}\), zatem każda liczba pierwsza p dzieląca \(\displaystyle{ a^2+b^2}\) dzieli tę liczbę w parzystej potędze, zatem \(\displaystyle{ a^2+b^2=c^2}\) dla pewnego całkowitego c. A my wiemy, że rozwiązania takiego równania przedstawiają się w formie \(\displaystyle{ a=(m^2-n^2)d \ \ b=2mnd \ \ c=(m^2+n^2)d}\), gdzie m i n są względnie pierwsze (można założyć, że m>n). Ale a i b są względnie pierwsze, zatem d=1. Możemy zatem napisać, że \(\displaystyle{ (m^2+n^2)^2|(m^2-n^2)x+2mny}\), zatem \(\displaystyle{ m^2+n^2|2mny-2n^2x=2n(my-nx)}\). Ale m i n są względnie pierwsze, zatem \(\displaystyle{ m^2+n^2}\) i n też, zatem \(\displaystyle{ m^2+n^2|2(my-nx)}\). Ponadto wiemy, że m i n są względnie pierwsze, zatem nie mogą być obie parzyste. Gdyby obie te liczby były nieparzyste, to zarówno a jak i b byłyby parzyste, a miały być względnie pierwsze. Zatem dokładnie jedna z liczb m i n jest parzysta, zatem \(\displaystyle{ m^2+n^2|my-nx}\). Dodatkowo wiemy, że \(\displaystyle{ x^2+y^2}\) jest względnie pierwsze z \(\displaystyle{ a^2+b^2}\), czyli z \(\displaystyle{ (m^2+n^2)^2}\), a więc też z \(\displaystyle{ m^2+n^2}\).
Zatem para liczb \(\displaystyle{ (m, n)}\) spełnia warunki, że istnieją takie całkowite x i y, że \(\displaystyle{ m^2+n^2|my+nx}\) oraz \(\displaystyle{ m^2+n^2}\) i \(\displaystyle{ x^2+y^2}\) są względnie pierwsze (tylko za x trzeba podstawić -x) i dodatkowo nietrudno sprawdzić, że \(\displaystyle{ m+n<a+b}\) (bo \(\displaystyle{ m+n<m^2+n^2<m^2-n^2+2mn=a+b}\)), co stoi w sprzeczności z minimalnością a+b.
[MIX] Obóz przygotowujący do IMO
: 6 lip 2011, o 12:14
autor: jgarnek
Skoro nikt jeszcze nie przedstawił dowodu do IMO4, to pokażę swój (ale nie krępujcie się, chętnie zobaczę coś lepszego)
IMO4:
Niech: \(\displaystyle{ K_{ij}=\sum_{1 \le k,l \le n; \quad k \neq i, l \neq j}(a_{ij}+a_{kl}-a_{il}-a_{kj})^2}\)
(sumujemy po wszystkich k,l różnych od i,j)
Wtedy: \(\displaystyle{ \left( \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} \right) ^2 + n^2 \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} ^2 -n \left( \sum_{i=1}^{n} \left( \sum_{j=1}^{n}a_{ij} \right)^2 + \sum_{j=1}^{n} \left( \sum_{i=1}^{n}a_{ij} \right)^2 \right) = \frac{1}{4} \sum_{1 \le i,j \le n} K_{ij}}\)
a to kończy dowód, bo wszystkie \(\displaystyle{ K_{ij}}\) są (jako sumy kwadratów) nieujemne. Oczywiście trzeba jeszcze udowodnić tę tożsamość
Dowód
Niech: \(\displaystyle{ S= \sum_{1 \le i,j \le n}a_{ij}^2}\), \(\displaystyle{ A=\sum_{i=1}^{n} \sum_{1 \le j < l \le n} a_{ij} a_{il}}\)
(A- suma wszystkich iloczynów par liczb, które znajdują się w tym samym wierszu) \(\displaystyle{ B=\sum_{j=1}^{n} \sum_{1 \le i < k \le n} a_{ij} a_{kj}}\)
(B- suma wszystkich iloczynów par liczb, które znajdują się w tej samej kolumnie) \(\displaystyle{ C=\sum_{1 \le i < k \le n; \quad 1 \le j \neq l \le n}a_{ij} a_{kl}}\)
(C- suma wszystkich iloczynów par liczb, które nie znajdują się w tej samej kolumnie ani wierszu)
\(\displaystyle{ \sum_{1 \le i,j \le n}K_{ij}= \sum_{1 \le i,j \le n} \qquad \sum_{1 \le k,l \le n; \quad k \neq i, l \neq j}(a_{ij}+a_{kl}-a_{il}-a_{kj})^2 = \sum_{1 \le i,j \le n} \qquad \sum_{1 \le k,l \le n; \quad k \neq i, l \neq j}(a_{ij}^2+a_{kl}^2+a_{il}^2+a_{kj}^2+2a_{ij}a_{kl}+2a_{il}a_{kj}-2a_{ij}a_{il}-2a_{ij}a_{kj}-2a_{kl}a_{il}-2a_{kl}a_{kj})=
\textrm{...(dwie strony później)...}=4(n-1)^2 S+8C+8(1-n)(A+B)}\)
Pełnych obliczeń nie przedstawiam, ale jak ktoś chce to jest to naprawdę niezłe ćwiczonko na kombinowanie z sumami Może dowód indukcyjny tej tożsamości jest łatwiejszy, ale nie chciało mi się już kombinować.
[MIX] Obóz przygotowujący do IMO
: 7 lip 2011, o 15:07
autor: timon92
imo 2
Ukryta treść:
\(\displaystyle{ m:=n}\) daje nam \(\displaystyle{ f(f(n))=2f(n)}\). Podstawienie \(\displaystyle{ n:=f(n)}\) daje \(\displaystyle{ f(m+f(n)) = f(m)+2f(n)}\), natomiast \(\displaystyle{ m:=m+n}\) daje \(\displaystyle{ f(m+f(n))=f(m+n)+f(n)}\). Stąd wniosek że \(\displaystyle{ f(m+n)=f(m)+f(n)}\) i stąd funkcja jest liniowa. Łatwo sprawdzić że tylko \(\displaystyle{ f(n)=0, f(n)=2n}\) pasują
[MIX] Obóz przygotowujący do IMO
: 7 lip 2011, o 20:15
autor: Swistak
Zadanie 9 jest zaiste za***iste . Zrobiłem już trochę z tych zadań i 3, które mi się najbardziej podobają to 3 zadania z 3 dnia . Moje rozwiązanie 9 może przerazić wyglądem, ale zachęcam do tego, aby się go nie przestraszyć ; p.
zad. 9:
Odpowiedź to potęgi dwójki. Ale zobaczymy, jak do tego dojść.
Jaka lekcja płynie z tego zadania? Jeżeli jeden ciąg ma być permutacją drugiego, to wszystkie symetryczne funkcje wielu zmiennych przyjmują dla tych ciągów takie same wartości. Przykładem takiej funkcji może być suma k-tych potęg elementów, albo ich iloczyn. W tym zadaniu chwycimy się właśnie sum k-tych potęg.
Nietrudno zauważyć, że suma elementów ciągu a i ciągu b jest taka sama.
Skoro te 2 ciągi dane w zadaniu są swoimi permutacjami, to suma kwadratów ich elementów jest taka sama, zatem \(\displaystyle{ (n-1) \sum_{}^{}a_i^2+ \sum_{i \neq j}^{}a_ia_j= \sum_{i<j}^{} (a_i+a_j)^2= \sum_{i<j}^{} (b_i+b_j)^2= (n-1) \sum_{}^{}b_i^2+ \sum_{i \neq j}^{}b_ib_j}\)
Ale \(\displaystyle{ \sum_{}^{}a_i^2+ \sum_{i \neq j}^{}a_ia_j= (\sum_{}^{} a_i)^2=(\sum_{}^{} b_i)^2=\sum_{}^{}b_i^2+ \sum_{i \neq j}^{}b_ib_j}\), zatem
odejmując od siebie stronami otrzymane równości otrzymamy, że suma kwadratów elementów ciągu a i ciągu b są sobie równe, o ile n jest różne od 2.
Teraz wykażemy, że jeżeli sumy zerowych, pierwszych, ..., k-tych potęg elementów ciągu a i b są sobie równe, oraz \(\displaystyle{ n \neq 2^k}\), to sumy k+1-szych potęg też. \(\displaystyle{ (2^{k+1}-2) \sum_{}^{} a_i^{k+1}+ {k+1 \choose 1} \sum_{i \neq j}^{}a_i^ka_j + {k+1 \choose 2} \sum_{i \neq j}^{}a_i^{k-1}a_j^2+...+ {k+1 \choose k} \sum_{i \neq j}^{}a_ia_j^k=\\
{k+1 \choose 1} \sum_{}^{} a_i^k \sum_{}^{} a_i + {k+1 \choose 2} \sum_{}^{}a_i^{k-1} \sum_{}^{} a_i^2+...+ {k+1 \choose k} \sum_{}^{} a_i \sum_{}^{} a_i^k={k+1 \choose 1} \sum_{}^{} b_i^k \sum_{}^{} b_i + {k+1 \choose 2} \sum_{}^{}b_i^{k-1} \sum_{}^{} b_i^2+...+ {k+1 \choose k} \sum_{}^{} b_i \sum_{}^{} b_i^k=(2^{k+1}-2) \sum_{}^{} b_i^{k+1}+ {k+1 \choose 1} \sum_{i \neq j}^{}b_i^kb_j + {k+1 \choose 2} \sum_{i \neq j}^{}b_i^{k-1}b_j^2+...+ {k+1 \choose k} \sum_{i \neq j}^{}b_ib_j^k}\)
Zobaczmy teraz, co dostaniemy, jak weźmiemy dwukrotności sum k+1-szych potęg dwóch stworzonych w zadaniu ciągów (wiemy, że są one sobie równe). \(\displaystyle{ 2\sum_{i<j}^{} (a_i+a_j)^{k+1}= \sum_{i \neq j}^{} (a_i+a_j)^{k+1}=\\2(n-1) \sum_{}^{} a_i^{k+1}+ \sum_{i \neq j}^{} ( {k+1 \choose 1}a_i^ka_j+ {k+1 \choose 2}a_i^{k-1}a_j^2+...+ {k+1 \choose k} a_ia_j^{k})= \\ (2n-2) \sum_{}^{} a_i^{k+1}+ {k+1 \choose 1} \sum_{i \neq j}^{}a_i^ka_j + {k+1 \choose 2} \sum_{i \neq j}^{}a_i^{k-1}a_j^2+...+ {k+1 \choose k} \sum_{i \neq j}^{}a_ia_j^k}\)
Mamy zatem \(\displaystyle{ (2n-2) \sum_{}^{} a_i^{k+1}+ {k+1 \choose 1} \sum_{i \neq j}^{}a_i^ka_j + {k+1 \choose 2} \sum_{i \neq j}^{}a_i^{k-1}a_j^2+...+ {k+1 \choose k} \sum_{i \neq j}^{}a_ia_j^k=\\
(2n-2) \sum_{}^{} b_i^{k+1}+ {k+1 \choose 1} \sum_{i \neq j}^{}b_i^kb_j + {k+1 \choose 2} \sum_{i \neq j}^{}b_i^{k-1}b_j^2+...+ {k+1 \choose k} \sum_{i \neq j}^{}b_ib_j^k}\)
oraz \(\displaystyle{ (2^{k+1}-2) \sum_{}^{} a_i^{k+1}+ {k+1 \choose 1} \sum_{i \neq j}^{}a_i^ka_j + {k+1 \choose 2} \sum_{i \neq j}^{}a_i^{k-1}a_j^2+...+ {k+1 \choose k} \sum_{i \neq j}^{}a_ia_j^k=\\ (2^{k+1}-2) \sum_{}^{} b_i^{k+1}+ {k+1 \choose 1} \sum_{i \neq j}^{}b_i^kb_j + {k+1 \choose 2} \sum_{i \neq j}^{}b_i^{k-1}b_j^2+...+ {k+1 \choose k} \sum_{i \neq j}^{}b_ib_j^k}\)
Z czego otrzymujemy wniosek, że jeżeli \(\displaystyle{ n \neq 2^k}\) i jeżeli sumy 0-wych, 1-szych, ..., k-tych potęg elementów ciągu a i ciągu b, były takie same, to sumy k+1-szych potęg też są.
Zatem jeżeli n nie jest potęgą dwójki, to dla dowolnego k, sumy k-tych potęg elementów ciągów a i b są takie same. Gdyby największe elementy ciągu a i ciągu b byłyby różne, to dla dostatecznie dużych n to nie mogłoby być możliwe, zatem są one równe. Zauważmy teraz, że drugie, co do wielkości elementy tych ciągów też muszą być równe, gdyż z każdej takiej sumy k-tych potęg możemy wywalić po największym elemencie i wtedy otrzymamy, że dla dowolnego k, sumy k-tych potęg elementów ciągu a i ciągu b, oprócz największych elementów, są sobie równe. To oznacza, że dla dostatecznie dużych k coś by się posypało, gdyby drugie od końca elementy byłby takie same. Postępując tak dalej otrzymujemy, że ciąg a i ciąg b składają się z tych samych elementów, czyli są swoimi permutacjami.
Teraz wystarczy jedynie pokazać przykłady dla potęg dwójki, co wbrew pozorom wcale nie jest takie łatwe.
Dla n=2 możemy wziąć \(\displaystyle{ a_1=0, \ \ a_2=3, \ \ b_1=1, \ \ b_2=2}\).
Załóżmy teraz, że skonstruowaliśmy już jakiś przykład dla \(\displaystyle{ n=2^k}\) i skonstruujemy dla \(\displaystyle{ n=2^{k+1}}\). Początkowe \(\displaystyle{ 2^k}\) wyrazów są takie same. Niech \(\displaystyle{ a_{2^k+i}=b_{i}+2^{k+1}}\) oraz \(\displaystyle{ b_{2^k+i}=a_{i}+2^{k+1}}\). Przykładowo dla n=8 te ciągi to \(\displaystyle{ 0, 3, 5, 6, 9, 10, 12, 15}\) \(\displaystyle{ 1, 2, 4, 7, 8, 11, 13, 14}\)
Nietrudno sprawdzić, że tak określone ciągi spełniają warunki zadania.
Swoją drogą konstrukcja takich ciągów jest prawie całym rozwiązaniem zadania 32 ze Zwardonia 08 . Warto też zauważyć, że dla danych 2 ciągów sumy 0-wych, 1-szych, ..., (k-1)-szych potęg są takie same, co wynika z analizy przeprowadzonego wcześniej dowodu i zobaczenia, kiedy on się sypie.
[MIX] Obóz przygotowujący do IMO
: 8 lip 2011, o 14:17
autor: timon92
imo 6 szkic ludzkiego rozwiązania ;p
Ukryta treść:
należy pokazać, że te okręgi przechodzą przez jakiś punkt X różny od C (lub że są styczne - to zaś nie może zajść, bo wtedy AE i BC byłyby równoległe)
robimy inwersję w C i teza jest taka, że BD, AE, XI są współpękowe. Mamy jakąś taką konfigurację, że mamy prostą AB; okręgi styczne do tej prostej w punktach A,B przecinają się w punktach C, X. AC tnie okrąg BCX w punkcie D, BC tnie okrąg ACX w punkcie E, punkt I jest symetryczny do C względem AB. Okazuje się, że okrąg ABX jest styczny do prostych BD, AE oraz że punkt I leży na tym okręgu i na dodatek XI jest symedianą w trójkącie ABX. To oznacza, że proste XI, BD, AE są współpękowe, czyli to co chcieliśmy.
[MIX] Obóz przygotowujący do IMO
: 9 lip 2011, o 13:59
autor: jerzozwierz
Zadanie dziewiąte rozwiązane sto razy krócej, chociaż to jest czysta magia: (to działa dla całkowitych, dla rzeczywistych wystarczy uderzyć jakąś bazą nad Q)
Ukryta treść:
Niech \(\displaystyle{ f(x) = \sum_{i=1}^{n} x^{a_i}}\) i \(\displaystyle{ g(x) = \sum_{i=1}^{n} x^{b_i}}\), \(\displaystyle{ f(x) - g(x) = (x-1)^k h(x)}\), \(\displaystyle{ h(1) \neq 0}\). Teza jest równoważna \(\displaystyle{ f(x)^2 - f(x^2) = g(x)^2 - g(x^2)}\), czyli \(\displaystyle{ (x-1)^k h(x) (f(x)+g(x)) = (x^2 - 1)^k h(x^2)}\), czyli \(\displaystyle{ (f(x)+g(x))h(x) = (x+1)^kh(x^2)}\), wstawiając \(\displaystyle{ x=1}\), \(\displaystyle{ f(1)+g(1) = 2^k}\), ale \(\displaystyle{ f(1)+g(1) = 2n}\), więc \(\displaystyle{ n}\) jest potęgą dwójki, abrakadabra. Przykład dla potęg dwójki indukcyjny, mając ciągi \(\displaystyle{ a_1, ... a_m}\) i \(\displaystyle{ b_1, ... b_m}\) bierzemy pierwszy ciąg \(\displaystyle{ a_1,...,a_m, M+b_1, ... M+b_m}\) a drugi taki sam tylko zamienione a z b, \(\displaystyle{ M=wchoy}\).