Zadání XXXI. ročníku

Stačí nám ukázat, že jedna z permutací dá polynom, který má dva reálné kořeny. Vybereme si tu, kde vedoucí koeficient je \(1\) a koeficient u linárního členu je větší než absolutní člen. Máme tedy polynom \(1x^2+bx+c; b>c\).

To, že má dva reálné kořeny, je ekvivalentní tomu, že jeho diskriminant \(b^2-4c\) je kladný. To tedy musíme dokázat.

Jelikož \(b>c\) a protože jsou obě přirozená, platí \(b\ge c+1\). Odtud \(b^2-4c \ge (c+1)^2-4c = c^2 - 2c + 1 = (c-1)^2\). Ze zadání víme, že \(c\) je větší než \(1\), takže \((c-1)^2 >0\), a tedy i diskriminant \(b^2-4c\) je kladný.

Ukázali jsme, že existuje permutace koeficientů taková, že diskriminant bude kladný a Permutoníkův polynom bude mít dva reálné kořeny.

Úloha nebyla složitá a většina si s ní poradila moc dobře. Nejčastěji jste postupovali jako ve vzorovém řešení nebo jste nerovnost dokázali rozdělením na více případů. Když upravujete rovnice a nerovnice, nemusíte psát moc slovních komentářů, ale je potřeba rozlišovat, co víte a co se snažíte dokázat. Často se stávalo, že se v řešeních objevily pouze rovnosti a nerovnosti s šipkami od jedné k druhé a musela jsem dešifrovat, co za úpravy provádíte. Dohromady ale moc dobrá práce!

Vzorové řešení bylo převzato od Jany Fisherové Hledáme kořen, tedy \(x\), pro které platí:

\[4x^2+ax-a=0\]

Předpokládejme, že \(x\neq 1\)

\[a=\frac{4x^2}{1-x}\]

Zlomek napravo musí být celé číslo, tudíž \(1-x\) musí dělit \(4x^2\). Víme, že \(x-1\) a \(x\) jsou neosudělná čísla, tudíž \(1-x\) dělí \(4\). To znamená, že \(x\) může být pouze: -3, -1, 0, 2, 3, 5. Pro tyto hodnoty najdeme \(a\), pro které jsou tyto čísla kořeny: 9, 2, 0, -16, -18, -25

Nyní stačí akorát prověřit, že 1 nemůže být kořen: \(4+a-a=4\neq 0\)

Tudíž kořeny jsou právě \(-3, -1, 0, 2, 3, 5\)

Obávám se, že jsme neodhadli obtížnost úlohy. Ač existuje velice jednoduché řešení, je pro polynomiální úlohy poměrně netypické. Spousta zkušených řešitelů se nachytalo na to, že pro polynomy, kde vedoucí člen není 1, tak nemusí platit, že když je jeden kořen celočíselný, musí být i druhý. Někteří sice došli ke správnému výsledku, ale jen pár našlo to jednoduché řešení. Kde bohužel spousta z nich zapomělo ověřit, zda je 1 kořenem.

