[email protected] Noro Micheľ

Je dobré si všimnúť jednoduchú vlastnosť, ktorú „strednutie“ dvojice mincí nezmení. Je to poloha ťažiska dvojice mincí, a teda aj ťažiska celku. Nasleduje obkec, ktorý túto myšlienku zapíše.

Pre dvojicu mincí $M$ a $N$, ktoré majú v (kartézskych) osiach $x$ a $y$ súradnice $[M_x,\ M_y]$, $[N_x,\ N_y]$, máme dvojicu súčtov $M_x+N_x$; $M_Y+N_y$, ktorú môžeme značiť skrátene $M+N$ (teda ide o nezávislé sčítanie dvoch dvojíc čísiel). Prečo má každá dvojica mincí (mincami myslíme súradnice ich stredov, čo je jediná relevantná informácia o nich) pred strednutím a po strednutí rovnaký súčet? To je preto, že stred $M$ a $N$ sa nachádza v priemere $x$-ových, ako aj $y$-ových súradníc $M$, $N$ (ak neveríte, je to ľahké cvičenie na podobné trojuholníky), teda podľa našej konvecnie je to $M’=N’=\frac{M+N}{2}$, takže súčet $M’+N’$ aj po strednutí ostane rovnaký. Skúsme preto dobre definovať ťažisko $T$, ktoré by sa, intuitívne, tiež nemalo meniť. Nech je to $$T=\frac{M_1+M_2+\dots+M_n}{n},$$ kde $M_1, M_2, \dots, M_n$ značí súradnice všetkých $n$ mincí. No a keďže súčet $M_1+M_2+\dots+M_n$ je invariantný, počet mincí tiež, tak aj $T$ je invariantné. Ťažisko $T$ je však na konci zároveň polohou každej mince v tomto momente.

Všimnime si cestu jednej mince. Pri každom spojení s inou mincou sa jej príspevok predelí dvomi. Táto minca prispieva do polohy ťažiska $\frac{1}{n}$-tinou svojej pôvodnej polohy a poloha ťažiska je zároveň jej konečná poloha. To by mohlo znieť nádejne na zabránenie preusporiadania niektorých pozícií do jedného bodu, totiž v tejto chvíli vidíme súvislosť medzi tým, ako sa môže minca hýbať, a tým, kde (v závislosti na $n$) má skončiť. Povedzme, že ak by bol príspevok jednej mince nejako unikátny (napríklad $\sqrt 2$, alebo by to bola jediná minca s nenulovými súradnicami), tak by sa dalo ľahko povedať, aký príspevok môže a musí táto minca mať na ťažisko $T$. Konštrukcií je mnoho, ukážeme si jednu.

Konštrukcia pozícií, ktoré sa nedajú strednúť do jedného bodu

Nech $n-1$ mincí má obe súradnice 0, minca $M_n$ bude na mieste [$0,1$]. Teda každá $M_i$ musí skončiť po konečnom počte krokov na pozícii $T=\frac{1}{n}$. Mincu $M_i$ po strednutí, ktorého sa zúčastnila, značme $M_i’$. Dokážeme, že ak je každá $M_i$ zapísateľná ako [$0,\frac{p}{q}$], kde $p,q$ sú nesúdeliteľné, $q$ je mocnina dvojky (ďalej už budeme, ak dovolíte, písať len $\frac{p}{q}$, lebo prvá súradnica je stále $0$), tak to isté platí aj pre $M_i’$. To na začiatku platí, keďže všetky mince majú celočíselné súradnice.

Nazačiatku je $M_i=0=\frac{0}{2^0}$ pre $i<n$ a $M_n = 1 = \frac{1}{2^0}$. Ďalej použijeme indukciu. Nech sa $M_i, M_j$ chystajú strednúť. $M_i = \frac{p}{2^k},\ M_j = \frac{r}{2^l}$. Potom

$$M_i’ = M_j’ = \frac{1}{2} \left(\frac{p}{2^k}+\frac{r}{2^l}\right) = \frac{p.2^l+l.2^k}{2^{k+l+1}}.$$

V čitateli má tento výraz prirodzené číslo, v menovateli mocninu dvojky, vykrátime prebytočné dvojky a je v požadovanom tvare.

A čo ťažisko? To je $1/n$, a keďže každá minca je vždy [$0,\frac{p}{2^{x}}$], $x \in \mathbb{N}$, čo chceme, aby bolo [$0,\frac{1}{n}$], tak $n$ je mocninou dvojky, v opačnom prípade sa všetky mince nedajú strednúť do jedného bodu.

Strednutie pre vyhovujúce $n$

Tým máme ťažšiu časť hotovú a ostáva vymyslieť algoritmus pre dostanie $n=2^{x}$ mincí do jedného bodu, t. j. prípad, keď $n$ je mocninou dvojky. Ak vieme skonštruovať sekvenciu strednutí pre ľubovoľnú konšteláciu $n=2^{x}$ mincí, tak popárovaním (nejaké isto existuje) $n=2^{x +1}$ mincí a následným interpretovaním každej dvojice mincí v jednom bode ako $1$ mincu máme $n=2^{x}$ mincí, čím sme, spolu s triviálnym indukčným predpokladom pre $n=2$, hotoví.