2. Kamaráti Mince Strážia vzorové riešenie

Ako prísť na riešenie

Pozrime sa na mince na stole. Pre jednoduchšie vyjadrovanie sa si označme mince otočené hlavou nahor písmenom \(H\), mince otočené znakom nahor písmenom \(Z\). V \(k\)-tom ťahu zmeníme písmenko \(k\) minciam, naším cieľom je dosiahnuť stav, že majú všetky mince rovnaké písmeno.

Všimnime si, že nezáleží na poradí mincí na stole, zaujímavé sú len počty \(H\) a \(Z\). Povedzme, že je viac mincí otočených hlavou hore (to vieme povedať bez ujmy na všeobecnosti – ak by neboli, vymeňme si označenia \(H\) a \(Z\)). Pokúsme sa docieliť, nech sú na konci všetky mince otočené hlavou hore. Ak máme spolu \(2n+1\) mincí, stačí nám otočiť nanajvýš \(n\) mincí.

Skúsme mince otáčať úplne priamočiaro. V prvom kole otočme \(1\) mincu zo \(Z\) na \(H\), v druhom kole otočme \(2\) mince zo \(Z\) na \(H\), \(\dots\) Keď budeme takto pokračovať, dôjdeme do stavu, keď už v \(k\)-tom kole budeme mať menej ako \(k\) mincí otočených znakom hore. V tomto momente pokračovaním v priamočiarom otáčaní sa nám počet znakov môže dokonca zvyšovať. Čo teraz? Treba to nejak opraviť.

Všimnime si, že ak sa nám to v jednom ťahu pri otáčaní \(k\) mincí pokazí, tak v nasledujúcom ťahu pri otáčaní \(k+1\) mincí môžeme tých \(k\) mincí otočených v predchádzajúcom kole dostať do pôvodného stavu a okrem nich otočiť jednu mincu.

Ak toto spravíme, pomocou dvoch po sebe idúcich kôl otočení vieme otočiť práve jednu (ľubovoľnú) mincu. Tým pádom, ak sme v \(k\)-tom kole a ostalo nám \(l\) mincí \(Z\) na stole (\(l<k\)), pomocou ťahov \(k\) a \(k+1\) otočíme jednu z daných mincí, pomocou ťahov \(k+2\) a \(k+3\) otočíme druhú z daných mincí, \(\dots\) poslednú (\(l\)-tú) mincu otočíme v ťahoch \(k+2(l-1)\) a \(k+2l-1\). Už to takmer máme hotové. K úplnosti riešenia treba ešte ukázať, že sa nám nestane, že by sme v nejakom ťahu mali otočiť viac mincí ako je na stole. To by nastalo, keby \(k+2l-1>2n+1\). Ako na to? Číslo \(l\) ide odhadnúť pomocou \(k\) vďaka \(l<k\), taktiež \(k\) ide odhadnúť pomocou \(n\) ako \(k\sim \binom{n}{2}\) (rozmyslite si), avšak takýmto výpočtom sa vieme vyhnúť. Celkovo máme \(2n+1\) otočení, potrebujeme otočiť nanajvýš \(n\) mincí. Ak budeme už od začiatku párovať po sebe idúce kolá otočení, stačí nám vykonať nanajvýš \(n\) párov otočení, t. j. vieme po nanajvýš \(2n\) kolách dosiahnuť rovnaké symboly.

Stručné riešenie

Vzorové riešenie napísané vyššie obsahuje intuíciu, ako prísť na riešenie. To vo vašom riešení písať nemusíte, na zisk plného počtu bodov stačí iba dôkaz, prečo to tak je. Osnova stručného riešenia môže vyzerať nasledovne:

Popárujme si kolá otáčania mincí, v pároch majme spolu kolá \(2k-1\) a \(2k\). Ak v tých kolách otočíme mince nasledovne (\(\dots\)), tak po danom páre kôl otočení vieme dosiahnuť otočenú práve jednu (ľubovoľnú) mincu. Keďže celkovo nám stačí otočiť nanajvýš \(n\) mincí, lebo (\(\dots\)), otočenie všetkých mincí na rovnakú stranu vieme docieliť po nanajvýš \(n\) pároch otočení, t. j. v nanajvýš \(2n\)-tom kole. Teda nenastane prípad, že by sme mali otočiť viac mincí, ako je na stole.