Zadanie
Astronauti Matthews a Patricks sa spokojní vrátili do lode. Chceli sa venovať svojej ďalšej úlohe – robiť nejaký výskum na marťanských formách života. Pristáli teda s loďou pri jednom štvornohom domorodcovi a požiadali ho, aby si nastúpil. Štyri nohy, štyri rohy, štyri oči. Vyzerali aj stavbári takto? To už si udatní astronauti nepamätali, domorodec im však nerozumel, tak sa ho rozhodli nalákať na čokoládu predtým, než ho spútajú a násilím dotlačia do lode.
Čokoláda značky Zem je tvorená tabuľkou \(4 \times 8\) štvorčekov. Podľa medziplanetárnej smernice spoločnosti Zem Inc., ktorá čokoládu produkuje, sa smie podávať mimozemským bytostiam len vo forme štvorcov \(1 \times 1,\, 2 \times 2,\, 3 \times 3\) a \(4 \times 4\) štvorčeky. Matthews a Patricks sa rozhodli, že čokoládu rovno rozdelia na niekoľko povolených kúskov. Koľko takých štvorcov mohli získať, ak rozdelili celú čokoládu? Nájdite všetky možné počty.
Keď rozdeľujeme tabuľku čokolády na povolené štvorčeky, musí platiť, že súčet obsahov rozdelených kúskov je rovnaký ako obsah celej čokolády. Platí teda nasledovná rovnica:
\[4^2\cdot a + 3^2\cdot b + 2^2\cdot c + 1^2\cdot d = 4 \cdot 8\] \[16 a + 9 b + 4 c + 1 d = 32\]
Kde \(a\) je počet \(4\times 4\) štvorcov, \(b\) je počet \(3\times 3\) štvorcov, \(c\) je počet \(2\times 2\) štvorcov a \(d\) je počet \(1\times 1\). Potom si zaveďme \(S = a + b + c + d\), čo bude náš počet rôznych štvorcov na ktorý sa môže čokoláda rozdeliť. Teraz si vypíšeme všetky možnosti, ktoré splňujú našu rovnicu, postupne od najväčších kúskov a potom ich postupne zmenšujeme.
| * | * | * | * | ||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(a\) | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| \(b\) | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| \(c\) | 0 | 1 | 0 | 4 | 3 | 2 | 1 | 0 | 1 | 0 | 3 | 2 | 1 | 0 | 5 | 4 | 3 | 2 | 1 | 0 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| \(d\) | 0 | 3 | 7 | 0 | 4 | 8 | 12 | 16 | 1 | 5 | 2 | 6 | 10 | 14 | 3 | 7 | 11 | 15 | 19 | 23 | 0 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 |
| \(S\) | 2 | 6 | 9 | 5 | 8 | 11 | 14 | 17 | 5 | 8 | 7 | 10 | 13 | 16 | 9 | 12 | 15 | 18 | 21 | 24 | 8 | 11 | 14 | 17 | 20 | 23 | 26 | 29 | 32 |
Avšak je podstatné si uvedomiť, že nie všetky možnosti sa dajú skutočne skonštruovať. Napríklad vieme, že ak budeme mať \(3\times 3\) štvorček čokolády, budeme musieť mať aspoň tri \(1\times 1\), inak by sme čokoládu nevedeli rozdeliť.
Keďže teda musí platiť \(b \le \frac{d}{3}\) , vieme, že možnosti označené * v tabuľke nie sú možné a preto ich nebudeme brať do úvahy. Špeciálne sa pozrieme aj na prípad \(a = 1\), \(b = 1\), \(c = 1\), a \(d = 3\). Keď od čokolády najprv oddelíme \(4\times 4\) štvorec a potom \(3\times 3\) štvorec, získame jeden z dvoch nižšie uvedených zvyškov, kde vidíme, že neexistuje miesto pre \(2\times 2\), preto túto možnosť tiež nebudeme brať do úvahy.
Z rovnice získavame tieto rôzne počty, na ktoré vieme čokoládu rozdeliť: \[S \in \{ 2 ; 5 ; 8 ; 9 ; 10 ; 11 ; 12 ; 13 ; 14 ; 15 ; 16 ; 17 ; 18 ; 20 ; 21 ; 23 ; 24 ; 26 ; 29 ; 32\}\] Aby sme dokázali, že tieto počty sú možné, môžeme buď nakresliť konštrukciu každého rozdelenia, alebo ukázať nejakým iným spôsobom, že existujú. My sme sa rozhodli pozrieť na rôzne rozdelenia \(4\times 4\) štvorca. Tie sme získali tak, že sme išli od najväčších štvorcov a doplňovali potom menšie.
Teraz získame možné rozdelenia \(4\times 8\) tabuľky čokolády tak, že vezmeme 2 ľubovoľné rozdelenia \(4\times 4\) štvorca a dáme ich dokopy. Napríklad ak vieme rozdeliť \(4\times 4\) štvorec na \(s_1 = 1\) ale aj na \(s_2 = 8\) tak potom \(4\times 8\) tabuľku vieme rozdeliť na \(S = s_1 + s_2 = 9\) kúskov. Dole môžeme vidieť všetky možnosti, ktoré vieme získať kombináciou dvoch \(4\times 4\) štvorcov.
| \(s_1 \backslash s_2\) | 1 | 4 | 7 | 8 | 10 | 13 | 16 | |
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 5 | 8 | 9 | 11 | 14 | 17 | |
| 4 | 5 | 8 | 11 | 12 | 14 | 17 | 20 | |
| 7 | 8 | 11 | 14 | 15 | 17 | 20 | 23 | |
| 8 | 9 | 12 | 15 | 16 | 18 | 21 | 24 | |
| 10 | 11 | 14 | 17 | 18 | 20 | 23 | 26 | |
| 13 | 14 | 17 | 20 | 21 | 23 | 26 | 29 | |
| 16 | 17 | 20 | 23 | 24 | 26 | 29 | 32 |
Z toho sme dokázali, že existujú rozdelenia:
\[S \in \{ 2 ; 5 ; 8 ; 9 ; 11 ; 12 ; 14 ; 15 ; 16 ; 17 ; 18 ; 20 ; 21 ; 23 ; 24 ; 26 ; 29 ; 32\}\]
Zostávajú nám teda rozdelenia \(S = 10\) a \(S = 13\). To už dokážeme konkrétnymi konštrukciami.
Poznámka: V tabuľke máme možnosť, ktorá sa nedá skonštruovať, konkrétne \(a = 0\), \(b = 1\), \(c = 5\), a \(d = 3\). Avšak táto možnosť má \(S = 9\), čo sme si inou konštrukciou dokázali, že môže existovať.
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ť.