Zadání XXXII. ročníku
4. série
Teorie čísel
Termín odevzdání: 9. března 2026 23:59
Náměstím se rozhostilo hrobové ticho. Finťa, sedící na vzpínajícím se černém oři, vypadala v zapadajícím slunci jako zjevení. Lidé v pestrobarevných hábitech na ni hleděli s otevřenými ústy. „Slyšíte mě?“ křikla znovu. „Král Čtvrtý se vás nebojí, on vámi opovrhuje!“ Dav začal nespokojeně hučet, ale než se stačil zformovat v nějaký odpor, z postranní uličky se vyhrnul podivný průvod.
V čele kráčel muž s obrovskou čepicí připomínající sněhovou kouli – místní mu neřekli jinak než Sněhurák. Za ním se v dokonalém šiku batolil zástup trpaslíků. Nebylo jich sedm, bylo jich… no, bylo jich přesně tolik, aby z toho šla hlava kolem. Každý v rukou svíral transparent se složitým mocninným vzorcem. Finťa si uvědomila, že tohle je další z pastí, kterou na lidi nastražil Devět.
Úloha 1 – Sněhurák a $2^{kn}-1$ trpaslic:
Najděte všechna přirozená čísla \(k\) taková, že ať si vezmeme za \(n\) libovolné přirozené číslo, bude \(2^{kn}-1\) dělitelné sedmi.
Řešení
Číslo \(2^{kn}-1\) je dělitelné \(7\), právě když \(2^{kn}\equiv 1\) mod \(7\).
Podívejme se, jak vypadají mocniny dvojky modulo 7: \(2^1=2\), \(2^2=4\), \(2^3=8\equiv 1\), \(2^4=16\equiv 2\), \(2^5=32\equiv 4\), \(2^6=64\equiv 1\). Vypadá to, že se nám tvoří cyklus délky \(3\). Rozepišme si tedy jednotlivé možnosti podle toho, jaký zbytek dává exponent po dělení \(3\):
\(2^{3m}=(2^3)^m=8^m\equiv 1^m=1\) mod \(7\),
\(2^{3m+1}=2\cdot 2^{3m}\equiv 2\cdot 1=2\) mod \(7\),
\(2^{3m+2}=4\cdot 2^{3m}\equiv 4\cdot 1=4\) mod \(7\), pro \(m\) přirozené.
Odtud už je jasné, že \(2^{kn}-1\) bude dělitelné sedmi právě tehdy, když \(kn\) bude dělitelné třemi. My hledáme taková \(k\), že \(n\) můžeme vzít libovolné, zejména to musí platit i pro \(n=1\). Z toho plyne, že \(k\) s touto vlastností musí být násobkem \(3\). Zároveň je jasné, že pokud \(k\) bude dělitelné \(3\), bude dělitelné \(3\) i \(kn\), a tedy závěrem je, že hledaná \(k\) jsou právě násobky \(3\).
Komentář
Pro mnohmnohé z vás byla úloha snadná, což vedlo k tomu, že jste některá “zřejmá“ tvrzení uváděli bez vysvětlení. Byla jsem v tomto hodně mírná, když ale jde o významnou část úlohy, dodejte prosím aspoň krátký komentář.
Nejčastějším kamenem úrazu bylo, že jste se snažili použít Malou Fermatovu větu, ze které vyplynulo, že násobky \(6\) vyhovují. Neplyne z ní ale už, že žádné číslo menší než \(6\) nemůže vyhovovat také.
„Ignorujte tu bláznivou holku!“ ječel Sněhurák a rozhazoval kolem sebe letáky. Mezi lidmi se začala šířit panika a podivná otupělost. Finťa si všimla, že někteří lidé v davu začali počítat na prstech a mumlat si něco o Eulerových funkcích. Jako by je Devět očaroval, aby se snažili najít smysl v číslech tam, kde žádný nebyl.
Úloha 2 – Idk reálně:
Určete všechna přirozená čísla m pro která existuje přirozené n takové, že \(\varphi (n)=\frac{n}{m}\).
Řešení
Nejdříve zkontrolujeme speciální případ \(n=1: \varphi(1)=1=\frac{1}{1}\), tedy dostáváme pro \(m=1\) existuje \(n=1\).
Nyní si můžeme \(n\) zapsat pomocí prvočíselného rozkladu: \(n=p_1^{a_1}\cdot p_2^{a_2}\dots p_k^{a_k}\), kde \(k\in\mathbb{N}\), \(p_i\) jsou pro všechna \(i\in\{1,2,\dots ,k\}\) prvočísla a \(a_i\in\mathbb{N}_0\) pro všechna \(i\in\{1,2,\dots ,k\}\).
Ze vzorečků z pomocného textu můžeme odvodit následující vzorec (druhá rovnost platí díky nesoudělnosti prvočísel): \[\begin{aligned} \varphi(n) &= \varphi(p_1^{a_1}\cdot p_2^{a_2}\dots p_k^{a_k})\\ &= \varphi(p_1^{a_1})\cdot \varphi(p_2^{a_2})\dots \varphi(p_k^{a_k})\\ &= (p_1-1)p_1^{a_1-1}\cdot (p_2-1)p_2^{a_2-1}\dots (p_k-1)p_k^{a_k-1}\end{aligned}\] Dosadíme do vztahu \(\varphi(n)=\frac{n}{m}\) a upravíme: \[\begin{aligned} (p_1-1)p_1^{a_1-1}\cdot (p_2-1)p_2^{a_2-1}\dots (p_k-1)p_k^{a_k-1}&=\frac{p_1^{a_1}\cdot p_2^{a_2}\dots p_k^{a_k}}{m}\\ m\cdot (p_1-1)\cdot (p_2-1)\dots (p_k-1)&=p_1\cdot p_2\dots p_k\\ m&=\frac{p_1\cdot p_2\dots p_k}{(p_1-1)\cdot (p_2-1)\dots (p_k-1)}\end{aligned}\] Všimněme si, že \(m\) není závislé na mocninách, ve kterých prvočísla byla v rozkladu \(n\).
Nyní využijeme znalosti, že 2 je jediné sudé prvočíslo a naši situaci si rozdělíme dle výskytu 2 v prvočíselném rozkladu \(n\).
1) \(n\) je liché
V tomto případě by číslo \(m\) nebylo přirozené, jelikož čitatel v našem vyjádření \(m\) by byl lichý, ale ve jmenovateli by byla pouze sudá čísla.
2) \(n=2^a\)
Pro tento případ máme \(m=\frac{2}{2-1}=2\).
3) \(n=2^{a_1}\cdot p_2^{a_2}\dots p_k^{a_k}\)
Dostáváme \(m=\frac{2\cdot p_2\dots p_k}{(p_2-1)\dots (p_k-1)}\). Víme, že \(p_2,\dots p_k\) jsou všechna lichá, a tedy všechna čísla ve jmenovateli budou sudá. V čitateli máme 2 pouze v první mocnině, a proto v prvočíselném rozkladu \(n\) může být kromě 2 jen jedno další prvočíslo. Máme \(m=\frac{2p_2}{p_2-1}\). \(p_2\) je dělitelné pouze 1 a samo sebou, proto \((p_2-1)\mid 2 \wedge p_2>2\Rightarrow p_2=3\). Tudíž \(m=\frac{2\cdot 3}{2}=3\) pro \(n=2^a\cdot 3^b\), kde \(a,b \in\mathbb{N}\).
Celkem máme \(m=1\) pro \(n=1\), \(m=2\) pro \(n=2^a\) a \(m=3\) pro \(n=2^a\cdot 3^b\).
Komentář
S úlohou jste si většina bez problémů poradila. Nejčastější chybou bylo zapomenutí 1: \(\varphi(1)=1=\frac{1}{1}\).
Finťa se pokusila popohnat koně kupředu, ale cestu jí zastoupil královský zahradník Lojza. Vypadal úplně nepříčetně, v rukou držel křídu a přímo na dlažební kostky náměstí horečnatě čmáral tři čísla. „Musím je sčítat a odčítat,“ mumlal si pro sebe k Fintě, „pokud nevytvořím to správné číslo, tak je to totální L, chápeš? Vesmír ztratí balanc!“
Úloha 3 – + nebo -:
Na tabuli jsou napsána 3 celá čísla. Lojza se nudí, a tak si v každém kroku vybere dvě čísla z tabule která buď sečte, nebo odečte a výsledek napíše místo libovolného čísla na tabuli. Za jakých podmínek bude schopný takto po konečně mnoha krocích vytvořit libovolné celé číslo které si vymyslí?
Řešení
Nejprve ukážeme, že pokud mají všechna tři čísla společný dělitel větší než \(1\), nezvládneme to. Označme tento společný dělitel \(d\). Poté součet i rozdíl libovolných dvou čísel bude opět dělitelný \(d\). Tedy každé číslo které vytvoříme bude dělitelné \(d\), tedy nezvládneme vytvořit například jedničku.
Naopak, pokud největší společný dělitel všech tří čísel je \(1\), ukážeme, že se nám to podaří. Označme čísla na tabuli \(a,b,c\). Začněme s čísly \(a,b\). Použitím Eukleidova algoritmu dosáhneme toho, že na tabuli budou čísla \(0,nsd(a,b),c\). Konkrétně z čísel \(a,b\) nahradíme to, které má větší absolutní hodnotu číslem, které vznikne jako rozdíl (resp. součet) tohoto čísla s druhým číslem, pokud je druhé číslo stejného (resp. opačného) znaménka. Například z trojice \((5,7,13)\) uděláme trojici \((5,2,13)\) odečtením, ale z trojice \((-5,7,13)\) uděláme trojici \((-5,2,13)\) přičtením. Celkově tedy snižujeme absolutní hodnoty součtu, než se po konečném počtu kroků dostaneme do stavu, \((0,nsd(a,b),c)\). Stejný postup uděláme pro čísla \(nsd(a,b)\) a \(c\) a po konečném počtu kroků dojdeme do stavu \((0,0,nsd(nsd(a,b),c))=(0,0,nsd(a,b,c))=(0,0,1)\). (resp. (0,0,-1)). Jedničku už můžeme kolikrát chceme přičíst a odečíst k nule a získat libovolné celé číslo.
Komentář
Většina z vás úlohu vyřešila bez problému, podobným či stejným argumentem jako já. Často jste používali argument skrz Bezoutovu větu. Nejčastější chyba byla, že jste si rozdělili příklad na dva případy - první, kdy jsou čísla soudělná, druhý, kdy nějaká dvojice je nesoudělná. To však nepokrývá všechny trojice :) .
Lojza ale nebyl jediný. Celé náměstí se měnilo v jednu velkou učebnu aritmetiky. Finťa viděla, jak si lidé na cáry papíru píšou obrovská čísla a snaží se z nich vypočítat nějaké podivné střídavé součty cifer. „Je to rok 2026!“ křičel někdo z davu. „Musíme to spočítat, než nás Devět promění v prach!“
Úloha 4 – + a -:
Pro přirozené číslo definujeme jeho pm součet podobně jako ciferný součet, akorát cifru na pozici jednotek přičteme, cifru na pozici desítek odečteme, cifru na pozici stovek přičteme atd. Pm součet záporného čísla je \(-\)pm součet jeho absolutní hodnoty. Určete pm součet pm součtu pm součtu čísla \(2026^{2025\times2027}.\)
Řešení
libovolné číslo \(x\) můžeme zapsat jako \[x=a_0+10a_1+10^2a_2+10^3a_3 \dots,\] kde \(a_i\) jsou jeho cifry. Když si nyní označíme pm součet čísla \(x\) jako \(pm(x),\) dostáváme: \[pm(x)=a_0-a_1+a_2-a_3 \dots .\] Z kritéria dělitelnosti číslem \(11\) víme, že \(x\equiv 0\pmod{11} \leftrightarrow pm(x) \equiv 0\pmod{11}.\) Podíváme se tedy na to obecně. Zřejmě \(10 \equiv -1 \pmod{11}\) a tedy \(10^n \equiv (-1)^n\) bude kongruentní s \(1\) pro sudá \(n\) a s \(-1\) pro lichá \(n.\) Dostáváme: \[x=a_0+10a_1+10^2a_2+10^3a_3 \dots \equiv a_0-a_1+a_2-a_3 \dots=pm(x) \pmod{11}\] a tedy \[pm(pm(pm(x))) \equiv pm(pm(x)) \equiv pm(x) \equiv x \pmod{11}.\] Pro výpočet nyní využijeme fakt, že \(x \equiv y \pmod{m} \rightarrow x^k \equiv y^k \pmod{m}\) a Malou Fermtovu větu (chcete-li, můžete použít Eulerovu ;)), ze které plyne, že \(x^{10} \equiv 1 \pmod{11}.\) Dostáváme tedy: \[2026^{2025\times2027} \equiv 2^{2025\times2027} = 2^{2026^2-1} \equiv 2^{6^2-1} \equiv 2^5 \equiv 10 \pmod{11}.\] Nyní víme, že náš výsledek musí dávát zbytek \(10\) po dělení \(11.\) Je potřeba ho nějak omezit. Zřejmě \(2025<2026<2027<10^4,\) tzn. \[2026^{2025\times2027}<10^{4\times10^4\times10^4}.\] Číslo \(10^{4\times10^8}\) má \(4\times10^8+1\) cifer a je nejmenší takové a tedy naše číslo \(2026^{2025\times2027}\) má nejvýše \(4\times10^8\) cifer. Jakou hodnotu tedy může mít \(pm(2026^{2025\times2027})\)? Nejvyšší hodnota by nastala, kdyby na všech sudých pozicích (tzn. \(a_n\) pro \(n\) sudé) byly devítky a na těch lichých naopak nuly. Pro to nejmenší by to bylo analogicky, ale prohozené pozice. Dostáváme tedy: \[|pm(2026^{2025\times2027})|\leq9\times\frac{4\times10^8}{2}=18\times10^8 < 2\times10^9.\] Aplikací prvního pm součtu se nám tedy snížil počet cifer už jen na 10. Stejnou úvahou dostáváme: \[|pm(pm(2026^{2025\times2027}))|\leq9\times\frac{10}{2}=45,\] tzn. 2 cifry a poslední aplikací pm součtu získáváme: \[|pm(pm(pm(2026^{2025\times2027})))|\leq9\times\frac{2}{2}=9.\] Náš výsledek je tedy někde v množině \(\{-9,-8,\dots 8,9\}\) a dává zbytek \(10\) po dělení jedenácti. Jediné takové číslo je \(-1.\)
Komentář
S úlohou jste si všichni poradili dobře, ale ne všichni jste pak zvládli pořádně dokázat, proč bude výsledek právě \(-1\) a ne jiné číslo co dává tento zbytek po dělení jedenácti.
V tu chvíli se z davu vyřítila Radina. Vypadala zmateně, jako by se právě probudila z hrozného snu. „Finťo! Musíš mi pomoct!“ křičela. „Devět použil ten svůj příšerný přístroj! Cítím se… jako by moje mysl nebyla moje. Jako by se někdo jiný díval mýma očima!“ Finťa pochopila, že Devět začal experimentovat s prohazováním myslí samotných studentů Brkosovic.
Úloha A - Chci tvoje tělo:
Přístroj věštce Devěta fungoval tak, že se do něj připojí dva lidé a těm se prohodí jejich mysli (tzn. např. Lojzova mysl pak žije v Radinině těle a naopak). Nicméně pak se do výměny zapojili další studenti Brkosovic, kterých je celkem \(n\). Po čase je to ale omrzelo a chtěli se pomocí stejného přístroje vrátit zpátky. Kolik nejméně sezení u věštce Devěta si musí zabukovat, aby se určitě vrátili zpátky, ať už bylo předchozí prohození libovolné?
Řešení
Nejprve ukáži strategii, která pomocí nejvýše \(n-1\) výměn dokáže vrátit všem \(n\) lidem jejich duši, ať už je počáteční rozestavení jakékoliv.
Postupně budu procházet těla lidí a pokud některé nebude mít svoji duši, vezme si ji. Pokud na začátku mělo každé tělo cizí duši, po \(n-1\) krocích bude mít těchto \(n-1\) těl svoji duši. Na poslední tělo zbývá poslední duše, která musí být jeho, tudíž každé tělo má svoji duši. Pokud by na začátku mělo \(k\) těl svoji duši, stačilo by nám dokonce jen \(n - 1 - k\) výměn. Ovšem nestačilo by méně než \(n-1\) výměn?
Pojďme si to ukázat na příkladě, kdy se lidé postaví do kruhu a každý dá svoji duši tomu po pravici. V tomto případě vznikne cyklus délky \(n\), kde žádné tělo nemá svoji duši.
Pokud dojde k jakékoliv výměně, rozpadne se cyklus na dva menší cykly délek \(k\) a \(l\), pro které platí \(k + l = n\).
Teď indukcí dokážeme, že libovolný cyklus délky \(n\) lze vyřešit nejméně \(n-1\) výměnami.
Báze: Pro cyklus délky \(1\) potřebujeme \(0\) výměn. Pro cyklus délky \(2\) potřebujeme \(1\) výměnu.
Indukční předpoklad: Pokud pro každý cyklus délky \(m < n\) platí, že jej lze vyřešit nejméně \(m-1\) výměnami, tak lze cyklus délky \(n\) vyřešit nejméně \(n-1\) přeměnami.
Důkaz: Jak jsme si již ukázali, jakoukoliv výměnou se cyklus délky \(n\) rozdělí na dva cykly délek \(k\) a \(l\), kde \(k + l = n\). Tyto cykly jsou menší než \(n\), tudíž z indukčního předpokladu víme, že je lze vyřešit nejméně \(k-1\), respektive \(l-1\) výměnami. Jelikož jsme použili jednu výměnu k rozdělení cyklu na dva, dostáváme celkem
\((k - 1) + (l - 1) + 1 = k + l - 1 = n - 1\)
výměn.
Tudíž jsme dokázali, že cyklus délky \(n\) lze vyřešit nejméně \(n-1\) výměnami a na začátku jsme ukázali, že libovolné rozpoložení \(n\) duší lze určitě vyřešit pomocí \(n-1\) výměn. Výsledek je tudíž \(n-1\).
Komentář
Většina z vás měla správný výsledek. Také jste se ho snažili obhájit na příkladu ze vzorového řešení, kde všechna těla tvoří jeden cyklus. Ovšem občas jsem strhával body za to, že jste pouze poukázali na strategii, kde si vymění duši sousedící těla. Bylo by dobré ještě okomentovat, proč to nejde lépe, kdyby si duše vyměnila nesousedící těla.
Zatímco se Finťa snažila uklidnit Radinu, vzduchem se ozval mechanický bzukot. Nad hlavami davu se vznášel podivný měděný stroj, který ze své terasy ovládal sám věštec Devět. „Fascinující, že?“ křičel na celé náměstí a jeho hlas zněl jako skřípání kovu. „Podívejte se na ty geometrické obrazce! Ty kružnice se musí dotýkat, Finťo! Jen jedna tečna je správně!“
Úloha B – Tečné kružnice:
Dokažte, že pro libovolný trojúhelník s vrcholy A, B, C existují tři kružnice se středy v bodech A, B, C takové, že se po dvou dotýkají (každá dvojice kružnic má právě jeden společný bod). Dokažte, že jsou tyto kružnice určeny jednoznačně.
Řešení
Nechť \(a, b, c\) značí délky stran trojúhelníka \(ABC\) protilehlé vrcholům \(A, B, C\). Označme \(r_A, r_B, r_C\) poloměry hledaných kružnic se středy v těchto bodech. Bod dotyku dvou kružnic vždy leží na spojnici středů kružnic, proto budou body dotyků ležet na stranách trojúhelníka a jejich poloměry musejí splňovat následující rovnice: \[\begin{aligned} r_A + r_B &= c \\ r_A + r_C &= b \\ r_B + r_C &= a\end{aligned}\]
Sečtením všech tří rovnic získáme \(2(r_A + r_B + r_C) = a + b + c\). Označme si délku \(s = \frac{a+b+c}{2}\), platí: $ r_A + r_B + r_C = s $
Odečtením původních rovnic (1), (2) a (3) od tohoto součtu dostáváme jednoznačné vyjádření poloměrů: $ r_A = s - a, r_B = s - b, r_C = s - c $
Nyní potřebujeme ukázat, že tyto délky jsou vždy kladné a hledané kružnice tedy existují. Zaměřme se na poloměr \(r_A\): \[\begin{aligned} 0 &< r_A \\ 0 &< s - a \\ 0 &< \frac{a+b+c}{2} - a \\ 0 &< \frac{-a+b+c}{2} \\ 0 &< -a+b+c \\ a &< b+c\end{aligned}\]
Po úpravě této nerovnosti jsme získali nerovnost \(a<b+c\), přičemž se nejedná o nic jiného než trojúhelníkovou nerovnost, kterou délky stran trojúhelníka vždy splňují. Analogicky jsme schopni z nerovností \(0 < r_B\) a \(0 < r_C\) dostat \(b<a+c\) a \(c<a+b\).
Vzhledem k nejednoznačnosti našeho zadaní, není jednoznačnost těchto kružnic plně zajištěna. Při vymýšlení této úlohy jsme brali v potaz pouze vnější dotyk kružnic, jak je řešení ukázáno výše. V tomto případě jsou kružnice dány jednoznačně (vzhledem k délkám stran trojúhelníka). Pokud však povolíme vnitřní dotyk kružnic, úloha nebude mít jednoznačné řešení.
Pokud povolíme vnitřní dotyk, změní se podmínky pro délky poloměrů. Tato situace geometricky odpovídá konfiguraci, kdy jedna kružnice vnitřně obepíná zbývající dvě. Bod dotyku kružnic bude stále ležet na spojnici středů kružnic (vrcholů trojúhelníka), ale tentokrát mimo stranu. Pro případ, kdy kružnice se středem \(A\) obepíná ostatní, dostáváme soustavu: \[\begin{aligned} r_A - r_B &= c \\ r_A - r_C &= b \\ r_B + r_C &= a\end{aligned}\]
Řešením této soustavy (a jejích symetrických variant) získáme další tři řešení: \[(r_A, r_B, r_C) \in \{ (s, s-c, s-b), (s-c, s, s-a), (s-b, s-a, s) \}\] Kladnost těchto délek máme již dokázanou. Celkem tedy existují právě čtyři trojice kružnic splňující podmínku dotyku (jedna vnější a tři vnitřní).
Komentář
V podstatě všichni z vás vyřešili úlohu bez problémů. Občas jsem musela strhnout menší bodový obnos za drobné nedostatky, avšak průměrný bodový zisk této úlohy podle mě bude nadstandardní! Je vidět, že do 4. série už nám tu vydrželi pouze samí šikovní matematici(/čky)!!!
Dále bych se ráda za celý BRKOSí tým omluvila za nepřesnost zadání. Chtěli jsme po vás ukázat jednoznačnost kružnic, avšak tak, jak byla úloha zadaná, kružnice jednoznačně určeny nebyly. Při vymýšlení úlohy nás nenapadl vnitřní dotyk kružnic. Moc nás mrzí, pokud vás zadaní zmátlo a velice si vážíme, že jste se do úlohy i přesto pustili! Jako správné řešení jsem uznávala obě varianty, tedy a) pokud jste řešili úlohu pouze s vnějším dotykem a b) pokud jste ukázali nejednoznačnost těchto kružnic pomocí vnitřního dotyku.
„Dost těch kouzel!“ zařvala Finťa a hodila po stroji zbylý střep z vázy. Přístroj zakolísal, ale v tu chvíli se otevřela brána paláce a vyšel král Čtvrtý. V rukou svíral barevnou kostku, na které se podivně leskly barvy. „Podívej se na tuhle kostku, Finto,“ pronesl král. „Devět se rozhodl ji přebarvit. Pokud ji nesložíš správně, už nikdy neuvidíš své Brkosovice!“
Úloha C – Rubikův bullshit:
Devět se rozhodl si přebarvit rubikovu kostku 3×3×3. Obarvuje jednotlivé čtverečky pomocí šesti barev. Vždy, když dva sousední (hranou) čtverečky budou mít stejnou barvu, dostane Devy bod. Kolik nejvíce může získat bodů, jestliže každou barvu musí použít alespoň jednou?
Řešení
Teoretické maximum bodů, které může Devy získat, je \(\frac{(9\cdot 4)\cdot 4}{2}=108\). Od tohoto maxima budeme odečítat ty hrany, které jsou mezi čtverečky různé barvy.
Označme si \(o_B\) součet obvodů všech oblastí s barvou \(B\) a barvy pro jednoduchost označme \(1,2, \ldots, 6\) Pak lze bodový zisk vyjádřit jako \(108-\frac{o_1+\ldots+o_6}{2}\). Nyní je třeba minimalizovat \(o_1+\ldots+o_6\).
Začněme se situací, kdy máme pouze dvě barvy \(1,2\). Předpokládejme, že barva \(1\) je hlavní, tj. touto barvou je obarveno více čtverečků než barvou \(2\) (případně jsou počty stejné). Pak je počet bodů roven \(108-o_2\). Pro \(o_2\) však platí, že (pro \(|1|\geq|2|\)) roste s počtem čtverečků, které jsou touto barvou obarveny (pro každý počet čtverečků uvažujeme útvar s nejmenším možným obvodem). Počet bodů v případě se dvěma barvami je tedy minimální, pokud jsou všechny čtverečky až na jeden obarveny hlavní barvou.
Přidejme třetí barvu. \(1\) bude hlavní barva. Počet bodů vyjádříme jako \(108-\frac{o_2+o_3+o_{23}}{2}\), kde \(o_{23}\) je obvod všech oblastí s barvou \(2\) nebo \(3\) - při jeho výpočtu tedy považujeme barvy \(2\) a \(3\) za identické. Při minimalizaci \(o_2+o_3+o_{23}\) uvažujeme tak, že nejprve minimalizujeme \(o_{23}\), tedy obvod obou barev, a poté rozdělíme celkový útvar pro barvy \(2,3\) mezi tyto barvy. Toto však lze ukázat tak, že dvakrát za sebou provedeme úvahu z odstavce výše. Optimální tedy je mít jeden čtvereček od dvou barev.
Dostáváme tak cosi jako indukci. Podobnými úvahami lze rekurzivně ukázat, že optimum pro \(4,5,6\) barev je vždy použít jeden čtvereček od každé barvy, která není hlavní. Zbývá rozmyslet jak tyto čtverečky optimálně rozmístit pro šest barev. To už není těžký problém, pozicí okolo rohu kostky dostaneme \(14\) hran, které jsou mezi čtverečky různé barvy. Devy může získat nejvýše \(108-14=94\) bodů.
Komentář
Kamenem úrazu bylo ukázání, že je optimální mít hlavní barvu a pět čtverečků. Plný důkaz tohoto tvrzení se všemi detaily je nad rámec tohoto semináře, hodnotil jsem jej proto velmi mírně, nicméně jsem musel poukázat na některé individuální nedostatky, které se u většiny řešitelů vyskytly. Děkuji všem řešitelům a pochvala těm, kteří získali tři a více bodů.
Král zrudl vzteky, když Finťa jeho hádanku rozsekala na kusy. „Dost!“ vykřikl a pokynul strážím. „Odveďte ji k Dvanáctistěnu!“ Dav zděšeně vydechl. Dvanáctistěn byla obří stavba na okraji náměstí, o které se říkalo, že je branou do jiného světa. Byla to čistá platónská dualita zhmotněná v kameni. Finťa stála před ní a sledovala, jak se její stěny začínají chvět. Tohle nebyl konec, tohle byl teprve ten správný grind.
Úloha D – Platonická dualipa:
Mějme pravidelný dvanáctistěn s hranou délky 1. Do něj vepíšeme dvacetistěn tak, že spojíme středy sousedních stěn. Do takhle vzniklého dvacetistěnu vepíšeme dvanáctistěn tak, že opět spojíme středy sousedních stěn. Tímto způsobem postupně vytvoříme nekonečně mnoho střídajících se dvanáctistěnů a dvacetistěnů. Sečtěte objemy všech vzniklých těles.
Řešení
Vzorové řešení bylo inspirováno postupem Petra Starého, děkujeme za pěkné řešení.
Naším cílem je spočítat objem pravidelného dvacetistěnu. K tomu si jej rozdělíme na \(20\) trojbokých jehlanů, jejichž podstavy budou stěny dvacetistěnu a společný vrchol je střed dvacetistěnu. Ze znalosti vzorce pro objem jehlanu tak dostáváme vzorec:
\[V=20\frac{1}{3}Ah\]
Podstava je rovnostranný trojúhelník, který má obsah:
\[A=\frac{\sqrt{3}}{4}a^{2}\]
Pro výpočet výšky jehlanů si spočítáme poloměr koule opsané dvacetistěnu, který označíme \(r\). Dále vybereme libovolný pětiboký jehlan tvořený trojúhelníky okolo jednoho vrcholu. Jeho výšku označíme \(v\) a poloměr kružnice opsané podstavy \(s\). Tento poloměr určíme jako poloměr kružnice opsané pětiúhelníku se stranou \(a\). Ze znalosti velikosti vnitřního úhlu pravidelného pětiúhelníku zřejmě platí:
\[\sin(\frac{72}{2}^\circ) = \frac{\frac{a}{2}}{s}\]
A tedy:
\[s=\frac{a}{2\sin(36^\circ)}\]
Nyní známe délku \(s\) v závislosti na \(a\) a můžeme z Pythagorovi věty dopočítat \(v\):
\[a^{2}=v^{2}+s^{2}\]
\[v=a\sqrt{1-\frac{1}{4\sin^{2}(36^\circ)}}\]
Díky pravému úhlu u středu pravidelného pětiúhelníku lze dostat ještě další rovnice a máme tak soustavu: \[\begin{aligned} v^{2}+s^{2} &= a^{2}\\ s^{2}+(r-v)^{2} &= r^{2}\end{aligned}\]
Úpravami obou rovnic dostaneme: \[a^{2}=2rv\]
Následně můžeme konečně vyjádřit \(r\) jen v závislosti na \(a\):
\[r=\frac{a^{2}}{2v}=\frac{a}{2}\frac{1}{\sqrt{1-\frac{1}{4\sin^{2}(36^\circ)}}}\]
Nyní můžeme dopočítat i \(v\) pomocí Pythagorovy věty: \[v=\sqrt{r^{2}-\frac{a^{2}}{3}}\]
Využijeme toho, že \(\sin^{2}(36^\circ)=\frac{10-2\sqrt{5}}{16}\) a dostáváme dosazením do našeho vzorce pro objem:
\[V=\frac{5}{12}(3+\sqrt{5})a^{3}\]
Dále určíme vzdálenost středů dvou sousedících stěn pravidelného dvacetistěnu, abychom dostali délku hrany pravidelného dvanáctistěnu. K tomu využijeme výpočtu nejdelší úhlopříčky pětiúhelníku, který tvoří základnu našeho pětibokého jehlanu. Pak lze z podobnosti trojúhelníků ukázat, že spojnice středů dvou sousedících stěn pravidelného dvacetistěnu je oproti úhlopříčce třetinová. Samotná úhlopříčka má délku:
\[a'=2a\cos(36^\circ),\]
přičemž
\[\cos(36^\circ)=\frac{\sqrt{5}+1}{4}\]
Okamžitě tedy vidíme, že spojnice středů má délku: \[b=\frac{1+\sqrt{5}}{6}.\]
U dvanáctistěnu budeme postupovat podobně, pouze zjistíme objemy pětibokých jehlanů. Použijme známý fakt, že správně zvolené vrcholy tvoří krychli. Střed dvanáctistěnu označíme \(X\). Vyberme libovolnou stěnu a její vrcholy označme postupně \(ABCDE\). Poté lze vzdálenost \(AX\) rčit pomocí délky úhlopříčky \(AC\).
\[AX = \frac{\sqrt{3}}{2}AC.\]
Pokud \(H\) je střed \(ABCDE\), tak \(AH\) odpovídá poloměru kružnice opsané, takže z Pythagorovy věty určíme výšku \(XH\). Obsah pětiúhelníku je známý, tedy stačí celý dvanáctistěn opět rozdělit na shodné pětiboké jehlany.
\[V=12\frac{1}{3}Ah=a^{3}\frac{15+7\sqrt{5}}{4}\]
Závěrem ještě určíme vzdálenost středů sousedních stran. K tomu určíme z Pythagorovy věty a kružnice opsané poloměr \(r\) kružnice vepsané stěně. Následně si určíme úhel, který dvě stěny svírají:
\[\tan(\phi/2)=\frac{XH}{r}\]
Konečně pomocí kosinové věty a kružnice vepsané určíme vzdálenost středů:
\[b=\frac{5+3\sqrt{5}}{10}a\]
Nyní již známe všechny potřebné informace pro výpočet součtu objemů. Délky hran těles zjevně klesají lineární, dostáváme tak geometrickou posloupnost. Nejprve určíme koeficient \(q\) změny objemů dvou po sobě jdoucích členů posloupnosti, kde jeden člen posloupnosti je součet objemů po sobě jdoucího dvacetistěnu a dvanáctistěnu. Zdůrazněme ještě, že to bude třetí mocnina koeficientu změny délek hran, jelikož objem se mění se třetí mocninou délky hran.
\[q=(\frac{5+3\sqrt{5}}{10}\cdot\frac{1+\sqrt{5}}{6})^3=(\frac{5+2\sqrt{5}}{15})^3\]
Ještě určeme počáteční objem \(V\) čistě dosazením. První člen výrazu je objem dvanáctistěnu s délkou hrany \(1\), druhý člen je objem dvacetistěnu s délkou hrany rovnou spojnici středů stěn tohoto dvanáctistěnu.
\[V=\frac{15+7\sqrt{5}}{4}+\frac{5(3+\sqrt{5})}{12}\left(\frac{5+3\sqrt{5}}{10}\right)^{3}\]
Posledním krokem je použít vzorec pro součet nekonečné geometrické řady s výše spočítaným počátečním objemem a kvocientem menším než \(1\): \[S=\frac{V}{1-q}=\frac{503055+229995\sqrt{5}}{68176}\doteq 14.9223.\]
Zadání neuvádí jednotku délky, proto je řešení v obecných jednotkách krychlových.
Komentář
Úlohu se rozhodlo řešit jen velice málo z vás a nedivím se vám. Ta spousta výpočtů by mě taky odradila. Dvě řešení byla perfektní, jedno mělo jen drobné nedostatky či chyby z nepozornosti. Celkově moc pěkná práce a velký respekt těm, kteří se odvážili do toho pustit.