Zadání XXXI. ročníku

Označme levou stranu rovnice jako \(L(n)\). Jelikož má být rovnice splněna pro všechna \(n\), musí také platit pro \(n=1\). Jednoduchým výpočtem zjišťujeme, že \(L(1) = 6\). Nyní tedy požadujeme \(6 \equiv 0 \mod k\). Jedinými vyhovujícími \(k\) tedy mohou být čísla \(1,2,3,6\).

Nyní jsou dva způsoby jak úlohu dokončit:

1: Podíváme se na levou stranu modulo 2 a 3. \(1|L(n)\) platí triviálně a dělitelnost 6 plyne z dělitelnosti 2 a 3.

Dělitelnost 2: Platí \(L(n) \equiv n^2-n \equiv (n-1)n \mod 2\). Tedy \(L(n)\) dá po dělení 2 stejný zbytek jako výraz \((n-1)n\), který je ale součinem dvou po sobě jdoucích čísel, tedy je vždy dělitelný 2. Pak také platí \(2|L(n)\).

Dělitelnost 3: Platí \(L(n) \equiv n^3-n \equiv (n-1)n(n+1) \mod 3\). Obdobný argument, jde o součin tří po sobě jdoucích čísel, tedy je dělitelný třemi. Pak také \(3|L(n)\).

Díky tomu zjišťujeme, že řešením úlohy jsou všechna z čísel \(k=1,2,3,6\).

2: Matematická indukce: pokud by číslo \(6\) bylo řešením našeho příkladu, byli by řešením i všichni jeho dělitelé, tedy bychom vyřešili všechny případy najednou. Dokažme tedy indukcí, že \(L(n) \equiv 0 \mod 6\).

Bázový krok: Pro \(n=1\) platí \(L(1) = 6 \equiv 0 \mod 6\).

Indukční krok: Nechť \(L(n) \equiv 0 \mod 6\), upravujme \[\begin{align*} L(n+1) = 4(n+1)^3 + 3(n+1)^2 - (n+1) = 4n^3 + 12n^2 + 12n +4 + 3n^2 + 6n + 3 - n - 1 = 4n^3 + 15n^2 + 17n + 6 \end{align*}\] Označme \(4n^3 + 15n^2 + 17n + 6 \equiv x \mod 6\). Využijeme indukční předpoklad a odečteme jej od obou stran rovnice: \[\begin{alignat}{2} (4n^3 + 15n^2 + 17n + 6) - (4n^3 + 3n^2 - n) & \equiv x - 0 \mod 6 \newline 18n^2 + 18n + 6 & \equiv x \mod 6 \end{alignat}\] Odtud je již jasně vidět, že číslo 6 dělí levou stranu, tedy \(x = 0\), což jsme chtěli dokázat.

Úloha byla zřejmě těžší než bylo zamýšleno. Chválím všechny kteří odevzdali bezchybné řešení. Ostatním vzdávám hold. Nejčastějších chyby byly:

1. Úvahy, že \(k\) musí být kořenem polynomu na levé straně: kořen polynomu má smysl uvažovat jen při dosazování za \(n\). My ale řešíme dělitelnost výrazu neznámým \(k\).

2. Práce s \(k=V(n)\) (\(k\) nějak závisí na \(n\)): \(k\) má implicitně být pevné přirozené číslo. Tato úvaha se částečně nabízela, ale po konzultaci jsme se tato řešení rozhodli neuznávat. Na tom, že je výraz \(4n^3+3n^2-n\) dělitelný \(n\) pro libovolné \(n\) není nic objevného.

3. Po rozložení polynomu nemusí platit že \(k\) přímo dělí některý člen rozkladu. \(k\) totiž obecně nemusí být prvočíslo, pro něž platí odpovídající věta.

4. Občas někdo opomněl ukázat, že pro jiná \(k\) než \(1,2,3,6\) není zadání splněno.

Nejprve si uvědomíme, že poslední dvojčíslí sexy patnáctky je její zbytek po dělení číslem \(100\). Označíme toto číslo \(n\) a můžeme psát:

\(15^{15^{15}} \equiv n \pmod{100}\)

K dalšímu postupu využijeme Čínskou zbytkovou větu, která nám říká, že si náš problém můžeme rozdělit na následující dvě kongruence:

\(15^{15^{15}} \equiv n \pmod{4}\)

\(15^{15^{15}} \equiv n \pmod{25}\)

