EGMO 2012 - Polki wygrały!

[adamm]

Dzień 1.

1. Punkt \(\displaystyle{ O}\) jest środkiem okręgu opisanego na trójkacie \(\displaystyle{ ABC}\). Punkty \(\displaystyle{ D, E, F}\) leżą odpowiednio we wnętrzach boków \(\displaystyle{ BC, CA}\) oraz \(\displaystyle{ AB}\), przy czym prosta \(\displaystyle{ DE}\) jest prostopadła do prostej \(\displaystyle{ CO}\) oraz prosta \(\displaystyle{ DF}\) jest prostopadła do prostej \(\displaystyle{ BO}\). Punkt \(\displaystyle{ K}\) jest środkiem okręgu opisanego na trójkacie \(\displaystyle{ AFE}\). Wykazać, że proste \(\displaystyle{ DK}\) oraz \(\displaystyle{ BC}\) są prostopadłe.
(Uwaga: Punkt \(\displaystyle{ Z}\) lezy we wnętrzu odcinka \(\displaystyle{ XY}\) , jeśli leży on na prostej \(\displaystyle{ XY}\) pomiędzy punktami \(\displaystyle{ X}\) oraz \(\displaystyle{ Y}\) .)

2. Dana jest liczba całkowita dodatnia \(\displaystyle{ n}\). Wyznaczyć, w zależności od \(\displaystyle{ n}\), największą możliwą liczbę całkowitą \(\displaystyle{ m}\) o następującej własności: tabelę posiadającą \(\displaystyle{ m}\) wierszy i \(\displaystyle{ n}\) kolumn można wypełnic liczbami rzeczywistymi w taki sposób, by dla każdych dwóch róznych wierszy \(\displaystyle{ [a_1, a_2,\ldots, a_n]}\) oraz \(\displaystyle{ [b_1, b_2,\ldots, b_n]}\) spełnione
było:

\(\displaystyle{ \max(|a_1-b_1|, |a_2-b_2|,\ldots, |a_n-b_n|) = 1.}\)

3. Wyznaczyć wszystkie funkcje \(\displaystyle{ f:\mathbb{R}\rightarrow\mathbb{R}}\) spełniające równanie

\(\displaystyle{ f\left(yf(x+y)+f(x)\right)=4x+2yf(x+y)}\)

dla wszystkich \(\displaystyle{ x,y\in\mathbb{R}.}\)

4. Zbiór liczb całkowitych \(\displaystyle{ A}\) nazywamy pełnym ze względu na sumy jesli \(\displaystyle{ A \subseteq A+A}\), to znaczy każdy element \(\displaystyle{ a\in A}\) jest sumą pewnej pary (niekoniecznie różnych) elementów \(\displaystyle{ b, c\in A}\). Zbiór liczb całkowitych \(\displaystyle{ A}\) nazywamy zero-wolnym ze względu na sumy jeśli \(\displaystyle{ 0}\) jest jedyną liczbą całkowitą, której nie da się przedstawić jako sumy elementów niepustego, skończonego podzbioru zbioru \(\displaystyle{ A}\).
Czy istnieje zbiór liczb całkowitych, który jest zarówno pełny za względu na sumy, jak i zero-wolny ze względu na sumy?

[tometomek91]

1.

Ukryta treść:    

Niech prosta \(\displaystyle{ CO}\) przecina okrąg o środku \(\displaystyle{ O}\) w punkcie \(\displaystyle{ P}\) i prosta \(\displaystyle{ BO}\) w punkcie \(\displaystyle{ Q}\). Niech \(\displaystyle{ DF \cap BO=M}\) i \(\displaystyle{ DE \cap CO=L}\). Ponieważ \(\displaystyle{ \angle CQB= \angle CPB}\) i \(\displaystyle{ \Delta CLD \sim \Delta PBC}\) oraz \(\displaystyle{ \Delta BMD \sim \Delta QCB}\), to \(\displaystyle{ \angle FDB = \angle EDC}\). Oznaczmy \(\displaystyle{ \angle FDB = \angle EDC=\alpha}\) i \(\displaystyle{ \angle BFD = \beta}\) i \(\displaystyle{ \angle DEC= \gamma}\). Zauważmy, że \(\displaystyle{ \gamma = \angle APC}\) i \(\displaystyle{ \beta = AQB}\) czyli \(\displaystyle{ \alpha + \beta + \gamma = \pi}\) jako suma kątów naprzeciwległych w czworokącie wpisanym w okrąg. Stąd \(\displaystyle{ \angle ABC=\gamma}\), \(\displaystyle{ \angle ACB=\beta}\) i \(\displaystyle{ \angle BAC=\alpha}\). I dalej \(\displaystyle{ \angle EKF=2 \alpha}\) a ponieważ \(\displaystyle{ \angle FDE = \pi- 2 \alpha}\) więc na \(\displaystyle{ KFDE}\) mozna opisac okrąg i z równości kątów \(\displaystyle{ KFE}\) i \(\displaystyle{ KEF}\) wynika, że kąt \(\displaystyle{ KDB}\) jest równy kątowi \(\displaystyle{ KDC}\), cnd.

