7. príklad - Vzorové riešenie
Kategórie:
5
6
7
8
9
Zadanie
Kubo sa hral takúto hru. Hrací plán má tvar kruhu, ktorý je rozdelený na 10 častí. V každej časti je 9 cukríkov. V jednom ťahu vieme presunúť 1 cukrík z jednej časti do susednej. Za susedné považujeme tie časti, ktoré sa dotýkajú aspoň jedným bodom. Kubo sa s Maxom stavil, že keď presunie všetky cukríky do jednej časti na presne 2020 ťahov, môže zjesť všetky cukríky, ktoré boli na plániku. Maxo chce vyhrať stávku, ale nevie si s tým poradiť. Dokáže, bez ohľadu na rozdelenie plánu, vždy splniť Kubovu podmienku?
Príklady rozdelenia na 4 časti:
Vzorové riešenie
Opravovali: gabrielaS, lámač, martinK
Riešenie:
Odpoveď na otázku v zadaní sa pokúsime zistiť tak, že sa budeme snažiť nájsť konkrétny protipríklad rozdelenia, v ktorom Maxo nedokáže vyhrať stávku. Ak sa nám ho podarí nájsť, tak určite bude záležať na rozdelení plániku. V tom prípade nám stačí ukázať, že existuje také rozdelenie plánu, pre ktoré nemôže byť Kubova podmienka splnená.
Predstavme si plánik, v ktorom je 9 menších častí umiestnených v kruhu tak, že sa dotýkajú iba poslednej desiatej časti. To znamená, že sa nachádzajú vo vnútri desiatej časti, tak ako na obrázku 1. Desiata časť sa teda dotýka všetkých zvyšných deviatich častí. Všimnime si, že žiadne tri časti sa všetky medzi sebou navzájom nedotýkajú. Preskúmajme, v ktorej časti môžu na konci skončiť všetky cukríky. Keďže plán je symetrický, stačí sa pozrieť na ľubovoľnú z deviatich vnorených častí a plus na desiatu centrálnu časť.
Obrázok 1: Rozdelenie plániku na 10 častí
Ak by sme sa rozhodli zhromaždiť cukríky na centrálnej časti, 9 cukríkov tam už máme od začiatku. Zvyšných 81 cukríkov tam musíme postupne v jednotlivých ťahoch popresúvať. Keďže centrálna časť susedí so všetkými zvyšnými časťami plánika, každý cukrík tam dokážeme dostať na jeden ťah. To znamená, že potrebujeme najmenej 81 ťahov na to, aby sme tam z jednotlivých deviatich zvyšných častí presunuli všetky cukríky.
V druhom prípade zhromažďujeme cukríky v jednej z vnorených častí. Prvých 9 cukríkov sa už v danej časti nachádza. Ďalších 9 je hneď vo vedľajšej centrálnej časti a každý z nich vieme dostať do zvolenej cieľovej časti na jeden ťah. Okrem nich je v zvyšných ôsmich vnorených častiach po 9 cukríkov, ktoré najskôr musíme po jednom presunúť do centrálnej časti a až následne do nami zvolenej časti, v ktorej sa cukríky zhromažďujú. To znamená, že každý z týchto 8 \cdot 9 = 72 cukríkov budeme presúvať na minimálne dva ťahy. Dokopy teda potrebujeme minimálne 9 \cdot 1 + 72 \cdot 2 = 153 ťahov na to, aby sme presunuli cukríky do zvolenej vnorenej časti.
Všimnime si, že čísla 81 aj 153 sú obe nepárne. Dozvedeli sme sa, že minimálny počet ťahov potrebných na presunutie všetkých cukríkov do ľubovoľnej z desiatich častí bude vždy nepárny. Zároveň však vieme, že Maxo chce umiestniť všetky cukríky do jednej časti na 2020 ťahov, čo je párny počet ťahov. Ako vieme zmeniť počet ťahov potrebných na umiestnenie všetkých cukríkov v jednej časti z nepárneho počtu na párny?
Ak máme určité usporiadanie cukríkov, vieme jeden z cukríkov posúvať istý počet ťahov tak, že nakoniec ho dostaneme do tej istej časti, v ktorej bol na začiatku tohto usporiadania. Cukrík, ktorý presunieme do istej časti, z nej musíme aj dostať naspäť, aby sme nakoniec dostali počiatočné usporiadanie. Z toho vyplýva, že pokiaľ sa v každom bode dotýkajú maximálne dve časti, budeme potrebovať párny počet ťahov. Pre naše rozdelenie plániku to teda vieme spraviť iba na párny počet ťahov.
Preto nedokážeme zmeniť počet ťahov z nepárneho minimálneho počtu ťahov na párny počet tak, aby sme mali všetky cukríky v jednej oblasti. Tým sme ukázali, že pre náš plánik Maxo nedokáže presunúť všetky cukríky do jednej časti na 2020 ťahov. Preto nedokáže, bez ohľadu na rozdelenie plánu, splniť Kubovu podmienku.
Toto je samozrejme len jeden konkrétny protipríklad. Pozorný čitateľ si určite všimol, že existuje množstvo podobných plánikov, na ktorých Maxo nedokáže vyhrať Kubovu stávku. Medzi odovzdanými riešeniami sa často vyskytovalo rozdelenie plániku na desať častí pomocou deviatich paralelných čiar, alebo rozdelenie plániku pomocou sústredných kružníc. Čo majú všetky tieto rozdelenia spoločné? Každý z nich neobsahuje ani jeden bod, v ktorom sa dotýkajú 3 alebo viacej častí. Pokiaľ by sa totiž na plániku vyskytovali 3 navzájom sa dotýkajúce časti, bolo by možné cukrík presunúť postupne medzi takýmito troma časťami na tri ťahy, pričom by sme nakoniec mali cukrík v časti, v ktorej bol na začiatku tohto presunu. To znamená, že by sme týmto spôsobom vedeli zmeniť nepárny celkový počet ťahov na párny. Vtedy by Maxo dokázal docieliť presunutie všetkých cukríkov na 2020 ťahov do jednej časti.
Odpoveď na otázku v zadaní sa pokúsime zistiť tak, že sa budeme snažiť nájsť konkrétny protipríklad rozdelenia, v ktorom Maxo nedokáže vyhrať stávku. Ak sa nám ho podarí nájsť, tak určite bude záležať na rozdelení plániku. V tom prípade nám stačí ukázať, že existuje také rozdelenie plánu, pre ktoré nemôže byť Kubova podmienka splnená.
Predstavme si plánik, v ktorom je 9 menších častí umiestnených v kruhu tak, že sa dotýkajú iba poslednej desiatej časti. To znamená, že sa nachádzajú vo vnútri desiatej časti, tak ako na obrázku 1. Desiata časť sa teda dotýka všetkých zvyšných deviatich častí. Všimnime si, že žiadne tri časti sa všetky medzi sebou navzájom nedotýkajú. Preskúmajme, v ktorej časti môžu na konci skončiť všetky cukríky. Keďže plán je symetrický, stačí sa pozrieť na ľubovoľnú z deviatich vnorených častí a plus na desiatu centrálnu časť.
Ak by sme sa rozhodli zhromaždiť cukríky na centrálnej časti, 9 cukríkov tam už máme od začiatku. Zvyšných 81 cukríkov tam musíme postupne v jednotlivých ťahoch popresúvať. Keďže centrálna časť susedí so všetkými zvyšnými časťami plánika, každý cukrík tam dokážeme dostať na jeden ťah. To znamená, že potrebujeme najmenej 81 ťahov na to, aby sme tam z jednotlivých deviatich zvyšných častí presunuli všetky cukríky.
V druhom prípade zhromažďujeme cukríky v jednej z vnorených častí. Prvých 9 cukríkov sa už v danej časti nachádza. Ďalších 9 je hneď vo vedľajšej centrálnej časti a každý z nich vieme dostať do zvolenej cieľovej časti na jeden ťah. Okrem nich je v zvyšných ôsmich vnorených častiach po 9 cukríkov, ktoré najskôr musíme po jednom presunúť do centrálnej časti a až následne do nami zvolenej časti, v ktorej sa cukríky zhromažďujú. To znamená, že každý z týchto 8 \cdot 9 = 72 cukríkov budeme presúvať na minimálne dva ťahy. Dokopy teda potrebujeme minimálne 9 \cdot 1 + 72 \cdot 2 = 153 ťahov na to, aby sme presunuli cukríky do zvolenej vnorenej časti.
Všimnime si, že čísla 81 aj 153 sú obe nepárne. Dozvedeli sme sa, že minimálny počet ťahov potrebných na presunutie všetkých cukríkov do ľubovoľnej z desiatich častí bude vždy nepárny. Zároveň však vieme, že Maxo chce umiestniť všetky cukríky do jednej časti na 2020 ťahov, čo je párny počet ťahov. Ako vieme zmeniť počet ťahov potrebných na umiestnenie všetkých cukríkov v jednej časti z nepárneho počtu na párny?
Ak máme určité usporiadanie cukríkov, vieme jeden z cukríkov posúvať istý počet ťahov tak, že nakoniec ho dostaneme do tej istej časti, v ktorej bol na začiatku tohto usporiadania. Cukrík, ktorý presunieme do istej časti, z nej musíme aj dostať naspäť, aby sme nakoniec dostali počiatočné usporiadanie. Z toho vyplýva, že pokiaľ sa v každom bode dotýkajú maximálne dve časti, budeme potrebovať párny počet ťahov. Pre naše rozdelenie plániku to teda vieme spraviť iba na párny počet ťahov.
Preto nedokážeme zmeniť počet ťahov z nepárneho minimálneho počtu ťahov na párny počet tak, aby sme mali všetky cukríky v jednej oblasti. Tým sme ukázali, že pre náš plánik Maxo nedokáže presunúť všetky cukríky do jednej časti na 2020 ťahov. Preto nedokáže, bez ohľadu na rozdelenie plánu, splniť Kubovu podmienku.
Toto je samozrejme len jeden konkrétny protipríklad. Pozorný čitateľ si určite všimol, že existuje množstvo podobných plánikov, na ktorých Maxo nedokáže vyhrať Kubovu stávku. Medzi odovzdanými riešeniami sa často vyskytovalo rozdelenie plániku na desať častí pomocou deviatich paralelných čiar, alebo rozdelenie plániku pomocou sústredných kružníc. Čo majú všetky tieto rozdelenia spoločné? Každý z nich neobsahuje ani jeden bod, v ktorom sa dotýkajú 3 alebo viacej častí. Pokiaľ by sa totiž na plániku vyskytovali 3 navzájom sa dotýkajúce časti, bolo by možné cukrík presunúť postupne medzi takýmito troma časťami na tri ťahy, pričom by sme nakoniec mali cukrík v časti, v ktorej bol na začiatku tohto presunu. To znamená, že by sme týmto spôsobom vedeli zmeniť nepárny celkový počet ťahov na párny. Vtedy by Maxo dokázal docieliť presunutie všetkých cukríkov na 2020 ťahov do jednej časti.