Hledáme polynom šestého stupně: \(P(x) = a_6x^6+a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x^1+a_0\). Takový polynom musí být záporně reciproký, tedy rovnou víme: \[\begin{aligned} a_6 &= -a_0 = 1 \\ a_5 &= -a_1 \\ a_4 &= -a_2 \\ a_3 &= -a_3 = 0\end{aligned}\] Protože polynom má být normovaný, rovnou víme, že \(a_6=1\) a \(a_0 = -1\), zároveň člen \(a_3=0\). To už víme spoustu věcí! Pojďme si to ale ještě přepsat do trochu víc uživatelsky příjemného tvaru, ať v tom něco vidíme: \(P(x) = x^6 + bx^5 + cx^4 - cx^2 - bx^1 + 1\). Zadá-li vám někdo polynom, můžete zkusit předpokládat, že takový člověk byl hodný a dal vám pěkné kořeny. Navíc u reciprokých polynomů, které jsou krásně symetrické je běžná praxe vyzkoušet, jestli nemá kořeny \(\pm 1\). Existují na to pravidla, podle toho jestli je záporně, nebo kladně reciproký, není ale potřeba si to pamatovat, prostě to vyzkoušejte. \[\begin{aligned} P(1) &= 1^6 + b1^5 + c1^4 - c1^2 - b1^1 + 1 = 0 \\ P(-1) &= (-1)^6 + b(-1)^5 + c(-1)^4 - c(-1)^2 - b(-1)^1 + 1 = 0 \end{aligned}\] Tak máme hned dva kořeny z maximálního počtu šesti kořenů. Můžou být tyto kořeny těmi dvojnásobnými? Jejich součet je nula, ne -4, tedy odpověď zní ne. To je ale dobře, protože teď víme, že máme mít čtyři kořeny, z čehož dva jsou dvojnásobné. Navíc při reciprokých polynomech platí krásná věc, že je-li \(\alpha\) kořenem, pak je kořenem i \(\frac{1}{\alpha}\). Hledejme tedy dvojnásobný kořen \(\alpha\) a dvojnásobný kořen \(1/\alpha\). \[\begin{aligned} \alpha+\frac{1}{\alpha} &= -4 \\ \alpha^2 + 1 &= -4\alpha \\ \alpha^2 + 4\alpha + 1 &= 0\\ \alpha_{1,2} &= \frac{4 \pm \sqrt{16-4\cdot1\cdot1}}{2} = 2 \pm \sqrt{3}\end{aligned}\]

Poznamenejme jen, že kvadratický polynom jehož řešením jsou převrácená čísla je také reciproký, a že skutečně platí \(2 + \sqrt{3} = \frac{1}{2-\sqrt{3}}\).

Když už známe všechny kořeny, není nic jednoduššího než mezi sebou roznásobit kořenové závorky a zpětně získat celý polynom! \[P(x) = (x-1)(x+1)(x-2-\sqrt{3})^2(x-2+\sqrt{3})^2 = (x-1)^2(x^2 - 4x+ 1)^2 = x^6+8x^5+17x^4-17x^2-8x-1\]

Řešení, která došla se vesměs dostala alespoň do nějakého bodu řešení - ať už jste přišli na kořeny \(\pm 1\) nebo vyřešili kvadratický polynom a našli dvojnásobné kořeny. SpoustSpousta z vás ale označiloznačila za násobné kořeny \(1\) a \(-1\), jejich součet ale není \(-4\). Stejně ale super práce!!

Pro část 1. ukážeme, že vyhovuje polynom tvaru \(f(x)=-x^n-x^{n-1}\). Pro \(n=1\) dostaneme polynom \(-x-1\), který má všechny koeficienty \(-1\). \(-1\) je zároveň kořen tohoto polynomu, tedy se zobrazením \(F\) pošle na nulu. Pro vyšší \(n\) je \(-1\) opět kořenem polynomu, neboť \(-x^n-x^{n-1}=x^{n-1}(-x-1)\). Zároveň bude zřejmě jeden z kořenů \(0\), proto \(f\) zobrazí koeficienty \(-1\) i \(0\) zobrazí na nulu. Jiné koeficienty nemáme :).

Druhá část je speciální případ části 3 pro \(k=1\).

Pro poslední část uvažujme pro libovolné \(n\) polynom tvaru \(g(x)=k^{\frac{1}{n}}x^n\). Jeho koeficienty jsou pouze \(0\) a \(k^{\frac{1}{n}}\). \(f(0)=0\), \(f(k^{\frac{1}{n}})=k\cdot k^{\frac{1}{n}}\). Vidíme, že každý koeficient se zobrazí na \(k\) násobek původního, tedy \(F(g)=kg\). Odtut tedy i druhá část má řešení \(g(x)=x^n\).