[adamm]

1. inaczej:    

Niech \(\displaystyle{ G=BE \cap CF}\), szybko przeliczamy na katach, że \(\displaystyle{ G}\) należy od okręgu opisanego na trójkącie \(\displaystyle{ AFE}\), łatwo zauważyć teraz, że \(\displaystyle{ D}\) jest punktem Miquela czworoboku zupełnego \(\displaystyle{ AFGEBC}\). Niech \(\displaystyle{ X,Y}\) będą teraz środkami odpowiednio \(\displaystyle{ GE,AF}\), rozważmy sobie podobieństwo spiralne przekształcające \(\displaystyle{ G}\) na \(\displaystyle{ F}\) i \(\displaystyle{ E}\) na \(\displaystyle{ A}\), ma ono środek w punkcie \(\displaystyle{ D}\) i przekształca także \(\displaystyle{ X}\) na \(\displaystyle{ Y}\), więc czworokąt \(\displaystyle{ XYBD}\) jest cykliczny, ale ponieważ \(\displaystyle{ KY\perp AF, KX\perp GE}\), więc \(\displaystyle{ K}\) też należy do okręgu opisanego na \(\displaystyle{ XYBD}\), stąd już mamy, że istotnie \(\displaystyle{ \angle BDK=90^{\circ}}\).
Dziwi mnie trochę, że dali na zawodach tak nieskończenie znaną konfigurację ._.

[MadJack]

3.:    

