Săptămâna 301

Rezolvare:
Soluţia 1 (Ruxandra Olimid):

Răspuns: Dana este cea care a furat cartea (a nu a văzut-o pe Andreea).

Justificare:

Considerăm toate afirmaţiile celor 6 corecte şi formăm următorul tabel, prin marcarea DA pe linia lui X, dacă aceasta spune că l-a văzut pe Y.

	A	B	C	D	E	F
A	---	DA			DA
B	DA	---				DA
C			---	DA		DA
D	DA			---		DA
E		DA	DA		---
F			DA		DA	---

Se observă că atât A şi B cât şi C şi F s-au vazut reciproc. Cum un singur student minte, înseamnă ca A şi B, respectiv C şi F au fost un anumit moment de timp împreună în bibliotecă.

Stim însă că dacă X l-a văzut pe Y (considerând adevărată acaeastă afirmaţie), atunci ei s-au aflat amândoi în bibliotecă pentru un anumit timp.

Se notează OK = “X si Y au fost simultan în bibliotecă o anumită perioadă de timp”;

(tabelul se obţine din cel de deasupra, prin “simetrizare” faţă de prima diagonală).

Toate pătrăţelele rămase libere corespund celor care nu s-au întâlnit.

	A	B	C	D	E	F
A	---	OK		OK	OK
B	OK	---			OK	OK
C			---	OK	OK	OK
D	OK		OK	---		OK
E	OK	OK	OK		---	OK
F		OK	OK	OK	OK	---

Deci se şţie cu siguranţă că nu au fost în acelaşi timp în bibliotecă: A şi C, A şi F, B şi C, B şi D, D şi E.

Se analizează tabelul:

D se întâlneşte în bibliotecă cu A dar şi cu C. Însă A nu se întâlneşte cu C (se ştie cu certitudine). Să presupunem că A a ajuns primul în bibliotecă şi după plecarea sa a venit C. Atunci D a fost prezent cu sigurantă în bibliotecă între plecarea lui A şi venirea lui C (fiecare a intrat o singură dată în sală). Dar E s-a întâlnit cu A şi cu C, însă nu şi cu D - după cum reiese din tabel. Ca să îi întâlnească pe ambii, C ar fi trebuit - asemenea lui B - să asiste la plecarea lui A şi venirea lui C, deci indirect să fie în sală atunci când era şi D. Contradicţie.

Avem 6 afirmaţii care duc la o contradicţie:

A şi D s-au întâlnit;

C şi D s-au întâlnit;

A şi C nu s-au întâlnit (sigur)

A şi E s-au întâlnit;

C şi E s-au întâlnit;

D şi E nu s-au întalnit (sigur).

Două dintre afirmaţii sunt sigure, aşa că rămân de analizat 4 cazuri:

1. 
   A şi D nu s-au întalnit.
   

Acest caz nu duce la nici o contradicţie.

Primul student care intră în sală este A, apoi B, E şi F în această ordine. A părăseşte sala, după un timp pleacă şi B. După plecarea lui B intră C , apoi va pleca E. Urmează să intre D. Într-un final vor ieşi C, D şi F.

Toate afrimaţiile sunt adevărate, cu excepţia lui D care nu s-a întânit cu A.

2) Pentru toate celelalte cazuri considerăm că A şi D s-au întâlnit.

Atunci A s-a întâlnit cu B şi D. Dar D nu s-a întâlnit cu B. F s-a întâlnit cu B şi cu D dar nu cu A  contradicţie.
Variantă (Gheorghe Pistol):

Andreea

Bogdan

Elena

Cosmin

Francisc

Dana

În acest mod s-au întâlnit cei 6 studenţi în bibliotecă (Dana putea pleca ultima).

Observăm că Dana a spus că a văzut şi pe Andreea, dar ar fi trebuit să se întâlnească şi cu Bogdan şi Elena; dar nici unul dintre Dana şi Bogdan, Dana şi Elena nu au spus că s-au văzut.

Bogdan sau Dana sunt unul dintre mincinoşi,deoarece ar fi trebuit să se fi întâlnit în sală; dar nici unul nu a spus că l-a văzut pe celălalt.

Singura variantă când Bogdan nu se putea întalni cu Dana, ne duce la o situaţie în care Dana şi Elena s-ar fi întalnit. Dar nici una nu a spus că a văzut-o pe cealaltă

Din cele trei raţionamente ale mele, Bogdan şi Elena, spunând corect, atunci Dana este mincinoasa şi atunci ea a furat .
Daniela Păduraru s-a apropiat foarte mult de rezultat, reducând cercul suspecţilor la două persoane (Bogdan şi Dana).
Soluţia 2 (Adrian Buturugă):

Transformăm enunţul problemei într-unul bazat pe teoria grafurilor. Fie un graf neorientat (dacă A şi B spun adevărul, nu contează dacă A îl vede pe B sau B pe A, pentru că amândoi sunt în cameră în acelaşi timp) cu nodurile: {A, B, C, D, E, F} şi arcele {AB, AD, AE, BE, BF, CD, CE, CF, DF, EF}.

Considerăm operaţiile:

• 
  Adăugare nod: se adaugă un nod în graful dat, doar dacă există muchii astfel încât graful rezultat să fie complet (şi, implicit – conex).
  
