Zadanie
Po tom, čo vedúci premrhali polhodinu debatovaním o tom, ako by sa mala vybrať trasa výletu, sa rozhodli, že by sa mali všetci spoločne zhodnúť na najbližšom postupe. A tak sa spoločne rozhodli, že rozhodnutie nechajú na náhodu pri hode Marekovými vysnívanými kockami.
Každá Marekova vysnívaná kocka má vrcholy v nejakom poradí očíslované číslami od \(1\) po \(8\) (každé z nich je v práve jednom vrchole každej kocky). Na každej stene je napísaný súčet čísel vo vrcholoch tej steny. Marekove vysnívané kocky sú však iba tie, ktoré majú na všetkých stenách prvočísla a navyše počet rôznych prvočísel na stenách je najväčší možný (spomedzi tých kociek, ktoré majú na stenách len prvočísla). Nájdite všetky neusporiadané1 šestice prvočísel, ktoré môžu byť na stenách Marekovej vysnívanej kocky.
Záleží iba na tom, ktoré číslo sa koľkokrát vyskytuje, a nie na konkrétnom rozložení čísel na kocke.↩
Vrcholy kocky máme očíslované len číslami do \(8\), z čoho ľahko vycítime, že prvočísla na stenách nemôžu byť veľmi veľké. Ako presne? Najväčšie číslo na stene kocky môže byť zjavne \(8+7+6+5\), čo je \(26\), teda väčšie prvočísla uvažovať nepotrebujeme. Podobne sa môžeme pozrieť na dolné ohraničenie: najmenšie číslo na stene môže byť \(1+2+3+4\), a teda \(10\). Čiže prvočísla, ktoré by sme teoreticky mohli dostať na Marekovej vysnívanej kocke, sú iba \(11\), \(13\), \(17\), \(19\) a \(23\).
Čo ďalej? Keď by ste sa chvíľu hrali a skúšali konštruovať Marekove kocky, možno by ste si všimli, že súčet čísel na protiľahlých stenách je vždy \(36\). Totiž, keď si vyberieme nejaké \(2\) protiľahlé steny kocky, tak každý vrchol kocky prislúcha práve jednej z nich. Takže keď pri jednej stene sčítavame nejaké \(4\) čísla spomedzi \(1,2,3, \ldots 8\), tak pri tej protiľahlej sčítavame zvyšné štyri. Čiže súčet čísel na týchto protiľahlých stenách je rovný súčtu všetkých čísel pri vrcholoch kocky, čo je práve \(\frac{8\cdot9}{2}=36\). Máme \(23+13=36\) a \(19+17=36\), teda tieto dvojice prvočísel musia byť na kocke oproti sebe. Avšak \(36-11=25\), čo nie je prvočíslo, a preto sa číslo \(11\) nemôže objaviť na Marekovej vysnívanej kocke.
O Marekovej vysnívanej kocke tiež vieme, že je na nej najviac rôznych prvočísel ako sa dá. Zatiaľ sme zistili, že najviac by ich mohlo byť \(4\) a možné neusporiadané šestice by boli \(13,23,13,23,17,19\) alebo \(13,23,17,19,17,19\) (keďže každú z dvojíc \(13,23\) a \(17,19\) chceme aspoň raz a potrebujeme spolu tri takéto dvojice). Nakoniec sa ukáže, že obe tieto šestice sa na Marekovej kocke dajú dosiahnuť, a to napríklad tak ako na obrázkoch nižšie.
Ako si zjednodušiť hľadanie
Hľadanie vhodného rozloženia čísel do vrcholov si môžeme zjednodušiť nasledujúcou úvahou: Na každej strane kocky chceme mať nepárne číslo, čo môžeme dosiahnuť buď tak, že sčítame tri párne a jedno nepárne, alebo tri nepárne a jedno párne. Povedzme, že máme stenu, ktorej tri vrcholy majú párne číslo a jeden má nepárne. Tým ale dostaneme ďalšie dve steny s aspoň dvoma párnymi číslami vo vrcholoch, a teda musia mať vo vrcholoch práve tri párne čísla. Tri sme ale už použili a zostalo nám iba jedno, takže musí byť vo vrchole, ktorý majú tieto dve steny spoločný (obrázok vľavo). Zvyšné vrcholy tak majú nepárne čísla. Preto keď si kocku vhodne otočíme, dostaneme situáciu ako na obrázku vpravo. (Rovnaký výsledok by sme dostali aj keby sme začali stenou s troma vrcholmi s nepárnym číslom.) Potom keď si rozložíme napríklad párne čísla, nemalo by byť ťažké doplniť tie nepárne, aby vyšlo čo potrebujeme.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.