Všichni jste se s tím poprali skvěle, úloha byla velmi jednoduchá. Občas vám unikla nějaká drobnost, třeba, že váš polynom není polynom, pokud \(n=1\).

Chválím ty, kteří zvládli řešení sepsat korektně, srozumitelně, jasně a stručně. Ne vždy platí, že čím víc toho napíšete, tím je to lepší.

Pro vzorové řešení jsem se rozhodla využít řešení Toma Pazourka:

Pro obvod celé menší kružnice platí \(2\pi r_1=a+\alpha r_1\). Zřejmě platí \(\alpha=\frac{\alpha r_1}{r_1}=\frac{|obloukBC|}{|BS|}\) a nyní z podobnosti dvou výsečí BSC a ESD dostáváme \(\alpha=\frac{|obloukED|}{|ES|}=\frac{a}{a+r_1}\). Náš nově vyjádřený úhel \(\alpha\) teď dosadíme do první rovnice a upravíme:

\(2\pi r_1=a+\frac{ar_1}{a+r_1}\).

\(2\pi r_1(a+r_1)=a(a+r_1)+ar_1\).

\(2\pi r_1a+2\pi r_1^2=a^2+ar_1+ar_1\)

\(a^2+(2-2\pi)ar_1-2\pi r_1^2=0\)

Rovnost vydělíme číslem \(r_1^2\) a zavedeme substituci, kde si náš hledaný poměr označíme jako \(x\), tzn. \(x=\frac{a}{r_1}\). Dostáváme:

\(x^2+(2-2\pi)x-2\pi=0\).

Když nyní vyřešíme tuto kvadratickou rovnici, vyjde nám, že

\(x_{1,2}=\frac{-(2-2\pi)\pm\sqrt{4(1-\pi)^2+8\pi}}{2}=\pi-1\pm\sqrt{\pi^2+1}\).

Vzhledem k tomu, že poměr dvou délek musí být nezáporné číslo, dostáváme jediné řešení \(x=\frac{a}{r_1}=\pi-1+\sqrt{\pi^2+1}\).

U této úlohy nastaly v podstatě jen dva případy. Buďto jste ji vyřešili naprosto správně, nebo jste ji nedořešili. Jak můžete vidět ve vzorovém řešení, řešením této úlohy bylo konkrétní číslo, protože náš pseudočtverec má vždy stejný úhel \(\alpha\) a tímpádem i konstantní poměr \(\frac{a}{r_1}\).

Nejprve si všimněme, že koně i střelec ohrožují vždy pole pouze jedné barvy, přičemž kůň jich ohrozí nejvýše osm a střelec třináct. Nechť BÚNO střelec ohrožuje černá pole. Pak zbývá ještě \(32-13=19\) neohrožených černých polí, na jejichž pokrytí budou zapotřebí alespoň tři koně. Na bílá pole tak zbývají čtyři koně. Je však zapotřebí pokrýt i dvě rohová bílá pole. Koně ohrožující tato pole zvládnou pokrýt právě šest polí celkem, všichni čtyři jezdci tak ohrozí nanejvýš \(2 \times 8 + 2 \times 6 = 30\) polí, což nestačí na pokrytí všech bílých polí. Tím jsme ukázali, že zadání nelze splnit.

Historicky první úloha co opravuju co měli všichni bezchybně. Potěšili jste mě, i já vás potěším.

Hledáme podíl počtu všech vyplnění testu, za něž po zaškrtnutí šestnácti odpovědí získáme 16 bodů, a všech možných vyplnění testu při zaškrtnutí šestnácti odpovědí. Všech možných vyplnění testu při zaškrtnutí 16 otázek je \(\binom{64}{16}\). Zbývá tedy zjistit počet všech vyplnění testu, za něž po zaškrtnutí šestnácti odpovědí získáme 16 bodů.

Za každou otázku můžeme získat buď 3, 0, nebo -1 bod. Hledáme čísla, která splňují následující soustavu rovnic: \(3s+0n-ch=16\) (počet získaných bodů je 16) \(s+n+ch=16\) (počet otázek je 16)

