7. príklad - Vzorové riešenie
Zadanie
Elektrická skriňa má vnútri niekoľko procesorov usporiadaných do n \geq 2 riadkov tvoriacich pravidelný trojuholník – postupne v riadkoch 1, 2,\dots , n procesorov. Chceme cez všetky procesory viesť kábel (lomenú čiaru) tak, že spojíme vždy dva susedné procesory. Určte, pre ktoré n sa to dá spraviť tak, že v žiadnom procesore nejdeme rovno.
- Dá sa to pre n = 3?
- n = 4?
- n = 5 a viac?
Vzorové riešenie
Príklad budeme riešiť najprv pre n\geq4. Prvé pozorovanie, ktoré spravíme je, že trojuholník má tri vrcholy, pričom čiara, ktorou sa snažíme pokryť všetky bodky z ktorých sa trojuholník skladá má iba dva konce. To znamená, že existuje vrchol trojuholníka, v ktorom čiara nezačína, ale ním iba prechádza. Tým, že v ňom nezačína tak obe vyznačené úsečky musia byť súčasťou kľukatice.
Ďalej však vieme, že cez žiadny bod čiara neprechádza rovno. To však znamená, že kľukatica musí pokračovať z oboch bodov po modrých čiarach. Ak by pokračovala po oboch, tak by sa nám uzavrela, čo nemôže.
V tomto momente si však musíme dať pozor, lebo to ešte nie je koniec riešenia. Doteraz sme nikde v riešení neukázali, že by kľukatica musela naozaj začínať v tých dvoch zvyšných rohoch. Zatiaľ sme iba ukázali, že existuje vrchol v ktorom nezačína. Ešte stále sa nám môže stať, že by začínala v ľubovoľnom z modrých políčok.
Nech teda začína napríklad v tom tyrkysovom. To by však znamenalo, že už máme iba jeden voľný koniec kľukatice. Preto určite existuje roh v ktorom kľukatica nezačína. Potom rovnakým argumentom ako v prvom prípade dostávame, že aspoň jedno z modrých políčok musí byť koncom kľukatice.
Tým sa dostávame k poslednému rohu a keďže už nemáme voľné konce, tak v ňom dostaneme cyklus a teda pre trojuholník, ktorý má 3 a viac vrstiev sa nám kľukaticu nakresliť nepodarí.
Povšimnime si však, že pre trojuholník o veľkosti strany 3 nevieme ostatné rohy doriešiť rovnako ako v predchádzajúcom prípade, lebo na to jednoducho nie je dosť miesta. Avšak ľahko nahliadneme, že kľukatica vie buďto ísť hore, alebo dole, takže aspoň jeden roh ostane nepokrytý.
Komentár
S príkladom ste sa väčšinou pekne popasovali. Hlavný problém bol, že väčšina z vás si neuvedomilo, že sme v riešení priamo neukázali, že kľukatica musí začínať v dákom z tých dvoch rohov a že treba ten príklad doriešiť. Niektorým sa úplne nepodarilo všimnúť si, že problematický je roh a snažili sa vyskúšať niekoľko kľukatíc a tým ukázať, že to nejde. Ak zvolíte takýto prístup, je potreba naozaj dôsledne ukázať, že sme cestu nemohli viesť iným spôsobom.