7. Kečku Musím Schladiť vzorové riešenie

Úloha sa nás pýta, koľko rôznych čísel môžeme dostať ako súčet nejakej podmnožiny čísel¹, ktoré sú napísané na guľôčkach.

Úvodné pozorovania

Všetkých možných podmnožín je \(2^n\), takže určite nemôžeme dostať viac ako \(2^n\) rôznych súčtov. Toľko zároveň vieme dosiahnuť – ak budú na guľôčkach mocniny dvojky: \(2^0, 2^1, \dots, 2^{n-1}\), tak vieme dostať ľubovoľný súčet \(s\) od \(0\) do \(2^n-1\), a to tak, že vyberieme tie mocniny dvojky, ktoré sú vynásobené cifrou \(1\) v binárnom zápise \(s\).

Tiež vieme dostať malé počty súčtov – ak na guľôčkach bude \(k\) jednotiek a \(n-k\) núl, vieme získať práve všetky súčty od \(0\) do \(k\), kde \(0\leq k \leq n\).

Náročnejšie môže byť získať \(2^n-1\) rôznych súčtov. V tomto prípade musia byť všetky súčty rôzne, až na jednu dvojicu podmnožín, ktorá má rovnaký súčet. Ak by obe tieto podmnožiny obsahovali ten istý prvok (guľôčku), tak po jeho odobraní z oboch by sme dostali ďalšiu dvojicu podmnožín s rovnakým súčtom, čo nechceme. Podobne, ak by obe neobsahovali nejaký prvok, jeho pridaním do oboch by sme dostali ďalšiu dvojicu s rovnakým súčtom. Musí preto ísť o podmnožinu a jej doplnok (tie čísla, ktoré nie sú v prvej podmnožine). Napríklad funguje aj prípad, kedy jedno číslo je súčtom ostatných, napr. \(\{3, 4, 7\}\) dáva iba jednu dvojicu s rovnakým súčtom, a to \(3 + 4 = 7\).

Vyzerá to tak, že nám nič nebráni dostať ľubovoľný počet súčtov od \(1\) do \(2^n\). Poďme to dokázať!

Všimnime si, že pridaním ďalšieho prvku počet možných súčtov vzrastie z \(2^n\) na \(2^{n+1}\), čiže sa zdvojnásobí. Podmnožiny po pridaní prvku sú tie pred pridaním a tiež tie pred pridaním plus nový prvok, čo je tiež zhruba zdvojnásobenie, ale niektoré súčty môžu byť rovnaké.

Dôkaz

Budeme postupovať indukciou podľa \(n\) – počtu čísel/guľôčok. Ukážeme, že vieme dostať ľubovoľný počet rôznych súčtov od \(1\) do \(2^n\).

Pre \(n=1\), ak chceme \(1\) súčet vezmeme guľôčku s číslom \(0\), súčet každej podmnožiny je \(0\). Ak chceme \(2\) súčty, vezme guľôčku s číslom \(1\), súčty podmnožín sú \(0\) a \(1\).

Predpokladajme, že tvrdenie platí pre \(n\) a poďme dokázať, že pre \(n+1\) vieme získať \(m\) rôznych súčtov (pre ľubovoľné \(1 \leq m \leq 2^{n+1}\)). Prvky aj súčty budeme generovať nezáporné, takže najmenší dosiahnuteľný súčet bude \(0\) (určite ho vieme dostať aspoň ako súčet prázdnej množiny).

Ak \(m=2k\) je párne, tak si z indukčného predpokladu zostrojíme \(n\) guľôčok, z ktorých vieme získať \(k\) súčtov \(0 = s_1 < s_2 < \dots < s_k\). Na novú guľôčku napíšeme číslo \(s_k + 1 = a\). Všetky súčty s novou guľôčkou sú teraz väčšie ako všetky súčty bez nej, pretože nová guľôčka má dostatočne veľké číslo. Vieme získať \(2k\) súčtov \(0 = s_1 < s_2 < \dots < s_k < a + s_1 < a + s_2 < \dots < a + s_k\).

Ak \(m = 2k-1\) je nepárne, tak si opäť z indukčného predpokladu zostrojíme guľôčky, z ktorých vieme získať \(k\) súčtov \(0 = s_1 < s_2 < \dots < s_k\) (polovicu zaokrúhlenú nahor). Teraz však pridáme číslo, ktoré je rovné najväčšiemu súčtu \(s_k\), takže všetkých súčtov bude o jeden menej ako dvojnásobok: \(0 = s_1 < s_2 < \dots < s_k < s_k + s_2 < \dots < s_k + s_k\). Naozaj to funguje, keďže v tomto prípade \(1 \leq k \leq 2^n\) a \(s_k = s_k + s_1 = s_k + 0\).

Indukcia je týmto hotová, pretože vieme mať \(n+1\) guľôčok s ľubovoľným počtom súčtov od \(1\) do \(2^{n+1}\).

Týmto sme dokázali, že pre \(n\) guľôčok vieme dostať ľubovoľný počet rôznych súčtov podmnožín od \(1\) do \(2^n\).