O problemă care circulă pe internet sub diverse enunțuri echivalente. Am ales și eu să o formulez în manieră personală, pentru a o face mai greu de găsit pentru cei care nu o știu deja. Așadar:
O pisică trebuie să prindă, desigur, un șoarece. Regulile jocului sunt următoarele:
- pisica se află la capătul holului de la parterul unui hotel
- pe partea stângă a holului există 7 camere, prevăzute cu 7 uși (să zicem ușile 1 la 7, dinspre capătul pisicii către celălalt capăt al holului);
- șoarecele se află într-una din cele 7 camere;
- la fiecare 10 minute, pisica deschide o ușă pentru a vedea dacă șoarecele este în camera respectivă;
- între două deschideri succesive de ușă efectuate de pisică, șoarecele se mută într-o cameră vecină.
De câte minute are nevoie pisica, una foarte pricepută la matematică și posesoarea unei logici impecabile, pentru a deschide ușa camerei în care se află șoarecele? Care este algoritmul cel mai rapid de urmat?