Body \(A,C,E\) a \(G\) dělí kružnici na 4 shodné oblouky. Pokud nalezneme bod \(B\) na oblouku \(AC\), který maximalizuje/minimalizuje součet \(|AB|+|BC|\), bude to stejné platit i pro body \(D,F,H\), neboť se jedná o totožnou úlohu, pouze otočenou.

Maximální/minimální obvod budeme tedy schopni vyjádřit jako \(4(|AB|+|BC|)\) a můžeme se tedy zaměřit pouze na hledání optima pro bod \(B\).

Minimální obvod

Každé \(3\) body splňují trojúhelníkovou nerovnost: \(|AC| \leq |AB|+|BC|\). Součet \(|AB|+|BC|\) tedy nemůže nabývat menší hodnoty než \(|AC|\). Rovnost nastává v případě, kdy bod \(B\) leží na úsečce \(AC\). Zároveň však víme, že bod \(B\) musí ležet na kružnici, máme tedy jen \(2\) možnosti: \(B=A\) nebo \(B=C\). Ve výsledku tedy dojde k degeneraci osmiúhelníku na daný čtverec \(ACEG\) a minimální obvod bude:

\(4|AC| = 4\sqrt{|SA|^2 + |SC|^2} = 4\sqrt{1^2 + 1^2} = 4\sqrt{2}\)

Maximální obvod

Víme, že \(|\measuredangle ASC| = 90° = |\measuredangle ASB| + |\measuredangle BSC|\). Položme \(|\measuredangle ASB| = \alpha\), potom tedy \(|\measuredangle BSC| = 90° - \alpha\). Bod \(B\) leží na kružnici, tj \(|SB| = |SA| = 1\). Trojúhelník \(ABS\) je rovnoramenný se základnou \(AB\), pro kterou bude platit:

\[\begin{aligned} sin(\frac{\alpha}{2}) &= \frac{\frac{|AB|}{2}}{|SA|} \\ sin(\frac{\alpha}{2}) &= \frac{\frac{|AB|}{2}}{1} \\ |AB| &= 2sin(\frac{\alpha}{2})\end{aligned}\]

Podobně pro \(BC\):

\[\begin{aligned} sin(\frac{90° - \alpha}{2}) &= \frac{\frac{|BC|}{2}}{|SB|} \\ sin(\frac{90° - \alpha}{2}) &= \frac{\frac{|BC|}{2}}{1} \\ |BC| &= 2sin(45° - \frac{\alpha}{2})\end{aligned}\]

\(|AB| + |AC|\) je tedy \(2sin(\frac{\alpha}{2}) + 2sin(45° - \frac{\alpha}{2}) = 2 (sin(\frac{\alpha}{2}) + sin(45° - \frac{\alpha}{2}))\)

Pomocí vzorce pro součet dvou sinů : \(sin(x) + sin(y) = 2sin(\frac{x+y}{2})cos(\frac{x-y}{2})\), můžeme výraz dále upravit na:

\(|AB| + |AC| = 2[2sin(\frac{\frac{\alpha}{2} + (45° - \frac{\alpha}{2})}{2})cos(\frac{\frac{\alpha}{2} -(45° - \frac{\alpha}{2})}{2})] = 4sin(22,5°)cos(\frac{\alpha - 45°}{2})= 2\sqrt{2-\sqrt{2}} cos(\frac{\alpha - 45°}{2})\)

Pokud tedy nalezneme maximální hodnotu výrazu \(cos(\frac{\alpha - 45°}{2})\), nalezneme i maximální obvod celého osmiúhelníku. \(\alpha\) je z intervalu \((0°,90°)\), protože se jedná o část úhlu \(ASC\). Výraz \(\frac{\alpha - 45°}{2}\) může tedy nabývat hodnot \((-22,5°,22,5°)\). Funkce cosinus nabývá hodnot \([0,1]\), přičemž maxima (\(1\)) nabývá v hodnotách argumentu ve tvaru \(2k\pi\), pro \(k \geq 0\), \(k \in \mathbb{Z}\), což v daném intervalu \((-22,5°,22,5°)\) splňuje pouze \(0\).

