Rozwi _{}azania

1. (by Chuck Norris)

Oznaczmy nasze liczby poprzez a, b, c, d, mamy wi_{}ec równania:

\{ \begin{matrix}a + bcd = 2 \\ b + acd = 2 \\ c + abd = 2 \\ d + abc = 2 \end{matrix}

Najpierw załóżmy, że któraś z liczb jest równa 0, bez szkody na ogólności a. Wówczas mamy, że b = 2, c = 2, d = 2, wi_{}ec i 2 · 2 · 2 = 2, to troch_{}e sprzeczność. Wi_{}ec żadna z liczb nie może być zerem. Weźmy pierwsze dwa równania i odejmijmy stronami. Uzyskujemy wówczas:

a − b + bcd − acd = 0
(a − b)(cd − 1) = 0

Mamy wi_{}ec, że a i b s _{}a równe lub c i d s _{}a nawzajem swoimi odwrotnościami - bo tylko wtedy cd = 1. Analogicznie rozumuj _{}ac dla każdej pary równań mamy, że dla każdej pary liczb albo s _{}a one równe albo pozostałe dwie s _{}a swoimi odwrotnościami. Załóżmy, że wśród tych liczb s _{}a dwie które nie s _{}a ani swoimi odwrotnościami ani nie s _{}a równe, bez szkody na ogólnoŚci s _{}a to a i b. Wówczas z tego, co właśnie powiedziliśmy c i d s _{}a zarówno swoimi odwrotnościami jak i s _{}a równe, wi_{}ec c = \frac{1}{c}, czyli c^{2} = 1, czyli c i d s _{}a albo jedynkami albo minus jedynkami. Załórmy, że jedynkami. wówczas mamy równania a+b = 2 i ab = 1, czyli a jest odwrotności _{}a b, czyli mamy sprzeczność z założeniem o nie byciu swoj _{}a odwrotności _{}a a i b. Załóżmy, że minus jedynkami. Wówczas mamy równania a + b = 2 i ab = −3. Wi_{}ec b = −\frac{3}{a} i wstawiaj _{}ac to do pierwszego mamy, że a − \frac{3}{a} = 2, czyli a^{2} − 2a − 3 = 0 (bo a ≠ 0), czyli (a + 1)(a − 3) = 0. Zatem rozwi _{}azaniami tutaj s _{}a a, b równe 3 i −1, wi_{}ec czwórk _{}a spełniaj _{}ac _{}a ż _{}adane warunki s _{}a trzy −1 i 3. Teraz załóżmy, że dla każdej pary liczb z a, b, c, d liczby w parze s _{}a równe lub s _{}a swoimi odwrotnościami. Wówczas wszystkie te liczby s _{}a albo równe a albo s _{}a odwrotnościami a. Załóżmy najpierw, że wszystkie s _{}a równe a, wi_{}ec mamy równanie a^{3}+a = 2, czyli a^{3}+a−2 = 0, czyli (a − 1)(a^{2} + a + 2) = 0. Zauważmy, że a^{2} + a + 2 = (a + \frac{1}{2})^{2} + \frac{7}{4} > 0, wi_{}ec iloczyn może być równy 0 tylko gdy a jest równe 1. Mamy wi_{}ec rozwi _{}azanie w postaci czterech jedynek. Teraz załóżmy, że trzy z liczb s _{}a równe a zaś jednak \frac{1}{a}. Mamy wi_{}ec równania: a + a^{2} · \frac{1}{a} = 2, wi_{}ec a = 1 i mamy znów to samo rozwi _{}azanie. Teraz załóżmy, że dwie z liczb s _{}a równe a zaś dwie \frac{1}{a}. Wówczas mamy równanie a + \frac{1}{a} = 2, czyli a^{2} − 2a + 1 = 0, czyli (a − 1)^{2} = 0, czyli znów mamy rozwi _{}azanie w postaci czterech jedynek. I ostatni przypadek, gdy jest jedno a i trzy \frac{1}{a}, mamy \frac{1}{a} + \frac{1}{a} = 2, czyli znów a = 1. Zatem rozważywszy wszystkie przypadki mamy dwie czwórki: trzy (−1) i 3 oraz same 1.

2. (by Maciej Zdanowicz)

Zauważmy, że z tw. Ptolemeusza w czworok _{}acie BCEA zachodzi nierówność BC ·AE +AB · CE ⩾ BE · AC, która korzystaj _{}ac z założeń o bokach sześciok _{}ata jest równoważna nierówności \frac{AB}{BE} ⩾ \frac{AC}{AE+CE} . Zapisuj _{}ac analogiczne nierówności dla czworok _{}atów CDEA,EF AC i dodaj _{}ac je stronami otrzymujemy:

\frac{AB}{BE} + \frac{CD}{DA} + \frac{EF}{F C} ⩾ \frac{AC}{AE + CE} + \frac{CE}{AC + AE} + \frac{AE}{AC + CE}

Po przyj_{}eciu oznaczeń x = AC,y = AE,z = CE, mamy pokazać, że:

\frac{x}{y + z} + \frac{y}{x + z} + \frac{z}{x + y} ⩾ \frac{3}{2}

Dowód tej nierówności jest już prosty, chociażby przez domnożenie stronami przez x(y + z) + y(x + z) + z(x + y) i zastosowanie nierówności Schwarza.

3. (by Chuck Norris)

(w całym rozwi _{}azaniu g jest BARDZO BARDZO DUŻE) Oznaczmy a = p_{1}^{s_{1}} p_{2}^{s_{2}} …p_{g}^{s_{g}} oraz b = p_{1}^{t_{1}}p_{2}^{t_{2}} …p_{g}^{t_{g}}. Wówczas w naszym równaniu współczynniki przy p_{i} obu stron musz _{}a być równe dla każdego i, wi_{}ec zachodzi dla każdego i:

s_{i} · b = t_{i} · ka

Czyli:

\frac{s_{i}}{t_{i}} = \frac{ka}{b}

Oznaczmy \frac{ka}{b} = \frac{p}{q}, gdzie p⊥q. Wówczas istnieje taka liczba c = p_{1}^{u_{1}}p_{2}^{u_{2}} …p_{g}^{u_{g}}, że a = c^{p} i b = c^{q} - bo po prostu dla każdego i u_{i} = NW D(s_{i}, t_{i}), zaś jako, że stosunek s_{i} i t_{i} jest stały równy \frac{p}{q} to po przemnożeniu u_{i} przez p i q uzyskamy odpowiednio s_{i} i t_{i}. Teraz b_{}edziemy poszukiwali jedynie rozwi _{}azań w których p = 1. Wówczas mamy, że:

\frac{1}{q} = k · \frac{p_{1}^{u_{1}}p_{2}^{u_{2}} …p_{g}^{u_{g}}}{p_{1}^{qu_{1}}p_{2}^{qu_{2}} …p_{g}^{qu_{g}}}

k = \frac{p_{1}^{(q−1)u_{1}} p_{2}^{(q−1)u_{2}} …p_{g}^{(q−1)u_{g}}}{q}

k = \frac{(p_{1}^{u_{1}}p_{2}^{u_{2}} …p_{g}^{u_{g}})^{q−1}}{q}

Musimy pokazać, że istnieje k dla którego to równanie ma dowolnie dużo rozwi _{}azań - wówczas z tych rozwi _{}azań da si_{}e wyprowadzić liczby a i b, które spełniaj _{}a warunki zadania. Niech teraz k = p_{1}^{r_{1}}p_{2}^{r_{2}} …p_{g}^{r_{g}} i chcemy znaleźć współczynniki r_{i}. B_{}edziemy rozpatrywali jedynie rozwi _{}azania w których q −1 jest pierwsze. Niech zbiór q_{1}, q_{2}, …, q_{N} gdzie N jest bardzo duże b_{}edzie zbiorem takich różnych q_{i}, że q_{i} − 1 jest pierwsze. Teraz chcemy znaleźć takie współczynniki r_{i}, aby kq_{i} było q_{i}-t _{}a pot_{}eg _{}a liczby naturalnej - wtedy znajdziemy k maj _{}ace dowolnie dużo rozwi _{}azań równania k = \frac{(p_{1}^{u_{1}} p_{2}^{u_{2}} ...p_{g}^{ug} )^{q−1}}{q} . Niech rozkładem na czynniki pierwsze q_{i} b_{}edzie q_{i} = p_{1}^{f_{1}} p_{2}^{f_{2}} …p_{g}^{f_{g}} . Wówczas współczynniki r_{i} musz _{}a spełniać kongruencje r_{j} +f_{j} ≡ 0(mod(q_{i}−1)) dla każdego j-ta. Zapisuj _{}ac taki układ kongruencji dla każdego i uzyskujemy dla każdego współczynnika r_{j} układ N kongruencji opisuj _{}acych jego zachowanie modulo kolejne q_{i} − 1. A ponieważ założyliśmy, że q_{i} − 1 s _{}a pierwsze, a wi_{}ec parami wzgl_{}ednie pierwsze, z Chińskiego Twierdzenia o Resztach możemy zawsze dobrać w odpowiednim przedziale takie r_{j}, wi_{}ec możemy znaleźć k, dla którego równanie k = \frac{(p_{1}^{u_{1}} p_{2}^{u_{2}} ...p_{g}^{ug} )^{q−1}}{q} ma N różnych rozwi _{}azań. Cofaj _{}ac si_{}e do zmiennych a, b z równań wynika, że w ten sposób uzyskujemy N różnych rozwi _{}azań równania danego w zadaniu, wi_{}ec mog_{}e dobrać takie k, aby było ich co najmniej 2005.

4. (by Maciej Zdanowicz)

Z łatwości _{}a zauważamy, że wszystkie wielomiany postaci P (x) = x^{n} i wielomian zerowy spełniaj _{}a warunki zadania. Załóżmy w takim w takim razie, że P (x) nie jest równe c · x^{n}, czyli ma pierwiastek zespolony ϵ o module wi_{}ekszym od 0. Niech ϵ ma najwi_{}ekszy moduł spośród pierwiastków P. Z danej w zadaniu równości, przepisanej dla y = x − 1, otrzymujemy:

P (y)P (y + 2) = P (y(y + 2))

Z równości wyjściowej przepisanej dla y = x + 1 dostajemy za to:

P (y − 2)P (y) = P (y(y − 2))

Z powyższych dwóch nierówności wnioskujemy, że jeśli α jest pierwistkiem P to jest nim również α(α−2) oraz α(α+2). Stosuj _{}ac poprzednie wnioski dla α = ϵ wiemy, że liczby ϵ(ϵ−2) i ϵ(ϵ+2) s _{}a pierwiastkami P. Jednak rysuj _{}ac okr _{}ag liczb o module ϵ zauważamy, że ktoraś z nich ma moduł wi_{}ekszy. Co jest sprzeczne z definicj _{}a ϵ. W zwi _{}azku z tym jedynymi wielomianami spełniaj _{}acymi warunki zadania mog _{}a być wielomiany P (x) = c · x^{n}. Wówczas wstawiaj _{}ac do pocz _{}atkowego wzoru c·(x−1)^{n} ·c·(x+1)^{n} = c·(x^{2}−1)^{n}, czyli dla każdego x zachodzi c^{2}(x^{2}−1)^{n} = c(x^{2}−1)^{n}, wi_{}ec c = 0 lub c = 1 co daje nam rozwi _{}azanie w postaci wielomianu zerowego i wielomianów postaci x^{n}.

5. (by Chuck Norris)

Lemat.1. Jeśli A = x+y oraz 0 < A < π to dla każdej liczby rzeczywistej k istnieje rozwi _{}azanie równania k = \frac{sin x}{sin y}, to istnieje ono co najwyżej jedno. Dowód: Wystarczy pokazać, że funkcja f(x) = \frac{sin x}{sin A−x} jest różnowartościowa, wi_{}ec wystarczy pokazać, że jest rosn _{}aca. Zauważmy, że:

f′(x) = \frac{cosx sin(A − x) + sinx cos(A − x)}{sin^{2}(A − x)} = \frac{sinA}{sin^{2}(A − x)}

Zatem pochodna jest dodatnia, wi_{}ec funkcja różnowartościowa c.k.d.l.

Dowód zadania: Oznaczmy ∠BAD = ∠DAC = α i ∠F ED = ∠CED = β. Zauważmy, że z k _{}atów przyległych ∠AEF = π − 2β, z sumy miar k _{}atów w trójk _{}acie ∠AF E = 2β − 2α i z k _{}ata zewn_{}etrznego ∠ADE = β − α. Zatem używaj _{}ac twierdzenia sinusów w trójk _{}atach AEF i AED mamy, że

F E = AE·\frac{sin2α}{sin(2β − 2α)} = ED\frac{sin(β − α)}{sinα} ·\frac{sin2α}{sin(2β − 2α)} = ED\frac{cosα}{cos(β − α)} = ED\frac{sin(\frac{π}{2} − α)}{sin(\frac{π}{2} − β + α)}

Wi_{}ec z tw. sinusów dla trójk _{}ata F ED:

\frac{sin∠EDF}{sin∠EF D} = \frac{F E}{ED} = \frac{sin(\frac{π}{2} − α)}{sin(\frac{π}{2} − β + α)}

Zauważmy zaś, że z sumy miar k _{}atów w trójk _{}acie mamy, że ∠EDF + ∠EF D = π − β zaś \frac{π}{2} − α + \frac{π}{2} − β + α = π − β także. Zatem k _{}aty \frac{π}{2} − α i \frac{π}{2} − β + α s _{}a rozwi _{}azaniem równania \frac{sin ∠EDF}{sin ∠EF D} = \frac{F E}{ED} = k, wi_{}ec z lematu wynika, że jedynym możliwym. Zatem ∠EDF = \frac{π}{2} − α, zatem ∠EDB = α c.n.d.

6. (by Chuck Norris)

Niech wiersze i kolumny b_{}ed _{}a odpowiednio prostymi równoległymi do osi OX i OY o przechodz _{}acymi przez punkty kratowe. W rozwi _{}azaniu b_{}edziemy rozważali tylko te wiersze i kolumny w których wyst_{}epuj _{}a miejsca do posadzenia kwiatków, oczywiście jest ich skończenie wiele. Teraz dodajmy jeszcze jeden wiersz i jedn _{}a kolumn_{}e i nazwijmy je superwierszem i superkolumn _{}a. W tych super b_{}ed _{}a miejsca na kwiatki w tych miejscach w których te super przecinaj _{}a si_{}e z odpowiednio kolumnami i wierszami o nieparzystej liczbie miejsc na kwiatki. Dodatkowo na przeci_{}eciu superwiersza i superkolumny umieszcazmy miejsce na kwiatka tak lub nie w taki sposób, aby liczba miejsc w superrz_{}edach była parzysta - możemy tak zawsze zrobić, bo parzystość liczby kwiatków w superwierszu i superkolumnie jest równa parzystości liczby wszystkich innychmiejsc na kwiatki, wi_{}ec przed dodaniem parzystość tych liczb jest taka sama, wi_{}ec dodajemy jedno miejsce tylko jeśli jest nieparzysta. Zauważmy, że w nowym układzie punktów w każdym wierszu i w każdej kolumnie jest parzyście wiele miejsc na kwiatki, wi_{}ec teraz pokażemy, że da si_{}e tak usadowić kwiatki, aby liczby goździków i róż w każdym wierszu i w każdej kolumnie była takie same. Nast_{}epnie w czasie powrotu z tego układu do pocz _{}atkowego z każdego wiersza i z każdej kolumny wyrzuc_{}e co najwyżej jednego kwiatka, wi_{}ec na każdej prostej liczba goździków i róż b_{}edzie si_{}e różniła co najwyżej o 1. Zatem do dzieła: Niech interesuj _{}acych wierszy b_{}edzie n zaś kolumn m. Skonstruujmy wi_{}ec macierz m × n w której na danym polu o współrz_{}ednych i, j b_{}edzie 1, jeśli na skrzyżowaniu i-tej kolumny i j-ego wiersza jest miejsce na kwiatka, 0 w przeciwnym razie. Skonstruujmy teraz graf dwudzielny w którym po jednej stronie jest m wierzcholków reprezentuj _{}acych kolumny, po drugiej n reprezentuj _{}acych wiersze, zaś poł _{}aczenie wierzchołków kraw_{}edzi _{}a oznacza, że na przeci_{}eciu odpowiedniego wiersza i kolumny jest 1, czyli miejsce na kwiatka. Teraz nasza teza sprowadza si_{}e do przyporz _{}adkowania kraw_{}edziom kwiatków tak, aby dla każdego wierzchołka liczba wychodz _{}acych kraw_{}edzi ’goździkowych’ była równa liczbie ’różanych’ zaś wiemy, że stopień każdego wierzchołka jest parzysty. Robimy to nast_{}epuj _{}aco: bierzemy jakikolwiek wierzchołek po lewej stronie i przechodzimy jak _{}aś kraw_{}edzi _{}a na prawo, nast_{}epnie spowrotem na lewo inn _{}a itd. kolejno oznaczaj _{}ac na przemian kraw_{}edzie jako ’goździkowe’ i ’różane’. W momencie dojścia do wierzchołka z którego zacz_{}eliśmy zamykamy cykl (który ma parzyst _{}a długość) i wyrzucamy go z grafu. Post_{}epujemy tak aż w grafie nie b_{}edzie kraw_{}edzi. Zauważmy, że do każdego wierzchołka jeśli wchodzimy to od razu wychodzimy, wi_{}ec liczba wyrzuconych kraw_{}edzi każdego wierzchołka zawse jest parzysta, wi_{}ec parzystość stopni wierzchołków si_{}e nie zmienia. Jednocześnie z tego samego powodu zawsze możemy z wierzchołka wyjść, wi_{}ec nasze tworzenie cyklu zawsze si_{}e skończy (najwyżej wykorzystamy wszystkie kraw_{}edzie). Także wśród wyrzucancyh kraw_{}edzi dokładnie połowa jest ’goździkowa’ a połowa ’różana’ (bo wchodzimy jedn _{}a a wychodzimy drug _{}a), wi_{}ec po zakoćzeniu całej procedury uzyskamy takie dopasowanie kwiatów do kraw_{}edzi o jakie nam chodziło, wi_{}ec cofaj _{}ac to rozumowanie Hofman może odpowiednio posadzić swoje kwiatki.