7. Krutá Mocná Smršť vzorové riešenie

Na začiatok uvedieme jednoduché a stručné riešenie nevyžadujúce veľké matematické vedomosti.

Nech \(a>b>c\). Zo zadania zrejme musia byť rôzne. V druhom kroku budeme mať trojicu \((b+c-a,a+c-b,a+b-c)\). Všimnime si niekoľko vecí, napríklad, že súčet sa nezmení (\(=123456789\)), alebo že budú usporiadané následovne: \[a+b-c>a-b+c=c+a-b>c-a+b.\] Všimnime si, že ak označíme \(k=b-c\) a \(l=a-b\), tak \(a-c=k+l\) a \((a+b-c)-(c-a+b)=2k+2l\), a teda sa vzdialenosť medzi najmenším a najväčším napísaním číslom zdvojnásobila.

Keďže platí \(a>b>c\), tak nutne musí aj \(a\geq c+2\), a preto po \(26\) krokoch budeme mať vzdialenosť medzi najväčším a najmenším napísaním číslom aspoň \(2\cdot 2^{26} = 134217728>123456789\). Keďže súčet musí byť rovný \(123456789\) a platí, že najväčšie napísané číslo je aspoň o \(134217728\) väčšie ako najmenšie napísané číslo, tak nutne najmenšie musí byť záporné.

Iné riešenie:

V tomto riešení sa budeme pozerať na problém s trochu náročnejšími kladivami, a síce je komplikovanejšie ako prvé, dodáva však iný pohľad na problém.

Na zadanie sa pozrieme ako na rovinu danú bodmi \((123456789,0,0),(0,123456789,0),(0,0,123456789)\). Tá zjavne spĺňa vlastnosť, že všetky body v rovine majú súčet súradníc rovný \(123456789\). Pre jednoduchosť budeme v celom následujúcom riešení uvažovať rovnobežnú rovinu danú \(E_1=(1,0,0),E_2=(0,1,0),E_3=(0,0,1)\) a súradnice uvažovaných bodov budú \((a,b,c)=\frac{(x,y,z)}{123456789}, x,y,z\in \mathbb{Z}\). Tieto body majú teraz požadované vlastnosti a budeme ich nazývať prípustné.

