Matematyka.pl

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.

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ę ._.

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.

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

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

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}\).

\(\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}\).

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}\).

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ę

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