Zad. 1. A1, A2, ..., An są punktami okręgu. Na ile sposobów można pokolorować te punkty p kolorami ([tex]p\ge 2[/tex]) tak, żeby każde dwa sąsiednie miały różne kolory?
Zad. 2. Niech [tex]m,n\ge 2[/tex] będą liczbami naturalnymi. Policz, ile jest wielomianów stopnia 2n–1 o parami różnych współczynnikach ze zbioru {1, 2, ..., m}, podzielnych przez wielomian
xn–1 + xn–2 + ... + 1.
Zad. 3. Okręgi o promieniach r i R są styczne do prostej l odpowiednio w punktach A i B. Okręgi te przecinają się w punktach C i D. Wykaż, że długość promienia okręgu opisanego na trójącie ABC nie zależy od długości odcinka AB.
W tym miesiącu punkty zdobyli:
- 20 - Radosław Górzyński (I LO Lubin),
- 4 - Miłosz Zajdel (I LO Krosno).
Zad. 1. Oznaczmy szukaną wartość przez an. Widać, że a2 = p(p–1) oraz a3 = p(p–1)(p–2). Żeby obliczyć an+1, podzielmy kolorowania A1, A2, ..., An+1 na dwa rodzaje. Pierwszym będą kolorowania, w których A1 i An mają różne kolory. Takich kolorowań jest (p–2)an, bo najpierw kolorujemy na an sposobów punkty A1, ..., An leżące na okręgu, a następnie wybieramy kolor An+1 na p–2 sposoby. Drugim rodzajem są kolorowania, w których A1 i An mają ten sam kolor. Analogicznie pokazujemy, że jest ich (p–1)an–1. W ten sposób otrzymaliśmy zależność rekurencyjną an+1 = (p–2)an + (p–1)an-1 prawdziwą dla [tex]n\ge 3[/tex]. Z niej wynika z kolei, że an+1 + an = (p–1)(an + an–1) = ... = (p–1)n–2(a2+a3) = p(p–1)n. Ta ostatnia tożsamość pozwala łatwo sprawdzić, że an = (p–1)n + (-1)n(p–1).
Zad. 2. Niech P(x) = a2n–1x2n–1 + a2n–2x2n–2 + ... + a0 będzie wielomianem o żądanych własnościach. Warunek [tex]x^{n-1} + x^{n-2} + ... + 1 \vert P(x)[/tex] jest równoważny warunkowi [tex]x^n-1\vert (x-1)P(x)[/tex], gdzie (x–1)P(x) = a2n–1x2n + (a2n–2 – a2n–1)x2n–1 + (a2n–3 – a2n–2)x2n–2 + ... + (a0 – a1)x – a0. Zauważmy, że [tex]x^n - 1\vert x^{n+i} - x^i[/tex] dla [tex]i\ge 0[/tex], więc warunek [tex]x^n - 1\vert (x-1)P(x)[/tex] jest równoważny warunkowi [tex]x^n - 1\vert (a_{2n-2} - a_{2n-1} + a_{n-2} - a_{n-1})x^{n-1} + ... + (a_n - a_{n+1} + a_0 - a_1)x + (a_{2n-1} - a_0 + a_{n-1} + a_n)[/tex]. Ten wielomian ma stopień niższy od stopnia wielomianu, przez który dzielimy, więc musi być wielomianem zerowym. W takim razie a2n–1+an–1 = a2n–2 + an–2 = ... = an+a0 = k dla pewnej liczby naturalnej k. W takim razie wielomianów o szukanych własnościach jest [tex] \sum_{k=0}^{\infty} A_k [/tex], gdzie Ak jest liczbą krotek (b0, b1, ..., b2n–1), w których b0 + bn = b1 + bn+1 = ... = bn–1 + b2n–1 = k oraz bi są parami różnymi liczbami ze zbioru {1, 2, ..., m}. Żeby liczba Ak była niezerowa, k musi spełniać oszacowanie [tex]\frac{1+2+...+2n}{n}=2n+1\le k \le 2m -2n +1[/tex]. Zauważmy, że min(b0, bn), min(b1, bn+1), ..., min(bn–1, b2n–1) są parami różnymi liczbami z przedziału [tex]1,2,...,\lceil\frac{k-1}{2}\rceil[/tex]. Jeżeli [tex]k\le m + 1[/tex], to [tex]A_k={\lceil\frac{k-1}{2}\rceil \choose n}2^nn![/tex], a jeżeli k > m+1, to [tex]A(k)= {\lceil \frac{2m -k}{2}\rceil \choose n} 2^nn![/tex].
Zad. 3. Bez straty ogólności r < R. Oznaczmy środki okręgów o promieniach r i R odpowiednio przez O1 i O2. Oznaczmy |O1O2| = d. Poprowadźmy prostą równoległą do l przez O1. Powstanie wtedy trójkąt prostokątny o przyprostokątnych długości |AB| i R–r oraz przeciwprostokątnej długości d, więc d2 = |AB|2 + (R–r)2. Z drugiej strony [tex]\angle ACB = (\frac{\pi}{2} - \angle CBA) + (\frac{\pi}{2} - \angle BAC) = \angle O_1AC + \angle O_2BC[/tex]. To oznacza, że [tex]\angle O_1CO_2 = 2\pi - 2\angle ACB[/tex], więc [tex]\cos(\angle O_1CO_2)=\cos(2\angle ACB)=1 - 2\sin^2(\angle ACB)[/tex]. Z twierdzenia sinusów długość promienia okręgu opisanego na trójkącie ABC jest równa [tex]\frac{|AB|}{2\sin(\angle ACB)}[/tex], a z twierdzenia kosinusów [tex]\cos(\angle O_1CO_2) = \frac{R^2 + r^2 - d^2}{2rR}[/tex], więc [tex]{\left( \frac{AB}{\sin(\angle ACB)}\right)}^2 = (d^2 - (R-r)^2)\left( \frac{1- \frac{R^2 + r^2 - d^2}{2rR}}{2}\right)^{-1}= 4rR[/tex]. To oznacza, że promień okręgu opisanego na trójkącie ABC jest równy [tex]\sqrt{rR}[/tex].