Maximální obvod bude tedy v případě, kdy

\[\begin{aligned} cos(\frac{\alpha - 45°}{2}) &= 1 \\ \frac{\alpha - 45°}{2} &= 0 \\ \alpha - 45° &= 0 \\ \alpha &= 45° \end{aligned}\]

Jedná se tedy o pravidelný osmiúhelník a jeho obvod bude nabývat hodnoty \[4 \cdot (|AB| + |BC|) = 4 \cdot 2 \sqrt{2 - \sqrt{2}} cos(\frac{\alpha - 45°}{2}) = 8 \sqrt{2-\sqrt{2}}\]

Spousta z vás úlohu vyřešila správně!!! Našla se však řešení, která nebyla úplně správná, nebo dotažená. Nejčastějším problémem bylo, že jste neprovedli pořádný důkaz (především při hledání maximálního obvodu), ale spíše jste řekli takto to prostě je! :D

Pokud graf obsahuje kružnici liché délky, pak je tato kružnice zároveň uzavřeným sledem liché délky, tedy jedna implikace je triviální.

Pro tu opačnou, předpokládejme, že graf obsahuje uzavřený sled liché délky. Najděme nejkratší uzavřený sled liché délky v našem grafu. (Každý lichý sled má konečnou délku, z těchto délek vybereme tu nejmenší. Pokud tuto nejmenší délku má více sledů, vyberme si jeden libovolně.)

Ukážeme, že tento sled nejkratší liché délky je kružnice. Označme ho \(v_1,\dots v_n,v_1\). Předpokládejme tedy pro spor, že není. Potom se nějaký vrchol \(v\) v tomto sledu opakuje, tedy \(v_i=v_j\), pro \(i\neq 1\). Tento vrchol nám rozělí sled na dva uzavřené sledy, jeden z nich je \(v_i\dots v_j\), druhý je \(v_1,v_2,\dots, v_i,v_{j+1},\dots v_n\). V součtu mají lichou délku \(n\), tedy právě jeden z nich musí být liché délky, což je spor s volbou nejkratšího lichého sledu, jelikož tento nově vzniklý je kratší.