Jelikož \(4\) a \(25\) jsou čísla nesoudělná, můžeme podle výše zmíněné věty říci, že \(\exists! n < 4 \cdot 25\) takové, že splňuje obě kongruence. Tedy jestliže najdeme \(n\) splňující tyto podmínky, máme jistotu, že se jedná skutečně o poslední dvojčíslí sexy patnáctky.

Podívejme se na první kongruenci. Přímo z definice a vlastností kongruencí plyne:

\(15 \equiv -1 \pmod{4} \Rightarrow 15^{15^{15}} \equiv (-1)^{15^{15}} \equiv -1 \equiv 3 \pmod{4} \Rightarrow n \equiv 3 \pmod{4}\)

Poznamejme ještě, že jsme využili faktu, že \(15^{15} = 225\) je liché číslo. Dále upravme sexy patnáctku na vhodnější tvar.

\(15^{15^{15}} = 15^2 \cdot 15^{15^{15}-2} = 25 \cdot 9 \cdot 15^{15^{15}-2}\),

z čehož jednoznačně plyne \(25 | 15^{15^{15}} \Rightarrow 25 | n \Rightarrow n \equiv 0 \pmod{25}\).

Nyní již víme, že hledáme \(n < 100\) takové, že \(25 | n \land n \equiv 3 \pmod{4}\). Snadno zjistíme, že tyto podmínky splňuje číslo \(75\).

Poslední dvojčíslí sexy patnáctky je \(75\).

Úloha měla spoustu moc pěkných a originálních řešení. Nejčastější přístup bylo buď použití Čínské zbytkové věty, nebo různé formy důkazu, že poslední dvojčíslí mocnin patnáctky (od druhé mocniny výše) je střídavě \(25\) a \(75\). Zatímco první přístup byl v drtivé většině správně, v druhém byl občas problém s nedostatečným odůvodněním. Uvedení prvních několika mocnin s tvrzením, že se tato vlastnost donekonečna opakuje jsem neuznával a strhával část bodů. Děkuji těm, kteří použili indukci či jiný formální důkaz :)

Nejdůležitější myšlenkou řešení bylo podívat se na výraz $n^{2a} + m^{2b} + 4^c $ modulo čtyřmi. Máme

\[n^{2a} + m^{2b} + 4^c = (n^{a})^{2} + (m^{b})^{2} + 4^{c} \equiv (n^{a})^{2} + (m^{b})^{2} \,\, \text{mod} \,4.\]

Využili jsme toho, že \(c \ge 0\), a tak výraz \(4^{c}\) dává po dělení \(4\) zbytek \(0\).

Podívejme se, jaké zbytky mohou dát ostatní dva členy. Oba jsou druhými mocninami nějakého přirozeného čísla a ty nám mohou dát následující zbytky:

\[0^{2} = 0,\] \[1^{2} = 1,\] \[2^{2} = 4 \equiv 0,\] \[3^{2} = 9 \equiv 1.\]

Dostáváme tedy pouze 3 možnosti:

\[ (n^{a})^{2} \equiv (m^{b})^{2} \equiv 0 \,\, \text{mod}\, 4 \, \Rightarrow n^{2a} + m^{2b} + 4^c \equiv 0 \,\, \text{mod}\, 4,\] \[ (n^{a})^{2} \not\equiv (m^{b})^{2} \,\, \text{mod}\, 4 \, \Rightarrow n^{2a} + m^{2b} + 4^c \equiv 1 \,\, \text{mod}\, 4,\] \[ (n^{a})^{2} \equiv (m^{b})^{2} \equiv 1 \,\, \text{mod}\, 4 \, \Rightarrow n^{2a} + m^{2b} + 4^c \equiv 2 \,\, \text{mod}\, 4.\]

Ukázali jsme, že ani v jednom případě nemůže nastat $ n^{2a} + m^{2b} + 4^c$ \(\equiv 3\) mod \(4\). Tedy žádné číslo dávající zbytek \(3\) po dělení čtyřmi nemůžeme zapsat tímto způsobem. To jsou všechna čísla tvaru \(4k + 3\) pro nějaké nezáporné celé \(k\), kterých je nekonečně mnoho, proto je důkaz tímto hotov.

Poznámka: Úlohu lze řešit i v případě, že povolíme \(c=0\). Zkuste se na výraz analogicky podívat modulo osmi.

