8. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Dvere do najvyššej veže majú 47 zamknutých zámkov v rade za sebou. Na týchto dverách sú aj kľučky. Každá kľučka môže byť stlačená, čím zmení stav dvoch zámkov, na ktoré je napojená, zo zamknutých na odomknuté a naopak. Každá kľučka je napojená na práve dva susedné zámky a každý zámok je napojený na aspoň jednu kľučku. Nájdite aspoň jedno také ponapájanie pri ktorom sa nedá otvoriť viac ako 32 zámkov. Dalo by sa také nájsť aj pre 31? Ak áno, nájdite aspoň jedno a ak nie, zdôvodnite prečo také nie je.

Vzorové riešenie

Opravovali: Danko, ViktorB

Pre ľubovoľné usporiadanie kľučiek medzi zámkami si môžeme všimnúť, že zámky sú rozdelené do niekoľkých súvislých skupín veľkosti aspoň dva - medzi každými dvoma susednými zámkami v ľubovoľnej takejto skupine je kľučka, no medzi dvoma susednými zámkami z rôznych skupín sa žiadna kľučka nenachádza. To znamená, že tieto skupiny sa navzájom neovplyvňujú, teda ak stlačíme ľubovoľnú kľučku, tak dva zámky, ktoré zmenia svoj stav, budú patriť do tej istej skupiny.

Pokiaľ je v skupine párny počet zámkov, dajú sa jednoducho otvoriť všetky tak, že stlačíme každú druhú kľučku počnúc prvou. Týmto každý zámok prepneme raz, teda otvoríme.

Teraz ukážme, že v skupine s nepárnym počtom zámkov vždy vieme otvoriť najviac všetky zámky okrem jedného. Rovnako ako minule prepnime každú druhú kľučku počnúc prvou. Ostane nám na konci jeden neprepnutý zámok, lebo poslednú kľučku neprepneme.

Pozrime sa na to, ako sa nám môže meniť počet odomknutých zámkov. Keď prepneme ľubovoľnú kľučku, nastane jedna z týchto situácií:
  1. Ak boli zámky pri tejto kľučke oba zamknuté, kľučka ich odomkne a počet odomknutých zámkov sa zvýši o dva
  2. Ak boli zámky pri tejto kľučke oba odomknuté, kľučka ich zamkne a počet odomknutých zámkov sa zníži o dva
  3. Ak bol jeden zámok pri tejto kľučke odomknutý a jeden zamknutý, kľučka iba vymení ktorý z nich je zamknutý - počet odomknutých zámkov sa nezmení

Teraz si môžeme všimnúť, že nech sa stane akákoľvek z týchto vecí, počet zámkov sa zmení o párne číslo. A keďže na začiatku je odomknutých zámkov v skupine nula, teda tiež párny počet, tak odomknutých zámkov bude párny počet vždy. To znamená, že sa nám nikdy nemôže podariť odomknúť celý nepárny počet zámkov. Ukázali sme teda, že pri nepárnom počte zámkov vždy vieme odomknúť aspoň všetky až na jeden zámok, ale nikdy nie všetky.

Teraz už vieme ľahko vypočítať, koľko zámkov sa nedá otvoriť. Je ich práve toľko, koľko je nepárnych skupín zámkov, pretože v každej z nich jeden zámok nemôžeme otvoriť. A z ostatných skupín vieme otvoriť všetky zámky, lebo sú párne. Najmenšia nepárna skupina má veľkosť tri, pretože každá skupina musí mať veľkosť aspoň dva. Teda najviac nepárnych skupín, koľko môžeme vytvoriť, je 47 \div 3 = 15 (so zvyškom 2). To znamená, že najmenej 47-15 = 32 zámkov vieme otvoriť vždy a teda neexistuje rozostavenie, pri ktorom by sa dalo otvoriť zámkov iba 31. Zároveň máme príklad stavu, pri ktorom sa dá odomknúť iba 32 zámkov (existuje v ňom 47-32=15 nepárnych skupín): skladá sa z pätnástich skupín veľkosti tri a jednej skupiny veľkosti dva.

Komentár

Často sme strhávali body za nedostatočné zdôvodnenie toho, prečo sa v párnych skupinách dajú všetky zámky odomknúť, a prečo sa v nepárnych dajú odomknúť práve všetky až na jeden. Tieto kroky sme nepovažovali za samozrejmé.