Většina z vás si s úlohou poradila bez problému. Dokonce se mi sešlo několik různých metod důkazu. Někteří jste dokázali pouze jednu implikaci :(.

Ozn. prvky množiny jako \(a_1, \dots, a_n\). Ukažme, že potřebujeme \(n\) permutací.

\(n-1\) nestačí - krásným protipříkladem budou permutace, které nám cyklicky prohodí všechny prvky, tj. každá permutace posune prvek \(a_i\) na \(a_{i+1}\) a \(a_n\) na \(a_1\). Pokud jich bude pouze \(n-1\), při složení se každý z prvků posune o menší počet než je \(n\), či-li se nezobrazí sám na sebe.

\(n\) už stačí - podívejme se na libovolný prvek (říkejme mu \(a\)) a zobrazme ho postupně ve všech permutacích, tj. se podívejme na \(a, f_1(a), f_2(f_1(a)), \dots , f_n(f_{n-1}(...f_1(a))...)\), těchto prvků bude přesně \(n+1\), z Dirichletova principu tam musí být alespoň dva prvky stejné. To znamená, že složení permutací mezi těmito prvky má pevný bod.

Většina se s úlohou porvala parádně, vzorně jste ukazovali i to, že \(n-1\) nestačí!

Tvrzení dokážeme sporem. Předpokládejme tedy, že existují dvě různá prvočísla \(p\) a \(q\), která dělí \(n\).

Podívejme se nejprve na jedno z nich a pokusme se vyjádřit, kolikrát se vyskytne v součinu na levé straně rovnosti. Víme, že \(n\) je násobkem \(p\) a \(p\) bude dělit přesně každé \(p\)-té číslo menší nebo rovno \(n\). Proto \(p\) dělí právě \(n/p - 1\) největších společných dělitelů v součinu. Pokud \(p^2\) už \(n\) nedělí, tady jsme skončili. Pokud ale ano, bude také podle stejné úvahy dělit \(n/p^2 - 1\) činitelů na levé straně.

Obecně tedy předpokládejme, že nejvyšší mocnina, v níž \(p\) dělí \(n\), je \(a\). Potom \(p^i\), \(i \leq a\) dělí právě \(n/p^i - 1\) činitelů. Abychom získali nejvyšší mocninu \(p\), která dělí levou stranu rovnice, musíme tato čísla sečíst. Dostaneme tedy

\[n/p-1 + n/p^2-1 + ... + n/p^a-1 = n(1/p + 1/p^2 + ... + 1/p^a) - a.\]

Na pravé straně máme \(n^k\). Toto číslo bude dělitelné \(p^a\) umocněným na \(k\), tedy nejvyšší mocnina \(p\), která ho dělí, je \(ak\). Jelikož se obě strany rovnice rovnají, musejí se rovnat i mocniny, v nichž je \(p\) dělí, a tak dostáváme

\[n(1/p + 1/p^2 + ... + 1/p^a) - a = ak,\] \[n(1+p+ ... + p^{a-1}) -ap^a = p^a ak,\] \[n\frac{p^a-1}{p-1} -ap^a = p^a ak.\]

Použili jsme vzoreček pro součet geometrické řady. Úplně stejnou úvahu můzeme provést i pro \(q\). Nejvyšší mocninu, ve které dělí \(n\), označme \(b\) a máme analogicky

\[n\frac{q^b-1}{q-1} -bq^b = q^b bk.\]

Vynásobením \(bq^b\), respektive \(ap^a\) dostáváme

\[nbq^b\frac{p^a-1}{p-1} -abp^aq^b = p^aq^b abk,\] \[nap^a\frac{q^b-1}{q-1} -abp^aq^b = p^aq^b abk.\]

Obě rovnice mají stejnou pravou stranu, máme tedy

\[nbq^b\frac{p^a-1}{p-1} -abp^aq^b = nap^a\frac{q^b-1}{q-1} -abp^aq^b.\] \[bq^b\frac{p^a-1}{p-1} = ap^a\frac{q^b-1}{q-1}.\]

Na levé straně rovnosti máme \(q^b\), které tak musí dělit pravou stranu. Určitě je nesoudělné s \(p^a\), vždyť \(p\) a \(q\) jsou různá prvočísla. Stejně tak je nesoudělné i se zlomkem, který je součtem geometrické řady, protože v této řadě \(q\) dělí všechny členy kromě \(1\). Zbývá tak, že \(q^b|a\). Analogicky ukážeme, že \(p^a|b\). Odtud zejména \(q^b \leq a\) a \(p^a \leq b\).

Jelikož \(p,q \geq 2\), máme \(a \geq q^b \geq 2^b\) a \(b \geq p^a \geq 2^a\), takže dohromady \(a \geq 2^b \geq 2^{2^a}\). Pro nejmenší možné \(a=1\) tato nerovnost neplatí a s rostoucím \(a\) poroste pravá strana mnohem rychleji než levá, takže nerovnost nemůže být splněna, máme spor.

Dostali jsme spor s předpokladem, kterým bylo, že existují dvě různá prvočísla dělící \(n\). Závěrem tedy je, že pokud nějaké \(n\) splňuje rovnici ze zadání, musí být mocninou prvočísla.

S úlohou jste se popasovali moc hezky. Všechna úplná řešení měla podobnou strukturu – vyjádření \(p\)-valuací, nějaký argument s dělitelností, spor z nerovností. Někteří z vás si mysleli, že součástí kompletního postupu je i potřeba najít nějaké konkrétní řešení. Když dokazujete implikaci, není nutné se zabývat tím, jestli opravdu může nastat případ, kdy obě tvrzení jsou pravdivá.

Vzorové řešení je ilustrováno pomocí obrázků:

Přidáním tetromina tvaru S se zaplnil 6. řádek a proto zmizel.

Přidáním tetromina tvaru T se nezaplnily žádné řádky ani sloupce, tudíž žádná hrací pole nezmizela.

Přidáním tetromina tvaru L se zaplnily první 3 sloupce a poslední 2 řádky, proto zmizely.

Přidáním tetromina tvaru I se zaplnil 5. řádek a proto zmizel. Na hracím plánu se již nenachází žádná zabarvená pole, tudíž jsme došli k výsledku.

Většina z vás měla řešení naprosto správně, pár z vás bohužel nepochopilo zadání. Doufám že to již bude zřetelné ze vzorového řešení. Děkuji všem, kteří si dali práci s obrázky, moc dobře se to po vás opravovalo :)