Úloha byla poměrně triková – jakmile vás napadla správná myšlenka, už nebylo těžké dostat se k cíli. Proto také naprostá většina odevzdaných řešení získala plný počet bodů. Byla jsem shovívavá ke stručným řešením, protože důkaz opravdu šel sepsat na pár řádků; přesto platí, že když si nejste jistí, jestli je váš komentář dostatečný, vždy je lepší nějaké vysvětlení přidat. Potěšilo mě, kolik z vás se v řešení odkazovalo na studijní text k sérii, který vám pomohl s nápadem na postup řešení i se sepsáním myšlenek.

Rozdělíme si řešení na tři případy \(p=2\), \(p \equiv 1\) modulo 4 a \(p \equiv 3\) modulo 4.

Nejprve si uvědomíme, že teseraktový zbytek \(x\) je ve skutečnosti pouze též kvadratický zbytek. Akorát pro něj musí existovat nějaký kvadratický zbytek \(y\) tak, že \(x \equiv y^2\) modulo \(p\). Dále víme, že pro libovolné zbytky \(k\) a \(-k\) je jejich druhá mocnina stejný kvadratický zbytek. Z toho, že nenulových kvadratických zbytků modulo \(p\) je \(\tfrac{p-1}{2}\), tedy přesně půlka nenulových zbytků, plyne, že pro každý nenulový kvadratický zbytek existují pouze 2 zbytky \(k\) a \(-k\), jejichž druhou mocninou je tento zbytek. Pro nulu samozřejmě platí, že je teseraktovým zbytkem vždy.

1. \(p=2\): V tomto případě jsou teseraktovými zbytky 0 i 1.

2. \(p \equiv 3\) modulo \(p\): v tomto případě ze studijního textu víme, že pokud \(k\) je kvadratický zbytek, tak \(-k\) je kvadratický nezbytek. Tedy v každé dvojici \(k\) a \(-k\) bude právě jeden kvadratický zbytek. Tudíž pro každý nenulový kvadratický zbytek \(x\) existuje kvadratický zbytek \(k\) tak, že \(k^2 \equiv x\) modulo \(p\). Proto každý kvadratický zbytek je i teseraktovým zbytkem a v tomto případě dostaneme \(\frac{p+1}{2}\) teseraktových zbytků.

3. \(p \equiv 1\) modulo \(p\): v tomto případě víme, že pokud je \(k\) kvadratický zbytek, tak je i \(-k\) kvadratický zbytek. Tedy vždy dva kvadratické zbytky se pošlou na stejný teseraktový zbytek. Proto pouze půlka z nenulových kvadratických zbytků bude i teseraktovým zbytkem. Tedy po přičtení jedničky za nulový teseraktový zbytek dostaneme, že jich bude \(\tfrac{p+3}{4}\).

Moc mě odevzdaná řešení potěšila, je vidět, že si se zbytky umíte poradit a většinou i velice hezky sepsat své řešení. Odpouštěla jsem občasné chyby v terminologii, protože se pro mnohé jedná o nové téma. Důležitější pro mě bylo, že si umíte rozmyslet, proč se budou pro různá prvočísla chovat teseraktové zbytky jinak.

