6. Krtko Modeluje Systémy vzorové riešenie

Priamočiarym prístupom v takejto úlohe je opísať, ako máme čísla povymieňať, aby sme najviac po \(35\) výmenách dostali požadovaný stav. Ako zariadime, aby súčty susedných čísel boli zložené čísla? Pri takýchto úlohách sa nám oplatí zamyslieť nad nejakou jednoduchou postačujúcou podmienkou, ktorá nám to zaručí. Napr. môžeme sa snažiť o to, aby skúmané súčty boli deliteľné nejakým číslom. Najmenším kandidátom je číslo \(2\). Musíme si však dať pozor na to, že nie všetky čísla, ktoré sú deliteľné dvomi, sú aj zložené. Neplatí to pre dvojku samotnú. To je však v poriadku, lebo súčet dvoch čísel je aspoň \(1 + 2 = 3\), tak číslo \(2\) ako súčet v tabuľke nikdy nedostaneme. Preto ak máme v tabuľke párny súčet susedov, tak ide o zložené číslo.

Súčet dvoch čísel je párny, ak sú obe čísla párne alebo obe nepárne. Preto by sme párne a nepárne čísla chceli dostať čo najviac k sebe. To vieme celkom pekne spraviť. Rozdeľme si tabuľku na dve polovice rozmerov \(5 \times 10\). Zoberme si tú polovicu, v ktorej je menej nepárnych čísel (ak ich je rovnako veľa, tak ľubovoľnú). Bez ujmy na všeobecnosti nech je to horná polovica. Keďže máme medzi číslami od \(1\) do \(100\) presne \(50\) nepárnych, tak v hornej polovici ich je najviac \(25\). Tiež platí, že ich počet je rovnaký ako počet párnych čísel v dolnej polovici. Preto môžeme každé nepárne číslo z hornej polovice vymeniť s párnym číslom z dolnej polovice. Tak spravíme najviac \(25\) ťahov a dostaneme sa do stavu, kedy máme v hornej polovici iba párne čísla a v dolnej polovici len nepárne. Preto súčet dvojíc v rovnakej polovici je vždy párny (a rôzny od \(2\)), a teda to je zložené číslo.

Jediné dvojice, ktoré nám dávajú nepárny súčet, sú tie, ktoré obsahujú jedno číslo z hornej polovice a druhé z dolnej. Takých je celkom \(10\). To je dobrá správa, lebo nám ostalo ešte \(10\) ťahov. Tie využijeme na to, aby sme v nich zabezpečili súčty ako zložené čísla. Keď nám tam deliteľnosť dvomi nevychádza, tak môžeme skúsiť ďalšie číslo, a to deliteľnosť tromi.

V každom stĺpci \(s\) vykonáme nasledovný ťah: Označme si číslo v piatom riadku ako \(a\) (teda to párne, najnižšie v hornej polovici) a číslo pod ním ako \(b\) (teda najvyššie nepárne). Označme si zvyšok čísla \(b\) po delení tromi ako \(z\). Číslo \(a\) chceme vymeniť s číslom, ktoré má zvyšok \(3 - z\) po delení tromi. V hornej polovici máme \(50\) párnych čísel, z nich z každého zvyšku máme aspoň \(16\) čísel (rozmyslite si to). Nechceme si z nich vybrať číslo \(2\), aby sme náhodou nedostali súčet \(3\) (jediný súčet, ktorý je deliteľný tromi a nie je to zložené číslo). Taktiež nechceme vyberať číslo z piateho riadku, aby sme si náhodou nepokazili súčet niekde inde. Každopádne, ostalo nám aspoň \(16 - 1 - 10 = 5\) čísel, ktoré majú zvyšok \(3 - z\). Vyberieme si ľubovoľné číslo z nich a vymeníme ho s číslom \(a\). Tak dostaneme v stĺpci \(s\) na hranici piateho a šiesteho riadku súčet čísel deliteľný tromi a zároveň väčší ako tri, a to je zložené číslo. Hornú polovicu sme si nepokazili, lebo v nej máme stále iba párne čísla. Celá tabuľka nám teda sedí a stačilo nám na to najviac \(25 + 10 = 35\) výmen.

Iné riešenie

Opíšeme ešte jeden spôsob, ako zaručiť na rozhraní dvoch polovíc súčty, ktoré sú zložené čísla. Tento spôsob pochádza z riešenia Uršule Márie Kossaczkej. Zakladá sa na tom, že pre každé párne číslo si predpíšeme práve jedno jedinečné nepárne číslo, ktoré s ním dá v súčte zložené číslo. V každom stĺpci spravíme nasledovné: označíme si (párne) číslo v piatom riadku ako \(y\) a (nepárne) číslo v šiestom riadku ako \(x\). Číslo \(y\) vymeníme s párnym číslom podľa nasledovnej tabuľky.

Tak vždy dostaneme v súčte na rozhraní piateho a šiesteho riadku zložené číslo. Jeho výhodou je, že nemusíme riešiť, či nám náhodou nevyjde súčet zrovna \(3\), alebo či si svojím ťahom nepokazíme nejaký predchádzajúci súčet.