ACM RTK - 1. skupina

Pacifistični generali

Ker imajo vse svetovne vojaške velesile jedrsko orožje, ga moramo nujno imeti tudi pri nas v Sloveniji. Pa je vlada naročila na IJS izdelavo jedrskih konic, od Rusov pa so kupili bojno plovilo VNL-11 Triglav, kjer so smrtonosne rakete zdaj shranjene. Dostopa do tako uničujočega orožja ne sme imeti kdorkoli, ampak ga ima samo peščica najpomembnejših generalov. Ker bi se lahko med generali našel norec, ki bi za zabavo poslal raketo ali dve na katero od sosednjih republik, so se na vojaškem ministrstvu odločili za stroge varnostne ukrepe. Naročili so izdelavo k različic ključev za aktivacijo jedrskih konic. Ključi so oštevilčeni s števili od 1 do k. Vsaka različica ključa je bila izdelana v več izvodih. Te ključe so nato razdelili med n generalov, tako da je vsak prejel neko podmnožico (samih različnih) ključev. Označimo z G_i podmnožico ključev, ki jih ima i-ti
general. Skupina generalov lahko sproži atomsko bombo, če imajo vsi skupaj vsaj po eno kopijo vsakega od ključev.

Zgled: recimo, da imamo k = 3 ključe in n = 3 generale. Naj bo

G₁ = {1, 2}, G₂ = {2, 3}, G₃ = {1, 3}.

Prvi general ima torej ključ št. 1 in ključ št. 2. Drugi general ima ključ št. 2 in ključ št. 3. Tretji general ima ključ št. 1 in ključ št. 3. Vsak posamezni general ne more aktivirati jedrske konice, če pa se združita npr. prvi in drugi general, imata skupaj G₁ ∪ G₂ = {1, 2, 3} vse ključe.

Na ministrstvu so pred kratkim opazili fenomen, na katerega pri snovanju sistema sploh niso pomislili. Med generali je vedno več pacifistov, ki niso pod nobenimi pogoji pripravljeni uporabiti jedrskega orožja. Vlada se zdaj boji, da bi lahko manjša skupinica pacifistov ostalim generalom preprečila uporabo orožja. Rekli bomo, da je sistem r-odporen, če nobena skupina r (ali manj) generalov ne more ostalim preprečiti aktivacije jedskih konic.

Sistem iz zgleda je 1-odporen, saj nobeden od generalov ne more sam ,,blokirati`` ostalih dveh.

Opiši postopek (ali napiši program, če ti je to lažje), ki bo za dani r in dani sistem preveril, če je ta sistem r-odporen. Opiši tudi, kako bi tvoja rešitev hranila in organizirala podatke (množice G₁, ..., G_n
in podobno).