Každý bod \((a,b,c)\) v tejto rovine vieme napísať ako barycentrickú kombináciu \(a E_1+ bE_2 +cE_3\), kde \(a+b+c=1\). Budeme uvažovať súradnice zapísané v barycentrickej sústave, ktoré sú zhodou okolností aj súradnice kartézske. Dokážeme, že body \(A=(a,b,c)\), \(A'=(b+c-a,a+c-b,a+b-c)\) a \(T\) (ťažisko trojuholníka \(E_1E_2E_3\)) ležia na priamke, ba čo viac, nájdeme aj pomer vzdialeností. Mimochodom \(T=\frac{E_1+E_2+E_3}{3}\). Zoberme kombináciu \(\frac{2}{3}A+\frac{1}{3}A'=\frac{2}{3}(a,b,c)+\frac{1}{3}(b+c-a,a+c-b,a+b-c)=\frac{1}{3}(a+b+c,a+b+c,a+b+c)=\frac{1}{3}(1,1,1)=T\). Čo znamená, že vskutku tie body ležia na priamke a navyše vieme, že pre vzdialenosti platí \(2|AT|=|A'T|\), tj. vzdialenosť od ťažiska sa zdvojnásobí.

Ešte k dokončeniu riešenia treba ukázať, že bod \(A^{26}\) bude mimo trojuholníka \(E_1E_2E_3\), bez ohľadu na pôvodnú voľbu bodu \(A\) (samozrejme s podmienkami zo zadania). Čo je kus škaredšie ako prvá časť druhého riešenia, ale treba ju zrobiť.

Uvažujme trojuholník s bodmi \(K,L,M\) takými, že sa nachádzajú na spojniciach \(TE_i\) a zároveň ich vzdialenosť od ťažiska je \(\sqrt{(1/3^2+1/3^2+(2/3)^2)}/2^{26}\), tj. \(K^{26}=E_1\), \(L^{26}=E_2\) a \(M^{26}=E_3\). Uvedomme si, že vskutku pri párnej mocnine máme bod na spojnici \(TE_i\). Prepíšme ich vzdialenosť od ťažiska na zlomok s menovateľom \(123456789\): \[\frac{\sqrt{(1/3^2+1/3^2+(2/3)^2)}/2^{26}\cdot123456789}{123456789} \leq \frac{1.503}{123456789},\] (označme to ako \(c\)). Vzdialenosť bodov \(T\) a \(E_i\) je \(\sqrt{(\frac{2}{3})^2+(\frac{1}{3})^2+(\frac{1}{3})^2}=\sqrt{\frac{6}{9}}=\sqrt{\frac{2}{3}}\) (označme to ako \(f\)) .

Teda trojuholník, v ktorom sa musí nachádzať prípustný bod, je trojuholník \(KLM\). (Prečo? Lebo inak po \(26\) krokoch sa dostaneme mimo trojuholníka \(E_1E_2E_3\), a teda určite bude jedno číselko záporné.) Ešte raz uvedieme ako nájdeme body \(K,L,M\) v závislosti od \(c\) a \(f\): \[K=\left(\left(1-\frac{c}{f}\right)T+\frac{c}{f}E_1\right),\ L=\left(\left(1-\frac{c}{f}\right)T+\frac{c}{f}E_2\right),\ M=\left(\left(1-\frac{c}{f}\right)T+\frac{c}{f}E_3\right).\] Pozrime sa na súradnice \(K\) a odhadneme ich zhora aj zdola, aby sme nemuseli počítať s presným výsledkom. Pri \(E_1\) bude: \[\frac{41152264.2}{123456789}\leq\frac{1}{3}\left(1-\frac{1.503}{123456789}\sqrt{\frac{3}{2}}\right)+\frac{1.503}{123456789}\sqrt{\frac{3}{2}}\leq \frac{41152264.3}{123456789}\] a pre \(E_2\) a \(E_3\) budú \[\frac{41152262.2}{123456789}\leq\frac{1}{3}\left(1-\frac{1.503}{123456789}\sqrt{\frac{3}{2}}\right)\leq \frac{41152262.4}{123456789}.\] Analogicky pre \(L,M\). Je zrejmé, že v danom trojuholníku nie je iný prípustný bod ako \(T\) a ten má všetky tri súradnice rovnaké. Teda žiaden prípustný bod zo zadania nie je vo vnútri trojuholníka \(KLM\), a preto ľubovoľný začiatočný bod \(A\) vskutku po \(26\) krokoch musí vyletieť z trojuholníka \(E_1E_2E_3\), čo sme chceli dokázať.

Úloha 7 ešte raz:

K problému budeme pristupovať vysokoškolsky, a preto neočakávame, že mu budete rozumieť. Je to skôr pre fajnšmekrov.

Na čísla \(a,b,c\) sa pozrieme ako na vektor \[\overrightarrow{v}=\begin{bmatrix} a \\ b \\ c \\ \end{bmatrix},\] a na zmenu súradníc sa pozrieme ako na maticu \[A=\begin{bmatrix} -1 & 1 & 1 \\ 1 & -1 & 1\\ 1 & 1 & -1 \\ \end{bmatrix}.\] Teda jeden krok je v skutočnosti násobenie \(A\overrightarrow{v}\), a teda to čo by sme radi urobili je \(A^{26}\overrightarrow{v}\) a potom sa pozreli na súradnice.

No stačilo by aby sme tupo násobili matice \(A\cdot A \cdot A \cdots A\) a potom teda našli \(A\cdot A \cdot A \cdots A \overrightarrow{v}\). Ale násobenie matíc je vcelku nepríjemný počin, hlavne keď to nemá pekné vlastnosti. Jedna pekná však je, že je to asociatívne, avšak hneď vás sklamem, nie je to komutatívne. Preto sa pokúsime previesť maticu \(A\) na tvar, ktorý sa bude ľahšie násobiť. Menovite ju prevedieme na takzvaný Jordanov kanonický tvar, teda nájdeme matice \(P\) a \(J\) také, že \(A=PJP^{-1}\). Na nájdenie \(J\) a \(P\) treba nájsť takzvané vlastné čísla a k nim príslušné vlastné vektory matice \(A\).

Vlastné čísla sa vo všeobecnosti hľadajú ako korene polynómu \(det|A - \lambda I|\) v premennej \(\lambda\). Teda korene \[det \begin{vmatrix} -1-\lambda & 1 & 1 \\ 1 & -1-\lambda & 1 \\ 1 & 1 & -1-\lambda \\ \end{vmatrix}= (-1-\lambda)^3+2-3(-1-\lambda) = -(\lambda -1)(\lambda+2)^2.\] Determinant pre matice \(3\times 3\) spočítame ako \[a_{11}(a_{22}a_{33}-a_{23}a_{32})+a_{12}(a_{23}a_{31}-a_{21}a_{33})+a_{13}(a_{21}a_{32}-a_{22}a_{31}).\] Netreba však byť moc nadšený, takto ľahko to pre väčšie matice nefunguje :). Keďže polynóm je rozložiteľný nad poľom komplexných čísel na faktory stupňa \(1\), tak matica \(J\) vyzerá tak, že na hlavnú diagonálu dáme korene a v prípade násobných koreňov treba zvážiť pridanie \(1\)-tky nad diagonálu. (To stále nie je všeobecná forma, len špeciálne pre naše potreby.) Jediné násobné vlastné číslo je \(-2\), ale k nemu prislúchajú dva vlastné vektory, a teda \(1\)-tku nad diagonálu nedávame. O vlastných vektoroch kúsok neskôr. \[J=\begin{bmatrix} 1 & 0 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & -2 \\ \end{bmatrix}\] Táto diagonálna matica má výhodu, lebo sa ľahko umocňuje.