• 
  Eliminare nod: se elimină nodul şi muchiile adiacente, dacă nu mai există muchii neutilizate până acum, adiacente cu nodul ce se vrea şters (decât eventual ale mincinosului, adică maxim o muchie adiacentă la nodul current).
  

Se observă că nu există nicio combinaţie de muchii astfel încât să poată exista la un moment dat un subgraf complet cu 4 noduri, iar pentru mai mult de 4 noduri nu se poate construi un graf complet cu 10 muchii.

Deci întotdeauna vor fi maxim 3 studenţi simultan în bibliotecă.

Cum A l-a văzut pe B şi B pe A, iar C pe F şi F pe C, rezultă ca niciunul nu a minţit, întrucât afirmaţia celuilalt îl “pune la faţa locului”. Hoţul nu poate fi deci decât D sau E.
Presupunem că A (pentru B se obţine acelaşi lucru) a fost primul nod în graf şi începem algoritmul:

Putem adăuga nodul B sau E (se observă că nu contează pe care îl alegem, atâta timp cât nu considerăm hoţ pe B sau pe E). Adăugăm nodul B.

• 
  Singurul nod care poate fi adăugat, astfel încât adăugand din muchiile nefolosite să formăm un subgraf complet, este E. (Deci considerăm că E nu este hoţul). Având 3 noduri în subgraf, conform observaţiei, trebuie să eliminăm cel puţin un nod. Presupunem că D este hoţul şi ignorăm muchiile date de el: AD şi DF. Astfel, eliminăm nodul A. Adăugăm nodul F (singurul posibil). Eliminăm nodul B. Adăugăm nodul C. După ce eliminăm nodurile E şi F, mai rămâne doar muchia CD, care - după eliminarea lui C - ne spune că D a rămas singur în bibliotecă, ultimul, adeverind presupunerea că el este hoţul. Rezultă ca hoaţa este Dana.
  
• 
  Presupunem că E este hoţul şi ignorăm BE şi CE. Cum A şi B mai au muchii adiacente nefolosite, şi am presupus că nu ei sunt hoţii, ajungem în impas, neputând continua. Deci E nu este hoţul.
  

Dacă algoritmul începe de la nodul C:

• 
  (considerând că D este hoţul). Putem adăuga doar combinaţia F şi E (ca să obţinem un graf conex, fără a ne bloca). Nu mai putem continua, întrucât l-am considerat pe D hoţ şi rămân muchii adiacente nefolosite pentru toate cele 3 noduri, neputând elimina niciunul.
  
• 
  Considerăm că E este hoţul: nu putem adăuga decât combinaţia D şi F. Fiecare nod mai are muchii nefolosite adiacente, în condiţiile în care am considerat pe E drept hoţ (si am ignorant muchiile aferente). Nu putem adăuga alte noduri, dar nici şterge. Deci nu se poate continua.
  

Dacă algoritmul începe de la nodul D (considerând implicit că E este hoţul). Putem adăuga doar combinaţia F şi C. Eliminăm nodul C. Nu mai există noduri astfel încât să obţinem un subgraf complet, dar nici nu mai putem elimina noduri.

Dacă algoritmul începe de la nodul E (considerând implicit că D este hoţul). Putem adăuga A şi B (caz studiat deja) sau B şi F. Adăugăm pe B şi F. Fiecare mai are muchii adiacente nefolosite şi nici nu mai putem adăuga alt nod.
În sfârşit, dacă pornim de la nodul F, putem adăuga combinaţiile B + E sau C + E (ambele cazuri au fost studiate). Deci F nu poate fi primul în bibliotecă.
În concluzie, singura posibilitate este: Andreea, Bogdan şi Elena au fost primii în bibliotecă (nu contează ordinea venirii lor). Pleacă Andreea, vine Francisc. Pleacă Bogdan, vine Cosmin. Pleacă Elena şi Francisc şi vine Dana. După plecarea lui Cosmin, Dana rămâne singură în bibliotecă, furând cartea.
Notă (AA):

Într-adevăr, se pare că problema a apărut într-o carte de Teoria grafurilor scrisă de Doug West - Introduction to Graph Theory, pagina 346. Acolo ea îi este atribuită lui M. Golumbic, în Algorithmic Graph Theory and Perfect Graphs (nu am găsit această carte).

Eu am luat problema de pe site-ul Colegiului Macalester, care indică aceste surse.
Plecând de la idea construirii grafului propus anterior, putem observa că acesta trebuie să verifice proprietatea următoare: orice ciclu de lungime cel puţin 4 trebuie să aibă o diagonală. De exemplu, dacă A vede pe B, B vede pe C, C vede pe D, D vede pe A, atunci A vede pe C sau B vede pe D (cu accepţiunea că “X vede pe Y” poate însemna la fel de bine că “Y vede pe X”). Afirmaţia se demonstrează uşor tratând toate situaţiile.

Deci vom căuta în acest graf toate ciclurile de 4 noduri, fără diagonale şi încercăm ca prin eliminarea unei singure mucgii, acestea să dispară.

Singurele cicluri de 4 noduri care nu au diagonale sunt ADFB şi AECD (marcate cu roşu şi verde).



Singurul mod de a le elimina este scoaterea arcului AD, ceea ce indică drept hoţi posibili pe A sau D. Un studiu imediat arată că numai D poate fi hoţul.