Neznámé \(s\), \(n\) a \(ch\) značí po řadě počty správných, nevalidních a chybných odpovědí a všechna patří do přirozených čísel s nulou. Tato soustava má tři možná řešení:

i - (s,n,ch)= (8,0,8)

ii - (s,n,ch)= (7,4,5)

iii - (s,n,ch)= (6,8,2)

Všechny tyto tři případy si postupně rozebereme. Chceme pro každou z těchto možností zjistit počet možných vyplnění testu:

i - Járo odpověděl osmkrát správně a osmkrát špatně. Otázky, na které Járo odpověděl správně vybereme \(\binom{16}{8}\) způsoby. Pro tyto otázky pak máme jasně dané, kterou odpověď musel Járo zaškrtnout - tu správnou. Na zbylé otázky musel Járo odpovědět chybně. Musel tedy u každé takové otázky vybrat jednu ze tří špatných odpovědí, kterou zaškrtl. To mohl udělat \(3^8\) způsoby. (Měl u osmi otázek tři možnosti.) Celkově měl tedy \(\binom{16}{8}*3^8\) možností.

ii - Járo odpověděl sedmkrát správně, pětkrát špatně a čtyřikrát nevalidně. Otázky, na které Járo odpověděl správně vybereme \(\binom{16}{7}\) způsoby. U těchto otázek musel vybrat jedinou správnou odpověď. Otázky, na které odpověděl Járo chybně vybereme \(\binom{9}{5}\) způsoby. (Vybíráme pětiprvkové podmnožiny z devítiprvkové množiny otázek, na které neodpověděl Járo správně.) Podobně jako u předchozího případu zaškrtnuté odpovědi u těchto otázek vybereme \(3^5\) způsoby. Zbývá určit počet možností, jak mohl Járo odpovědět na zbylé čtyři otázky, jejichž odpověď měla být nevalidní. U každé otázky mohl vybrat buď 0,2,3, nebo 4 odpovědi. (Kdyby vybral jednu, počítala by se tato otázka do správně nebo chybně zodpovězených otázek.) Járovi zbývají ještě čtyři zaškrtnutí. Má dvě možnosti: Buď u jedné ze čtyř otázek odpoví zaškrtnutím všech odpovědí (vybíráme jednu ze čtyř otázek) a ostatní odpovědi nechá prázdné, nebo odpoví na dvě otázky dvěma odpověďmi a zbylé odpovědi nechá nezaškrtnuté (vybíráme dvě odpovědi ze čtyř a pak máme u každé odpovědi 6 možností, jak vybrat dvě odpovědi ze čtyř). To odpovídá \(\binom{16}{7}*\binom{9}{5}*3^5*(\binom{4}{1}+\binom{4}{2}*6^2)\).

iii - Járo odpověděl šestkrát správně, dvakrát špatně a osmkrát nevalidně. Otázky, na které odpověděl správně, vybereme \(\binom{16}{6}\) způsoby. Opět mohl vybrat pouze jedinou odpověď. Otázky, na které odpověděl Járo chybně vybereme \(\binom{10}{2}\) způsoby. Chybné odpovědi vybírá, podobně jako v předchozích případech, \(3^2\) způsoby. Teď zbývá rozebrat počet různých možných nevalidních zodpovězení. Potřebujeme mít osm nevalidně zodpovězených otázek a to osmi odpověďmi. Máme čtyři možnosti, jak toho dosáhnout: a) 4 a 4 odpovědi, b) 4, 2 a 2 odpovědi c) 3, 3 a 2 odpovědi d) 2, 2, 2 a 2 odpovědi. Odpovídá to celkově \(\binom{16}{6}\binom{10}{2}*3^2*(\binom{8}{2}+\binom{8}{2}*6^2*\binom{6}{1}+\binom{8}{2}*4^2*\binom{6}{1}*6+\binom{8}{4}*6^4)\).

