Zadania 3. zimného kola - Ahojte, Rieškari! Skončilo sa nám druhé letné kolo, a teda prichádzajú zadania tretieho kola aj s pokračovaním príbehu! Môžete ich nájsť v sekcii zadania máte na nich čas do 26. … Prejsť na článok
×4. príklad - Vzorové riešenie
Zadanie
Šiesti strážcovia múzea musia v noci strážiť múzeum, ale chcú aj spať. Počas 12 hodinovej noci, ktorá trvá od 19:00 do 7:00, musia v každom momente múzeum strážiť aspoň dvaja strážci.
Strážci však majú špeciálne požiadavky na ich spánok.
Alenka: Ja chcem spať 10 hodín, a to bez prerušenia.
Baška: Ja chcem spať 7 hodín bez prerušenia.
Chiarka: Ja chcem dokopy spať 9 hodín, ale viac po polnoci ako pred polnocou.
Danko: Ja chcem spať 5 hodín, ale viac pred polnocou ako po nej.
Ela: Ja chcem spať 9 hodín bez prerušenia.
Fredo: Ja chcem spať 8 hodín bez prerušenia.
Okrem toho sú strážcovia leniví a striedať sa chcú iba po celých hodinách.
Koľko rôznych časových plánov na noc môžu mať?
Vzorové riešenie
Začnime pozorovaním, že strážcovia musia celkovo spať aspoň 10+7+9+5+9+8=48 hodín, a strážiť musia celkovo aspoň 24 hodín, lebo noc trvá 12 hodín a vždy strážia aspoň dvaja vedúci. Spolu je to 48+24=72 hodín. Celkovo má ale každý iba 12 hodín na spanie a stráženie, to je dokopy 6\cdot 12=72 hodín času. Z toho vyplýva, že nemajú čas nazvyš, teda musia dokopy spať presne 48 hodín a strážiť presne 24 hodín. Vždy teda strážia presne 2 strážcovia a ostatní spia. Zároveň každý spí iba toľko, koľko minimálne podľa zadania potrebuje, a inak musí strážiť.
Označme si strážcov podľa prvého písmena ich mena, teda A, B, C, D, E, F. Úlohu si vieme znázorniť tabuľkou do ktorej si zapíšeme, ktorý strážca kedy spí a kedy stráži, keď už to budeme vedieť s istotou. Stĺpce sú označené číslami podľa začínajúceho času celej hodiny (napríklad stĺpec 19 hovorí o čase 19:00 - 20:00). Každý riadok zobrazuje aktivitu jedného strážcu, modrá značí, že vedúci tú hodinu spí, a zelená, že tú hodinu stráži.
A musí spať 10 hodín bez prerušenia, čo nám jej spánok veľmi obmedzuje. Ak by začala spať hneď o 19, tak by potom už od 5 musela strážiť (lebo sme ukázali, že nemôže spať viac, ako potrebuje). Ak by sa zobudila čo najneskôr, až na konci, išla by spať o 21. Vždy teda musí spať v hodinách 21 až 4. Rovnako zistíme, že B musí začať spať najneskôr od hodiny 0 a strážiť nezačne skôr ako v hodine 2. Preto v hodinách 0 a 1 musí isto spať. Podobne je to pri ostatných, ktorí musia spať bez prerušenia. E musí spať v hodinách 22 až 3, F musí spať v hodinách 23 až 2.
Vidíme, že teraz v hodinách 0 a 1 už spia 4 strážcovia (A, B, E, F), takže C a D, ktorí vtedy nespia, musia strážiť.
C musí zo svojich 9 hodín spať po polnoci viac ako pred ňou, teda aspoň 5. Keďže po polnoci je iba 7 hodín a vieme, že v hodinách 0 a 1 už stráži, takže musí spať vo všetkých ostatných hodinách, 2 a neskôr.
Teraz v hodine 2 už spia 4 strážcovia (A, C, E, F), takže B a D musia vtedy strážiť. Keďže B musí spať 7 hodín bez prerušenia a spí v hodinách 0 a 1, musí spať aj vo všetkých 7 hodinách pred 2, a potom musí celý čas strážiť.
V hodine 23 už tiež spia 4 strážovia (A, B, E, F), takže zvyšní strážcovia, teda C a D, musia vtedy strážiť. Ostatné hodiny už musí C spať, inak nenaspí 9 hodín, ktoré zo zadania potrebuje.
V hodine 22 už spia 4 strážcovia (A, B, C, E), takže D a F musia vtedy strážiť. F musí spať 8 hodín bez prerušenia, a spí už v hodine 23, takže všetkých 8 hodín od 23 musí spať tiež. Vo všetkých ostatných hodinách musí strážiť.
D musí spať 5 hodín a z toho viac pred polnocou ako po polnoci, takže musí spať aspoň 3 hodiny pred polnocou. My už ale vieme, že v 2 z nich stráži, takže vo zvyšných 3 musí spať.
Potom vieme, že v hodine 21 spia 4 strážcovia (A, B, C, D), takže s F musí strážiť E. Keďže musí spať 9 hodín bez prerušenia a spí v hodine 22, musí spať vo všetkých hodinách od 22 a strážiť vo všetkých hodinách pred 22.
V hodinách 19 a 20 už strážia E aj F, a vždy musia strážiť práve 2 strážcovia, takže A musí vtedy spať. Potom musí v hodinách 5 a 6 strážiť, aby nespala viac ako 10 hodín.
V hodine 3 aj 4 spia strážcovia A, C, E, F, takže vtedy s B musí strážiť aj D. Keďže D musí spať 5 hodín a zatiaľ spal iba 3, zvyšné 2 hodiny musí spať.
Teraz už máme celú tabuľku vyplnenú, a vždy sme do nej vypĺňali iba to, čo nemohlo byť inak, aby bolo splnené zadanie. Takže je iba 1 riešenie, ktoré sme tu našli:
