O clădire are de etaje. Holul fiecărui etaj este accesibil prin oricare dintre cele două uși principale, iar holul conține patru camere. Fiecare cameră are ușa ei, în fiecare cameră locuiește o persoană. O singură încuietoare va fi instalată pe fiecare uşă, inclusiv pe uşile holului, iar cheile vor fi distribuite pentru a se asigura că:
- Fiecare persoană poate accesa propria sa cameră, dar nu a altcuiva și
- Fiecare persoană poate accesa holul de la etaj,
- Este permis ca cineva să aibă acces la holurile de la alte etaje.
Fiecare încuietoare este asociată cu o cheie corespunzătoare unică și poate fi deschisă numai cu acea cheie. Cu toate acestea, aceeași încuietoare poate fi folosită pe mai multe uși, dacă este necesar, și pot fi făcute și distribuite orice număr de copii ale cheii corespunzătoare. Persoanele fizice pot deține câte chei sunt necesare. Compania responsabilă de instalare își propune să minimizeze costul total de producere a cheilor. Crearea unei chei noi costă 3 RON și realizarea unei copii a unei chei existente costă 2 RON. Care este costul total minim al tuturor cheilor în timp ce îndeplinesc condițiile de mai sus?Soluție
Răspuns:
Luăm în considerare o aranjare optimă din punct de vedere al costurilor a încuietorilor și a cheilor; este clar că într-un astfel de caz niciun rezident nu deține mai mult de două chei. Mai arătăm că putem presupune, fără pierderi de generalitate, că la fiecare etaj, există exact un rezident (sau echivalent, cel puțin unul, deoarece nu poate fi mai mult de unul) rezident care deține o singură cheie. Această cheie oferă acces atât la camera lor, cât și la una dintre ușile holului, în timp ce ceilalți trei rezidenți de la acel etaj folosesc cealaltă ușă a holului.
Să presupunem că nu este cazul la un etaj. Apoi, una dintre ușile holului, , este folosită de cel mult doi dintre cei patru rezidenți – rezident și, eventual, rezident . Dacă niciun rezident dintre cei patru nu poate debloca , selectăm unul dintre ei în mod arbitrar și le tratăm în continuare ca . Modificam sistemul de chei astfel: inlocuim incuietoarea de la usa cu una complet noua si instalam aceeasi incuietoare pe usa camerei lui . Ca rezultat, necesită acum doar o singură cheie, care costă , în timp ce cele două chei anterioare aveau un cost combinat de cel puțin . Acest lucru reduce costul total cu cel puțin .
Mai mult, dacă rezident există, le reatribuim cheia de la hol pentru a se potrivi cu cealaltă ușă de hol de la acel etaj, ceea ce nu crește costul total. Totuși, în acest fel, ar putea ajunge la o combinație de taste care să permită accesul la o cameră de la alt etaj; pentru a remedia acest lucru, înlocuim blocarea camerei lui cu una complet nouă, care crește costul cu cel mult .
Deoarece costul total nu crește prin acest proces, concluzionăm că configurația presupusă este cel puțin la fel de rentabilă ca orice alternativă. Prin urmare, în cele ce urmează, presupunem că există exact un rezident cu o singură cheie la fiecare etaj.
Astfel, problema se reduce la minimizarea costului cheilor pentru 160 de etaje unde fiecare hol are o singură intrare și trei încăperi separate. Fie tipuri de chei distincte . Fiecare rezident primește o cheie pentru camera sa și o cheie pentru hol, iar aceste două chei nu pot fi de același tip. De asemenea, doi rezidenți nu pot avea aceeași pereche de tipuri de chei, deoarece acest lucru ar însemna că au acces la aceeași cameră. Prin urmare, numărul de perechi de chei valide este dat de .
Deoarece distribuim un total de perechi de chei, determinăm limita inferioară pentru din inegalitate
Obținem că . Acum, demonstrăm că este posibil să folosim exact tipuri de chei distincte. Pentru a realiza acest lucru, împărțim cele 160 de etaje în 32 de grupuri a câte 5 etaje fiecare. Atribuirea cheilor se desfășoară după cum urmează (prima cheie din pereche este pentru hol și a doua pentru cameră):
- Cei 15 rezidenți din primul grup primesc perechile de chei .
- Celui de al doilea grup i se atribuie perechile de chei .
- Acest model continuă, al 31-lea grup primind perechile de chei .
- În cele din urmă, ultimului grup (al 32-lea) i se atribuie perechile de chei .
Este ușor de observat că această distribuție îndeplinește condițiile prezentate mai sus. Prin urmare, este numărul minim de chei unice necesare, la care adăugăm copii de pentru a acoperi toate cheile de .
Luând în considerare rezidenții menționați în primul paragraf, trebuie să fie produse un total de chei unice. Astfel, costul final este calculat ca .