Najpierw \(\displaystyle{ y:=0}\), dostajemy \(\displaystyle{ (1) f(f(x))=4x}\). Teraz \(\displaystyle{ x:=0}\) i mamy \(\displaystyle{ f(y \cdot f(y) + f(0)) = 2y \cdot f(y)}\). Funkcja jest różnowartościowa, gdyż w przeciwnym wypadku byłoby dla \(\displaystyle{ x \neq y}\):
\(\displaystyle{ f(f(x))=f(f(y))}\), więc z \(\displaystyle{ (1)}\): \(\displaystyle{ 4x=4y}\), co przeczy założeniu.
Zauważmy, że z \(\displaystyle{ (1)}\) mamy również \(\displaystyle{ f(f( \frac{1}{2}y \cdot f(y)) = 2y \cdot f(y)}\), skąd z różnowartościowości funkcji mamy:
\(\displaystyle{ (2) y \cdot f(y) + f(0) = f( \frac{1}{2}y \cdot f(y))}\)
Teraz oznaczmy \(\displaystyle{ f(0)=a}\). Mamy \(\displaystyle{ f(a)=f(f(0))=0}\) i \(\displaystyle{ f(f(a))=4a}\), czyli \(\displaystyle{ f(0)=4a}\), więc \(\displaystyle{ f(0)=0}\). Także z \(\displaystyle{ (2)}\) mamy już wniosek, że \(\displaystyle{ f(x)=2x}\), łatwo sprawdzić, że ta funkcja spełnia to równanie.

Mam nadzieję, że nie pomyliłem się nigdzie

[timon92]

MadJack, ostatni wniosek jest błędny,

Ukryta treść:    

możesz jedynie wnioskować, że \(\displaystyle{ f(x) = 2x}\) dla argumentów postaci \(\displaystyle{ \frac 12 y f(y)}\)

trzeba to jeszcze chwilę pomęczyć żeby wyszło to co trzeba

[Leszczu21]

(Uwaga: Punkt \(\displaystyle{ Z}\) lezy we wnętrzu odcinka \(\displaystyle{ XY}\) , jeśli leży on na prostej \(\displaystyle{ XY}\) pomiędzy punktami \(\displaystyle{ X}\) oraz \(\displaystyle{ Y}\) .)

Świetne

[Swistak]

4:    

\(\displaystyle{ a_{i-1}=(-1)^iF_i}\) dla \(\displaystyle{ i \geq 2}\), gdzie \(\displaystyle{ F}\) to ciąg Fibonacciego.

[marcin_smu]

3:    

Podstawiamy \(\displaystyle{ y=0}\): \(\displaystyle{ f(f(x))=4x}\) (f jest różnowartościowa)
Podstawiamy \(\displaystyle{ y=-3}\) i \(\displaystyle{ x=4}\): \(\displaystyle{ f(-3f(1)+f(f(f(1))) )=16-6f(1) \Rightarrow f(f(1))=16-6f(1) \Rightarrow f(1)=2}\)
Następnie podstawiamy \(\displaystyle{ y=1-x}\): \(\displaystyle{ f(2-2x+f(x))=4=f(f(1))=f(2)}\) Czyli dzięki różnowartościowości \(\displaystyle{ 2-2x+f(x)=2 \Rightarrow f(x)=2x}\).

[Sylwek]

1:    

\(\displaystyle{ \angle BAC=x}\), stąd \(\displaystyle{ \angle EKF = \angle BOC = 2x}\) (kąty środkowe), dalej \(\displaystyle{ \angle OBC = \angle OCB = 90^o-x = \angle KEF = \angle KFE}\) (trójkąty równoramienne). Teraz wykorzystując dwie prostopadłości dostajemy \(\displaystyle{ \angle CDE = x = \angle BDF}\), czyli \(\displaystyle{ \angle EDF=180^o-2x}\). Stąd mamy okrąg \(\displaystyle{ o(K,E,D,F)}\) i z kątów wpisanych \(\displaystyle{ \angle EDK= \angle EFK = 90^o-x}\), czyli \(\displaystyle{ \angle KDC = (90^o-x)+x=90^o}\).

2:    

Zamiast \(\displaystyle{ m}\) będę używał \(\displaystyle{ f(n)}\). Pokażemy przez indukcję \(\displaystyle{ f(n)=2^n}\). Indukcja przyda nam się tylko do tego, żeby mieć zawsze na wcześniejszych \(\displaystyle{ n}\) nierówności: \(\displaystyle{ f(n)<+\infty}\) ( ) oraz \(\displaystyle{ f(k-1)< f(k)}\) przy kroku indukcyjnym. Można to omijać na inne sposoby, być może prostsze, ale pokażę indukcję.

Łatwo na palcach policzyć, że \(\displaystyle{ f(1)=2}\). Zakładamy dla pewnego \(\displaystyle{ k \ge 2}\), że dla wszystkich \(\displaystyle{ n \in \lbrace 1, \ldots k-1 \rbrace}\) jest \(\displaystyle{ f(n)=2^n}\). Pokażemy stąd, że \(\displaystyle{ f(k)=2^k}\)

Kilka obserwacji:

(1) Oczywiście tablica o \(\displaystyle{ 2^k}\) wierszach, której wierszami jest wszystkie możliwe \(\displaystyle{ 2^k}\) ciągów \(\displaystyle{ \lbrace 0,1 \rbrace^k}\) spełnia warunki zadania, stąd \(\displaystyle{ f(k) \ge 2^k}\).

(2) Weźmy pewną tablicę o \(\displaystyle{ k}\) kolumnach spełniającą warunki zadania (ilość wierszy \(\displaystyle{ \ge 2^k}\)). Jeśli w pewnej kolumnie mamy 3 różne liczby \(\displaystyle{ x<y<z}\) (możemy oczywiście przyjąć, że w takim wypadku \(\displaystyle{ x}\) to minimalna wartość w komórkach tej kolumny, a \(\displaystyle{ z}\) - maksymalna), to po zastąpieniu wartości \(\displaystyle{ y}\) przez \(\displaystyle{ x}\) lub \(\displaystyle{ z}\) również dostaniemy tablicę spełniającą warunki zadania. Wynika to od razu z prawdziwej dla dowolnego elementu tej kolumny nierówności: \(\displaystyle{ |y-t| < max \lbrace |z-t|, |x-t| \rbrace \le 1}\), pierwsza nierówność wynika z warunku narzuconego na \(\displaystyle{ x,y,z}\), druga z warunków zadania. Czyli wystarczy się ograniczyć do tablic, gdzie każda kolumna zawiera max. 2 różne wartości.

(3) Jeśli tablica spełnia warunki zadania, to jeśli do każdej komórki w pewnej kolumnie dodamy tę samą liczbę rzeczywistą, to również dostaniemy tablicę spełniającą warunki zadania. Czyli zawężamy poprzednie kryteria o taki warunek: minimum i-tej każdej kolumny jest równe 0, a maksimum to \(\displaystyle{ M_i}\) (dla każdego \(\displaystyle{ i \in \langle 1, k \rangle}\)).

(4) Jeśli pewne \(\displaystyle{ M_i<1}\), to na modułach różnic wartości pośród wyrazów tej i-tej kolumny nigdy nie jest realizowane maksimum zadane w poleceniu. To oznacza, że tablica powstała po wycięciu i-tej kolumny spełnia warunki zadania dla \(\displaystyle{ k-1}\) kolumn. Ale liczba wierszy jest \(\displaystyle{ \ge 2^k > 2^{k-1}=f(k-1)}\), sprzeczność (**). Stąd każde \(\displaystyle{ M_i}\) jest równe 1 (oczywiście większe być nie może). Czyli możemy poprzedni wybór ograniczyć do tablic, gdzie minimum i-tej kolumny jest równe 0, a maksimum 1.

(5) To wszystko oznacza, że w poszukiwaniu \(\displaystyle{ f(k)}\) wystarczy się przyjrzeć tablicom zero-jedynkowym. Z tego dostajemy, że każdy wiersz (jak widać, cały czas przekornie operowaliśmy na kolumnach) jest pewnym ciągiem z \(\displaystyle{ \lbrace 0,1 \rbrace^k}\), więc gdyby \(\displaystyle{ f(k)>2^k}\), to pewne dwa wiersze byłyby równe, a to znaczy, że ich odległość zadana w poleceniu by była równa 0. A tak być nie może.

Czyli \(\displaystyle{ f(k)=2^k}\).

P.S. (**) to jedyne miejsce, gdzie użyłem założenia indukcyjnego. Jak widać, można było w ogóle nie używać słowa indukcja, po prostu wycinając te \(\displaystyle{ t}\) kolumn, na których maksimum nie jest wybijane dla żadnej pary wierszy, dalej byśmy rozumowali dla tablicy o \(\displaystyle{ k-t}\) kolumnach, że \(\displaystyle{ f(k) \le 2^{k-t} \le 2^k}\). Już nie będę zmieniał, niech to zostanie jako opis subtelności przy opisywaniu kombinatoryki. Z drugiej strony tak głupio by było, gdyby dopiero po przeprowadzeniu pełnego dowodu stwierdzić, że \(\displaystyle{ f(k-1)<f(k)<+\infty}\).

4:    

\(\displaystyle{ a_{i-1}=(-1)^iF_i}\) dla \(\displaystyle{ i \geq 2}\), gdzie \(\displaystyle{ F}\) to ciąg Fibonacciego.

Nie działa to ("-3" nie otrzymasz).

[timon92]

Sylwek, -3 = 1 + 3 - 2 - 5

jeśli ktoś nie śledził konkursu, to był jeszcze drugi dzień zawodów (zadania są tu )

nasze reprezentantki zdobyły złoty medal oraz trzy srebrne, natomiast w klasyfikacji drużynowej (polegającej na zsumowaniu wyników indywidualnych) nasze dziewczęta wywalczyły pierwsze miejsce

gratulujemy!

[Sylwek]

Sylwek, -3 = 1 + 3 - 2 - 5

Dzięki. Działa to jednak

A tu klasyfikacja:


Przyłączam się do gratulacji!

[Swistak]

Plis, co to za staty za 8:    

Załóżmy, że dane na początku słowo nie jest okresowe. Jeżeli jest, to musi być złożone z tych samych liter, bo zamieniając 2 różne stojące obok siebie otrzymamy nieokresowe. Załóżmy, ze po jakiejś zamianie liter otrzymaliśmy słowo, które jest \(\displaystyle{ k-okresowe}\) (oznaczmy tak słowa, dla których istnieje takie słowo, że napisane \(\displaystyle{ k}\) razy tworzy nam nasze słowo). Oczywiście \(\displaystyle{ k|n}\). Nietrudno także zauważyć, że jeżeli chcemy otrzymać słowo \(\displaystyle{ k-okresowe}\) z przestawienia 2 liter, to jak \(\displaystyle{ k>2}\) to możemy wybrać co najwyżej 1 taką parę sąsiednich literek, a jak \(\displaystyle{ k=2}\) to co najwyżej 2 takie pary. Zatem par literek, po których zamianie otrzymamy słowo okresowe jest co najwyżej \(\displaystyle{ d(n)}\), gdzie to coś oznacza liczbę dzielników \(\displaystyle{ n}\). A ma ich być \(\displaystyle{ n-1}\), zatem \(\displaystyle{ n-1 \leq d(n) \Rightarrow n \leq 4}\) i każdy już sobie sprawdzi tezę

[kaszubki]

Co do zadania 8.:

Ukryta treść:    

ale chamówa:
ciekawe, czy to Dan Schwarz zaproponował to zadanie na egmo

[Sylwek]

O sukcesie Polek napisała Gazeta Wyborcza:

[humanistyczna dusza]

Nie dość, że mamy w Polsce najpiękniejsze kobiety, to jeszcze mamy najlepsze matematyczki .