Provocare-noua-3

După o petrecere de neuitat, ai mers acasă, să te odihnești. Casa ta are 7 camere, dispuse ca în imaginea de mai jos. Cu tine locuiește prietenul tău cel mai bun, motanul Garfield. Fiind foarte special pentru tine, te vei simți mai bine dacă acesta e lângă tine. Din păcate, nu știi unde se ascunde și fiind atât de obosit nu vrei să stai mai mult de 10 min căutându-l. Într-un minut, știi sigur că acesta se va deplasa din camera în care este, într-o cameră alăturată, iar tu te poți deplasa în același minut câte 2 camere. Dacă intri în camera în care este el, îl vei găsi imediat, dar nu știi nici de unde începe, și nici în ce camere va merge. De asemenea, nu te poți întâlni cu el pe holuri dintre camere. Poți porni din orice cameră dorești. Vei putea să îl găsești în 10 minute, ca să te poți odihni liniștit?

Soluție

Problema nu ne oferă prea multe informații, și pare că nu sunt suficiente pentru a o rezolva, dar observând anumite detalii, aceasta devine mai simplă. Prima dată observăm că intr-o mișcare, motanul merge dintr-o cameră cu număr par, într-una cu număr impar, sau invers. Să presupunem că acesta se află inițial într-o cameră cu număr par. Astfel, vom porni și noi dintr-o cameră pară, spre exemplu 2. Dacă nu îl găsim aici înseamnă ca acesta a început din 4 sau 6 și se va putea mișca doar în camerele 3, 5 și 7. Cum 3 are cele mai multe conexiuni cu alte camere, acolo vom căuta următoarea dată. Dacă nu este nici aici, însemnă că se află ori în 5, ori în 7, putând mai apoi să se întoarcă în 4 sau 6. Să cautăm în următoarea tură 4. Dacă nu îl găsim nici aici, înseamnă că se află în camera 6. Următoarele 2 mișcări în 3 și apoi în 6 vor garanta găsirea lui Garfield. Dar dacă presupunerea noastră este greșită? Atunci, dupa cele 5 mișcări făcute de noi, el se va afla într-o cameră cu număr par. Deci reluarea algoritmului precedent va duce la găsirea motanului în 10, sau mai puține, mișcări.