Kuba H.

Máme rovnici \(4^y-2^yy-4y=0\). Jednoduchými úpravami dostáváme \[\begin{aligned} 4^y&=2^yy+4y\\ 2^{2y}&=y(2^y+4).\end{aligned}\] Vidíme, že levá strana rovnice je tvaru \(2^{2y}\), tedy i pravá strana musí být mocnina čísla 2, proto i oba činitelé součinu na pravé straně budou mít tuto vlastnost. \[\begin{aligned} y&=2^a\\ 2^y+4&=2^b\end{aligned}\] Druhá rovnice má v přirozených číslech řešení pouze pro \(y=2\):

• \(\bullet\) rovnici můžeme přepsat jako \(2^b-2^y=4\)

• \(\bullet\) obecně je rozdíl \(2^m-2^n\), kde \(m \geq n\), \(m,n\in \mathbb{N}\), roven součtu mocnin dvojky \(2^k\), pro které platí \(2^n \leq 2^k < 2^m\), např. \(2^6-2^2=64-4=60=32+16+8+4\), v případě \(m-n=1\) je rozdíl roven menšiteli

• \(\bullet\) v našem případě máme rozdíl 4, to nemůže být součet mocnin dvojky, proto \(2^y=4\)

Po dosazení skutečně \(4^2-2^2\cdot 2-4\cdot 2=16-8-8=0\). Tedy jediné řešení naší rovnice je \(y=2\).

Většině z vás se úloha velmi povedla. Našli jste různé způsoby řešení, ať už jste rovnici upravovali, nebo si všimli rostoucí povahy levé strany rovnice. Ovšem spousta z vás rostoucí charakter nedokazovala, což jste mohli provést například pomocí matematické indukce.

Jako první se zamyslíme nad tím, jak nejjednodušeji tento objem vyjádřit. Jako v zadání se na to budeme dívat pouze z boku, ale počítat budeme rovnou objem ve 3D.

