Problema a fost propusa de Vasile Trofin, care a primit punctajul aferent acesteia (15 puncte). Multumim pentru propunere!
Soluţii corecte, in care strategia implica cel mult 13 intrebari pentru determinarea celor 3 bile castigatoare: Zoltan Szabo, Traian Dajma, Ioan Scutaru.
Am primit si alte solutii, dar cu un numar de intrebari care poate fi mai mare decat 13: Mihaela Voinescu, Viorel Manta, Emil Claudiu Man, Jean Henry Berevoescu.
O solutie particulara este 15, care se poate obtine prin intrebari care injumatatesc intervalul de cautare.
Vasile Trofin (observatie pentru determinarea maximului optim): celor 4960 de combinatii posibile a celor 32 numere luate cate 3 li se acorda numar de ordine in intervalul [1,4960] si identificarea numarului combinatiei respective se face prin 13 = log24960 incercari / pasi
Postam, pentru exemplificare, prima solutie corecta primita.
Zoltan Szabo:
Vom lucra cu grupe de bile în care știm că exact câte bile câștigătoare există. Notația nk înseamnă că grupa este formată din n bile, din care k bile sunt câștigătoare.
Observăm următoarele:
1. Grupele 11 și 22 sunt formate doar din bile câștigătoare și nu necesită întrebări.
2. Orice grupă de forma n1 se transformă în (n/2)1 cu o singură întrebare. Se întreabă despre una din cele două grupe înjumătățite dacă conține bilă câștigătoare? Astfel grupa 21 necesită 1 întrebare, grupa 41 necesită 2 întrebări, grupa 81 necesită 3 întrebări.
3. Orice grupă de forma n2 se transformă în (n/2)2 sau două grupe de (n/2)1 prin cel mult 2 întrebări. Prima întrebare despre o grupă înjumătățită este: Această grupă conține exact o bilă câștigătoare? Dacă răspunsul este DA, atunci se va ști că ambele grupe conțin câte o bilă câștigătoare. Altfel se mai pune încă o întrebare pentru a afla dacă grupa conține 0 sau 2 bile câștigătoare?
4. Orice grupă de forma n3 se transformă în (n/2)3 sau două grupe de (n/2)1 respectiv (n/2)2 prin 2 întrebări. Se construiesc cele două grupe cu câte (n/2) bile și se întreabă Grupa 1 conține mai puține bile câștigătoare decât grupa 2? După ce aflăm în care grupă sunt mai puține bile, vom întreba dacă are bile câștigătoare?
Aplicând cele menționate mai sus, începem rezolvarea problemei prin împărțirea celor 32 de bile în 4 grupe de 8 bile.
Pentru fiecare grupă în parte se pune întrebarea: Această grupă conține bile câștigătoare? Astfel din cel mult 4 întrebări aflăm grupele care conțin bile câștigătoare. Menționăm că dacă primele 3 întrebări au răspuns afirmativ, atunci a patra grupă nu poate conține bilă câștigătoare și întrebarea nu își mai are rostul.
Putem avea:
- 1 grupă 83
- 3 grupe 818181
- 2 grupe 8182?. Pentru că nu știm grupa în care se află 2 bile, mai punem încă o întrebare: Această grupă conține 2 bile câștigătoare? Indiferent de răspunsul dat, vom identifica cu siguranță 81 și 82.
În continuare cazul 818181 se va rezolva din 3*3=9 întrebări. Cazul 8182 se va rezolva cu cel mult 8 întrebări. Cazul 83 se va rezolva cu cel mult 7 întrebări.