Nakonec všechny případy sečteme a podělíme \(\binom{64}{16}\):

\[\frac{\binom{16}{8}*3^8+\binom{16}{7}*\binom{9}{5}*3^5*(\binom{4}{1}+\binom{4}{2}*6^2)+\binom{16}{6}\binom{10}{2}*3^2*(\binom{8}{2}+\binom{8}{2}*6^2*\binom{6}{1}+\binom{8}{2}*4^2*\binom{6}{1}*6+\binom{8}{4}*6^4)}{\binom{64}{16}}\]

Což když vyčíslíme je přibližně \(0,0009076\), tedy \(0,09076 \%\).

Úloha nebyla početně až tak složitá, pokud znáte aspoň nějaký základy kombinatoriky a kombinační čísla. Řešení ale vyžadovalo opravdu systematický a přehledný přístup. Bylo opravdu snadné něco přehlídnout a jenom dvoum z vás se podařilo úlohu vyřešit zcela správně. Tímto gratuluji Viktorovi Golovi a Andreji Mackovi! Skvělá práce! U ostatních se často objevily potíže hned u porozumění zadání. Nějaký body jsem dala i tak, pokud tam byla aspoň nějaká správná myšlenka, ale nemohla jsem jich dát moc, když jste pak řešili často mnohem jednodušší úlohu, než jaká byla zadaná. No ale musím vás pochválit, protože i když tam byly nějaký chyby, tak řešení byla většinou napsaná hezky přehledně:-)

Nejprve dokážeme, že \(n-3\) bodů nestačí. Mějme libovolnou triangulaci \(n\)-úhelníka. Ta obsahuje \(n-2\) trojúhelníků. V každém z nich musí ležet alespoň jeden bod, což dává \(n-2\) bodů, tedy \(n-3\) bodů určitě stačit nebude.

Nyní mějme libovolný konvexní n-úhelník. Zorientujme ho tak, aby žádná z jeho stran ani úhlopříček nebyla svislá (což zřejmě jde, jelikož je jich konečný počet). Označme vrchol nejvíce nalevo \(V_1\) a číslujme podle x-ové souřednice \(V_n\), tedy \(V_n\) je vrchol nejvíce vpravo. Nyní sestrojíme chtěných \(n-1\) bodů. Pro každý vrchol \(V_i\) kromě \(V_1\) a \(V_n\) sestrojíme bod \(B_i\). Spusťmě svislou přímku \(p_i\) procházející bodem \(V_i\). Nechť \(U_i\) je bod odpovídající průsečíku \(p_i\) s některou z úhlopříček takový, že jeho vzdálenost od \(V_i\) je minimální. Bod \(B_i\) pak bude ležet v polovině úsečky \(V_iU_i\).

Nyní dokážeme, že danou konstrukcí jsme opravdu dosáhli toho, že v každém trojúhelníku, jehož vrcholy jsou vrcholy tohoto n-úhelníku, leží alespoň jeden bod. Mějme trojúhelník \(V_iV_jV_k\), kde búno \(i<j<k\). Pak bod \(B_j\) zřejmě leží uvnitř úhlu \(\angle V_iV_jV_k\). Zároveň z konstrukce platí, že úsečku \(V_jB_j\) neprotíná strana \(V_iV_k\), neboť ji neprotíná žádná úhlopříčka. Bod \(B_j\) tedy leží uvnitř trojúhelníku \(V_iV_jV_k\).

Tím jsme dokázali, že musíme nakreslit alespoň \(n-2\) bodů.

Ps.: vzorové řešení bylo lehce upraveno pro lepší čitelnost, nápad na zčitelnění zapůjčen od Erika Ježka.

Připomínám, že v brkosu chceme vždy důkaz, nebo alespoň zřejmé odůvodnění. Obzvláště v příkladech 4 a D, a obzvláště v případech, kdy není to zřejmé.