Začněme pořádným obrázkem. Pokud se má kulka dvakrát odrazit a pak Ňoumu střelit, bude muset trajektorie kulky vytvořit trojúhelník vepsaný nebo degenerovaný trojúhelník, ze kterého bude jen úsečka (to by se ale odrazil jen jednou a Ňoumu by už trefil, což nesplňuje zadání. Počítejme tedy s tím, že dráha kulky opisuje trojúhelník.

Nechť tedy Ňouma vystřelí pod úhlem \(\alpha\) (prozatím berme jako ostrý, aby odpovídal nákresek), a odrazí se v bodě M a v bodě K. \(t_L\) bude tečna v bodě \(L\). Spojnice středu a tečny musí dávat pravý úhel (jinak by to nebyla tečna) a proto \(|\angle SLM| = 90^{\circ} - \alpha\). Pak ale i \(|\angle SML| = 90^{\circ} - \alpha\), protože MSL je rovnoramenný trojúhelník. Ze zákona odrazu pak i \(|\angle SMK| = 90^{\circ} - \alpha\). Protože je SMK rovnoramenný tak získáme stejnými úvahami, že \(|\angle MKS| = 90^{\circ} - \alpha\) a \(|\angle SKL| = 90^{\circ} - \alpha\) a pak z rovnoramennosti SKL ještě, že \(|\angle KLS| = 90^{\circ} - \alpha\). Všechny vnitřní úhly v trojúhelníku jsou nyní stejné a to \(180^{\circ}-2\alpha\). Zjevně tedy KLM musí být rovnostranný a \(\alpha = 60^{\circ}\).

Bereme-li, že dvě úsečky/přímky mohou svírat jen ostré úhly, pak \(\alpha = 60^{\circ}\) je skutečně jediné řešení. Pokud úhlem výstřelu od tečny myslíme třeba orientovaný úhel, musíme za řešení považovat i \(\alpha = 120^{\circ}\).

Většina řešení byla správně, super práce! Je dobré při řešení takovýchto úloh se zamyslet, jestli by se nám nemohl stát nějaký extrémní, nebo degenerovaný případ, jako řešení, že by kulka neopsala trojúhelník, ale jen přímku. Zde jde toto řešení samozřejmě vyloučit, ale taková diskuse by měla být součástí řešení. Často totiž by situace mohla vypadat jinak pro jiný typ nákresku, jako například, kdybychom si úhel nakreslili tupý, namísto ostrého apod.

Políčka si očíslujeme zleva do prava od 1 do 7. Hráč prohraje, pokud položí kámen na poslední (tedy sedmé) pole. Dokážeme, že jeden z hráčů může vždy hrát tak, aby donutil druhého hráče pokládat kameny na lichá políčka. Při prvním tahu první hráč (červený) nutně položí kamínek na první pole a následně musí druhý hráč (modrý) umístit kamínek na druhé pole. Zkusíme tedy dokázat výherní strategii pro modrého.

Políčka si spárujeme následujícím způsobem: 1. s 2., 3. se 4. a 5. s 6.

Indukcí dokážeme, že modrý může hrát vždy tak, aby po jeho tahu byla v každém z párů buď obě políčka prázdná, a nebo obě obsazená a to tak, že v levo v páru (na lichém poli) je červený kamínek a v pravo (na sudém poli) modrý kamínek. Jako indukční předpoklad zvolíme pozici po druhém tahu, protože první dva tahy nutně musí v každé hře vypadat stejně. (Oba hráči musí umístit nový kamínek na první volné pole, protože ve hře ještě nemají žádné jiné kameny, kterými by mohli hrát.) Začínáme tedy z pozice, kdy je požadavek splněn. První pár je obsazen a ostatní jsou prázdné.

Předpokládejme, že je před nějakým tahem požadavek splněn a dokážeme, že modrý může vždy na základě tahu červeného reagovat tak, aby požadavek platil i po jeho tahu. Červený má podle pravidel na výběr ze dvou možností:

1. Přidá nový kamínek do prvního volného páru. Kamínek umístí na první volné pole, tedy do prvního volného páru. Modrý chce doplnit pár. Po tahu červeného je první volné pole to druhé z páru, do kterého umístil kámen červený. Modrý může tedy taky umístit kámen do tohoto páru. (Do prvního volného páru přibydou dva kameny, červený kámen je víc vlevo a požadavek je stále splněn.)

2. Skočí kamínkem z obsazeného páru na levé pole prvního volného páru. Modrý pak reaguje tak, že kamínkem z páru, ze kterého skočil červený, taky skočí. Přeskočí tak všechny páry, které přeskočil červený a navíc i červený kamínek a octne se tak na pravém políčku stejného páru, jako červený. Podmínka tedy stále platí.

Dokázali jsme, že modrý zvládne přinutit červeného hrát tak, aby se červený pohyboval po lichých políčkách a modrý při tom zůstával na sudých. Nyní stačí dokázat, že je hra konečná.

Každý tah číselně ohodnotíme podle toho, na kterých políčkách jsou umístěny kameny. Pokud je kámen například na 3. a na 4. poli, řekneme, že hotnota po tomto tahu je 3 + 4, tedy 7. Hodnota tak může nabývat od 0 do 28. V každém tahu se nutně hodnota zřejmě zvýší, protože buď přidáváme kameny a nebo je posouváme do prava. Hra tedy nepotrvá více než 28 tahů, je tedy konečná.

Hra končí, když jeden z hráčů umístí kamínek na sedmé pole, což musí být červený hráč, protože modrý dokáže hrát tak, aby na liché pole nemusel kámen položit.

Dokázali jsme, že druhý hráč má vyhrávající strategii.

V podstatě všichni odhalili, že vítěznou strategii má druhý hráč. Většině z vás se to podařilo i korektně dokázat. Objevovaly se především dva typy řešení. Buď jste (pomocí indukce) dokázali, že druhý hráč (modrý) může vždy hrát tak, že donutí prvního hráče (červeného) hrát pouze na lichá políčka. (Tím, že napodobuje tahy červeného.) Někteří ale zapomněli dokázat, že ve všech situacích lze takový tah provést. Druhým typem postupu bylo rozkreslení každého možného tahu červeného a reakci modrého. Možností nebylo tolik, takže se to dalo docela přehledně znázornit, což se spoustě i povedlo. Některá řešení ale byla nepřehledná a chyběly některé možné tahy červeného hráče.

Předpokládejme pro spor, že existují alespoň dva různé středy \(S_1\) a \(S_2\), podle kterých je množina \(M\) souměrná. Bez újmy na obecnosti je můžeme umístit do roviny jako body o souřadnicích \(S_1=[0,0],S_2=[1,0]\). Označme \(f_1\) středovou souměrnost podle \(S_1\) a \(f_2\) středovou souměrnost podle \(S_2\) Protože je \(M\) neprázdná, obsahuje nějaký bod \(X\), označme si jeho souřadnice \([x,y]\). Podívejme se, jak se chovají \(f_1\) a \(f_2\). Dosadíme-li bod \(X\) do \(f_1\), dostaneme bod \([-x,-y]\). Nyní druhé zobrazení. Vektor \(XS_2\) je vektor \((1-x,-y)\). Tedy obraz \(f_2(X)\) můžeme vyjádřit přičtením tohoto vektoru k bodu \([1,0]\) a dostaneme bod \(X_1=[-x+2,-y]\). Protože bod \(X\) patří do množiny \(M\), patří do ní i jeho obraz \(X_1\). Tento bod však musí mít obraz podle středu \(S_1\), který bude \([x-2,y]\). Označme \(f\) toto složení \(f_1\circ f_2\). V souřadnicích je tedy \(f([x,y])=[x-2,y].\) Pokud budeme opakovat \(k\)-krát za sebou zobrazení \(f\), dostaneme z bodu \([x,y]\) bod \([x-2k,y]\).

Množina \(M\) je omezená, proto musí existovat nějaká kružnice s celočíselným poloměrem a středem v \(X\), která obsahuje všechny body \(M\). Označme \(r\) poloměr kružnice s touto vlastností. Pokud budeme iterovat třeba \(r\) krát (stačí méně) zobrazení \(f\) na bod \(X\), dostaneme \(f^r([x,y])=[x-2r,y]=L\). Bod \(L\) má \(x\)-souřadnici \(x-2r\), což je megaspor s tím, že leží uvnitř kružnice se středem v \(X\) a poloměrem \(r\).

Tedy taková množina neexistuje.

Spoousta z vás pouze ukázala, že s každým bodem množiny \(M\) existuje jiný bod této množiny, který je od nějakého středu vzdálenější. To je dobrý začátek, ale neznamená to skoro nic. Můžeme mít ostře rostoucí posloupnost, která je stejně ohraničená.

Označme si průsečík \(AY\) a \(BZ\) jako \(P\) a průsečík \(AY\) a \(CX\) jako \(R\). Chceme tedy dokázat, že \(P=R\).

Všimněme si, že trojůhelníky \(ABY\) a \(XBC\) jsou shodné podle věty sus a stejně tak i \(YCA\) a \(BCZ\):

\(|AB|=|XB|;\) \(|\measuredangle ABY| = |\measuredangle XBC| = \beta + 60\)°; \(|BY|=|BC|\)

\(|YC|=|BC|;\) \(|\measuredangle ACY| = |\measuredangle BCZ| = \gamma + 60\)°; \(|AC|=|ZC|\)

Proto tedy \(|\measuredangle PCB| = |\measuredangle PYB| =>\) jsou to obvodové úhly nad \(PB=>\) body \(P,B,Y,C\) leží na jedné kružnici.

Stejně tak \(|\measuredangle RBC| = |\measuredangle RYC| =>\) body \(R,B,Y,C\) leží na jedné kružnici.

Kružnice je jednoznačně určena třemi body (v tomto případě \(B, Y, C\)) \(=>\) všech 5 bodů \(P, R, B, Y, C\) leží na jedné kružnici \(k\).

Úsečka má s kružnicí maximálně dva průsečíky. Pokud se zaměříme na průsečíky \(AY\) s \(k\): jeden průsečík je \(Y\) a druhý musí být \(P=R\), protože oba tyto body leží jak na úsečce \(AY\), tak i na kružnici \(k\).

Většina z vás úlohu vyřešila správně! Jak někteří zmínili, jedná se o Fermatův bod v trojúhelníku.