Nejlehčí asi bude si těleso rozdělit podle úsečky \(XY\). Vznikne nám tak kužel (\(XYC\)) a spodní část koule. Objem kužele vypočítáme podle klasického vzorečku \(V_{kuzel}=\frac{1}{3}\pi r^2v\), kde \(r=a\) a \(v=2+c\) (protože \(|CD|=|CS|-1=2\)). Objem zbytku koule pak vypočítáme tak, že od objemu koule odečteme objem useklé úseče (vrchní), tzn.: \(V_{zbytkek koule}=V_{koule}-V_{usec}=\frac{4}{3}\pi r^3 - \frac{1}{3}\pi v^2(3r-v)\), kde tentokrát \(r\) značí poloměr původní koule, tedy \(1\) a \(v=c\) je výška úseče. Pro celkový objem tedy dostáváme: \[V=\frac{1}{3}\pi a^2(2+c)+\frac{4}{3}\pi - \frac{1}{3}\pi c^2(3-c)\] Stačí nám tedy vypočítat délky \(a\) a \(c=1-b\). Z podobnosti trojúhelníků \(ASC\) a \(XZC\) dostáváme: \[\frac{|CS|}{|AS|}=\frac{|CZ|}{|XZ|}\] \[\frac{3}{1}=\frac{3-b}{a}\] \[3a=3-b\] \[b=3(1-a)\] To si nyní dosadíme do Pythagorovy věty z pravoúhlého trojúhelníku \(SXZ\) a dostáváme kvadratickou rovnici. \[a^2+b^2=1\] \[a^2+(3(1-a))^2=1\] \[10a^2-18a+8=0\] \[5a^2-9a+4=0\] Tu si za pomoci diskriminantu \(D=(-9)^2-4\cdot 5\cdot 4=1\) jednoduše dopočítáme jako: \(a_{1,2}=\frac{-(-9)\pm \sqrt{1}}{2\cdot 5}\) a tedy \(a_1=1\) a \(a_2=\frac{4}{5}\). Můžeme si ale všimnout, že \(a\) musí být jistě menší než \(1\) a dostáváme tedy \(a=\frac{4}{5}\), \(b=3(1-\frac{4}{5})=\frac{3}{5}\) a konečně i \(c=1-\frac{3}{5}=\frac{2}{5}\). Výsledný objem tedy vychází jako: \[V=\frac{1}{3}\pi (\frac{4}{5})^2(2+\frac{2}{5})+\frac{4}{3}\pi - \frac{1}{3}\pi (\frac{2}{5})^2(3-\frac{2}{5})=\]\[=\frac{64}{125}\pi + \frac{4}{3}\pi -\frac{52}{375}\pi=\frac{192+500-52}{375}\pi =\] \[=\frac{640}{375}\pi=\frac{128}{75}\pi\]

Začala bych tím, že opravování této úlohy mi dalo fakt zabrat. Snažila jsem se být co nejvíce spravedlivá a několikrát jsem si to kontrolovala, aby to bylo fér. Dělali jste totiž hrozně moc náhodných chyb, které se vůbec neopakovaly. Řekla bych, že to bylo většinou způsobené tím, že jste to sepisovali hodně chaoticky, nepřekontrolovali si to po sobě, nebo jste třeba vůbec nenapsali, co dosazujete do vzorečků a pak jste se v tom možná sami ztratili.. Nejčastější chybou tak bylo to, že jste do svého řešení nedali žádný obrázek.. (Můžete se podívat do pravidel, máme tam napsáno, že za to můžeme strhávat body, tak ne že si někdo bude stěžovat!) Možná vám to přijde jako blbost, ale ten obrázek fakt pomůže to řešení pochopit. Jinak moc chválím ty, co mají \(3,75\) bodů a víc! :)

Nejprve si lze povšimnout, že ani jedna z operací nedokáže změnit první a poslední písmeno slova (vyjma \(xx=x\), které spojí první a poslední písmeno). Pak všechna slova délky \(2\) budou v různých třídách.

Díky příkladu ze zadání již víme, že \(abc=azbc\) (kde \(z \in S\)), tedy libovolná slova se stejným prvním a stejnými posledními dvěma písmeny jsou ve stejné třídě. Tím dostaneme, že tříd slov bude nejvýše tolik, kolik je nejvýše třípísmenných slov (ve kterých není stejné písmeno \(2 \times\) za sebou).

Díky rovnosti \(abc=abcc=abcacc=acc=ac\) však lze také přiřadit libovolnému třípísmennému slovu třídu dle jeho prvního a posledního písmene, tedy ztotožníme dvoupísmenná a vícepísmenná slova. Jinými slovy, libovolná dvě slova se stejnými počátečními a posledními písmeny jsou ve stejné třídě slov. Tříd slov je tedy tolik, kolik je dvoupísmenných slov, tzn. \(27\cdot27=729\). (pozn. jednopísmenná slova patří do příslušné třídy dle rovnosti \(a=aa\))

Tato Déčková úloha evidentně nebyla mezi řešiteli oblíbená. Samo zadání zřejmě spoustu lidí odradilo. Osm odevzdaných řešení však mělo svou kvalitu, byť nebyla všechna správně - rovnost abc=ac byla hodně schovaná. Řešitele této úlohy mohu pochválit za snahu i správné uvažování.