Anketa - Ahoj Rieškar, stalo sa ti niekedy, že si nerozumel zadaniam? Chcel by si v lete prísť na denný tábor? Sú nejaké akcie, ktoré by si chcel, aby sme robili častejšie? … Prejsť na článok
×10. príklad - Vzorové riešenie
Zadanie
Subjekt je zabezpečený najvyšším stupňom ochrany a k prístupu je tak potrebných niekoľko hesiel. Máme jedného správcu siete a 4 koordinátorov, pričom každý z nich pozná niektoré z hesiel. Heslá sú rozdelené tak, aby správca spolu s ľubovoľným koordinátorom alebo ľubovoľní traja koordinátori spolu mohli získať prístup. Naopak správca sám ani žiadna dvojica koordinátorov prístup získať nesmie.
Aký je najmenší počet hesiel, akými môže byť subjekt zabezpečený? Nájdite pre tento počet aspoň jedno rozdelenie jednotlivých hesiel medzi koordinátorov a správcu a dokážte, že menej hesiel nestačí.
Vzorové riešenie
Najprv sa zamyslime nad koordinátormi, a správcu siete si necháme na neskôr...
Koľko hesiel nám bude stačiť? Musí platiť, že nech zvolíme ľubovoľnú dvojicu koordinátorov, nejaké heslo jej bude chýbať. Inak by vedeli spoločne získať prístup. Rôznych dvojíc je šesť, teda musí byť aj šesť hesiel, aby každej nejaké chýbalo. Alebo? Nemôže jedno heslo chýbať viacerým dvojiciam naraz? Potom by nám hesiel stačilo menej…
Pravda je taká, že určite nemôže jedno heslo chýbať viacerým dvojiciam. V dvoch dvojiciach sú určite aspoň traja koordinátori (v prípade, že jeden je v oboch). Dokopy teda určite z týchto dvojíc vieme zostaviť nejakú trojicu. Táto trojica bude pozostávať len z koordinátorov, ktorí dané heslo nepoznajú. To ale protirečí zadaniu, ktoré hovorí, že každá trojica koordinátorov vie získať prístup. Teda naozaj to takto nemôže byť.
Vidíme teda, že každá zo šiestich rôznych dvojíc musí mať "vlastné" heslo, ktoré nepozná. To je šesť hesiel. Ostáva nám teraz len zamyslieť sa, ako zaručiť, že správca nebude mať sám všetky heslá, ale zároveň mu bude stačiť pomoc ľubovoľného koordinátora, aby získal prístup.
Určite nejaké heslo bude správcovi chýbať. Nemôže to byť ani jedno z našich šiestich hesiel, pretože potom by dvojica správcu s nejakým koordinátorom, ktorému to heslo tiež chýba, nedokázala získať prístup. Teda ide o nejaké siedme heslo, ktoré musí mať každý z koordinátorov.
Sme si teda istí, že hesiel potrebujeme určite aspoň 7. Stačí to naozaj? Skúsme si zapísať, kto bude poznať ktoré z týchto hesiel:
- Správca siete: 1,2,3,4,5,6,
- Koordinátor 1: 1,2,3,7,
- Koordinátor 2: 1,4,5,7,
- Koordinátor 3: 2,4,6,7,
- Koordinátor 4: 3,5,6,7.
Vidíme, že naozaj naša konštrukcia funguje - ľubovoľná trojica koordinátorov aj ľubovoľný koordinátor so správcom majú všetkých sedem hesiel, ale správca sám ani žiadna dvojica koordinátorov ich nemá.
Odpoveď: Hesiel musí byť najmenej sedem.