Zadanie
Grafik Peter Senov bol medzitým na svojej pravidelnej návšteve u kolegu z Geometrie. Aj keď krajina sa pod vládou Al-Gebry zmenila, na rozhovore dvoch umelcov to nebolo badať. Petrov priateľ Feuer Sebastian mal ako vždy veľmi podnetné otázky.
„Pozri, Peter, je všeobecne známe, že keď máš v rovine rozsypanú množinu čísel \(\{1, 2, \dots, 30\}\), tak jej podmnožina je pekná, ak sa v nej nenachádza žiadne číslo zároveň s jeho trojnásobkom. V čom je však ozajstné umenie, je vedieť nájsť najväčšiu peknú podmnožinu. Koľko najviac prvkov môže mať pekná podmnožina? Koľko rôznych pekných podmnožín s týmto počtom prvkov existuje?“
Na začiatok rozdelíme našu množinu \(\{1, \dots, 30\}\) na disjunktné (navzájom rôzne) podmnožiny tak, aby každá podmnožina obsahovala rastúcu postupnosť takú, že každý jej člen je \(3\)-násobkom predchádzajúceho, teda \[\begin{gathered} \{1 \to 3 \to 9 \to 27\}, \{2 \to 6 \to 18\}, \{4 \to 12\}, \{5 \to 15\}, \{7 \to 21\}, \{8 \to 24\}, \{10 \to 30\},\\ \{11\}, \{13\}, \{14\}, \{16\}, \{17\}, \{19\}, \{20\}, \{22\}, \{23\}, \{25\}, \{26\}, \{28\}, \{29\}.\end{gathered}\]
Všimnime si, že ak do peknej podmnožiny pridáme nejaký člen, ktorý je v našom rozdelení na podmnožiny v množine samostatne, nezabráni nám to pridať ľubovoľné iné číslo z množiny \(\{1, \dots, 30\}\). Teda nakoľko máme za cieľ dostať do peknej podmnožiny čo najviac čísel, takéto čísla tam budú patriť všetky.
Pozrime sa ďalej na podmnožiny z nášho rozdelenia, ktoré sú po dvojiciach. Ak vyberieme jedno z nich do peknej podmnožiny, druhé tam pri dodržaní podmienok zadania byť nesmie. Teda do najväčšej peknej podmnožiny patrí práve jedno z nich.
Ak zoberieme \(3\)-prvkovú podmnožinu, tak v prípade, že by sme do peknej podmnožiny vybrali stredné z čísel, zabránili by sme zvyšným dvom číslam, aby boli v peknej podmnožine. Ak však vyberieme krajné dve, tento problém nenastane a môžeme ich tam pridať dve namiesto jedného, čo je optimálne, nakoľko chceme maximalizovať ich počet.
V prípade \(4\)-prvkovej množiny, ak vyberieme ľavé krajné číslo, nemôžeme vybrať druhé zľava, ale tretie alebo štvrté už áno, avšak najviac jedno z nich, nakoľko pridanie ďalšieho vedie ku porušeniu pravidla o trojnásobkoch zo zadania. Rovnaká úvaha ide použiť aj na ostatné pozície ako počiatok našich úvah a teda z takejto podmnožiny do peknej podmnožiny vieme vybrať najviac 2 čísla. A teda tak aj spravíme.
Väčšie podmnožiny nášho delenia na podmnožiny už nemáme a teda vieme usúdiť, že najväčšia pekná podmnožina musí mať nutne \(13 \cdot 1 + 5 \cdot 1 + 1 \cdot 2 + 1 \cdot 2 = 22\) prvkov.
Poďme sa ešte pozrieť na to, koľko je takýchto podmnožín. Ak je číslo v našom delení osamostatnené, tak v tejto množine nutne bude. Ak sú po dvojiciach, vždy tam bude práve jedno z nich (teda sa tieto pekné podmnožiny delia na dve vetvy). Ak sú po trojiciach, existuje práve jeden vhodný výber do peknej podmnožiny. V prípade, že sú v podmnožine nášho delenia \(4\) čísla, sú práve 3 možnosti, ako vybrať prvky do peknej podmnožiny (konkrétne \(1.+3.\), \(1.+4.\) a \(2.+4.\)). Nakoľko sú tieto výbery na sebe navzájom nezávislé, počet pekných podmnožín sa dá spočítať ako súčin počtu výberov z nášho rozdelenia množiny na podmnožiny a to ako \(2^5 \cdot 3 =96\).
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ť.