Na hľadanie matice \(P\) treba nájsť vlastné vektory. To sú také \(\overrightarrow{u}\), že \(A \overrightarrow{u}=\lambda_i \overrightarrow{u}\). K vlastnej hodnote \(\lambda = 1\) je príslušný vlastný vektor \((1,1,1)^T\). (Značenie \((1,1,1)^T\) znamená len transponovanie, teda ten istý vektor zapísaný v stĺpci.) K vlastnému číslu \(\lambda = -2\) je to komplikovanejšie. Ale v princípe treba vyriešiť sústavu rovníc. \[\begin{bmatrix} -1 & 1 & 1 \\ 1 & -1 & 1\\ 1 & 1 & -1 \\ \end{bmatrix}\begin{bmatrix} u_1 \\ u_2 \\ u_3 \end{bmatrix} = -2 \begin{bmatrix} u_1 \\ u_2 \\ u_3 \end{bmatrix}\] \[\begin{aligned} -u_1+u_2+u_3=-2u_1 \\ u_1 -u_2 + u_3 = -2u_2 \\ u_1 +u_2-u_3=-2u_3\end{aligned}\] To je to isté ako \(u_1+u_2+u_3=0\) a to má dva nezávislé (pekné, upravené) riešenia \((-1,1,0)^T\) a \((-1,0,1)^T,\), a preto nemáme v matici \(J\) jednotku nad diagonálou.

Maticu \(P\) zostrojíme ako \([u_1|u_2|u_3]\), kde \(u_i\) chápeme ako stĺpcové vlastné vektory. Inverznú maticu \(P^{-1}\) si dopočítajte za domácu úlohu sami a je to \[P^{-1}= \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{-1}{3} & \frac{2}{3} & \frac{-1}{3} \\ \frac{-1}{3} & \frac{-1}{3} & \frac{2}{3} \end{bmatrix},\] a teda \[A=\begin{bmatrix} 1 & -1 & -1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & -2 \\ \end{bmatrix} \cdot \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{-1}{3} & \frac{2}{3} & \frac{-1}{3} \\ \frac{-1}{3} & \frac{-1}{3} & \frac{2}{3} \end{bmatrix}.\]

Na domácu úlohu si ešte overte, že to v skutočnosti funguje. Hurá môžeme umocňovať! \[A^{26}=PJP^{-1} PJP^{-1}\cdots PJP^{-1}=PJ^{26}P^{-1},\] a teda stačí umocniť \(J\), ale to ide ľahko: \[J^{26}= \begin{bmatrix} 1 & 0 & 0 \\ 0 & (-2)^{26} & 0 \\ 0 & 0 & (-2)^{26} \\ \end{bmatrix}.\] A teda celá matica \(A^{26}\) vyzerá ako \[\begin{bmatrix} 44739243 & -22369621 & -22369621\\ -22369621 & 44739243 & -22369621\\ -22369621 & -22369621 & 44739243 \end{bmatrix}.\] Rýchla kontrola, súčet v riadkoch sa zachoval a je stále \(1\).

Teraz nám stačí povedať, že \[\begin{bmatrix} 44739243 & -22369621 & -22369621\\ -22369621 & 44739243 & -22369621\\ -22369621 & -22369621 & 44739243 \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix}\] má aspoň jednu zápornú hodnotu. Keby nie, tak by to znamenalo, že platia všetky tri rovnice zároveň \[\begin{aligned} 44739243a -22369621b -22369621c \geq 0,\\ -22369621a + 44739243b -22369621c \geq 0,\\ -22369621a -22369621b + 44739243c \geq 0.\\\end{aligned}\] Ale keď povieme, že nech bez ujmy na všeobecnosti \(a>b>c\), tak určite jedna hodnota bude záporná, menovite tá posledná. Čo je spor. Ostatné usporiadania vypadnú obdobne.

Preto môžeme povedať, že skutočne jedna hodnota bude po \(26\) prepísaniach záporná a dokázali sme to troma spôsobmi. Čo bolo treba dokázať.