7. Kopu Mincí Sústredím vzorové riešenie

Andy[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í.