Cred ca la inceput de saptamana cand nici iarba nu creste, un imbold primit din partea unor probleme de logica ar fi binevenit pentru “demarajul” mintal necesar unei noi saptamani. Sper sa fiti mai inspirati decat sunt eu lunea.
Astazi avem probleme cu diferite jocuri logice cu 2 jucatori.
Problema 1
Doi jucatori au jucat un joc cu bete de chibrit. Dintr-o gramada cu bete fiecare jucator avea dreptul sa inlature, cu randul, un anumit numar de bete (cu un maxim fixat) pana la terminarea gramezii. Jucatorul care inlatura ultimul bat castiga partida. Daca jucatorul A putea sa aleaga daca sa inceapa primul, sau nu, spuneti care ar fi strategia lui daca:
- In gramada ar fi 28 de bete, si fiecare jucator ar putea sa inlature 1 sau 2 bete odata?;
- In gramada ar fi 28 de bete, si fiecare jucator ar putea sa inlature 1,2 sau 3 bete odata?
- In gramada sunt x bete, si fiecare jucator ar putea sa inlature de la 1 la y odata?
Problema 2
Alti doi jucatori au jucat un joc asemanator cu X si 0. Pe o foaie au trecut 15 puncte in linie in felul urmator:
. . . . . . . . . . . . . . .
Jocul consta in a inlocui, pe rand, punctele cu X-uri. Primul jucator care pune un X astfel incat sa formeze o linie de 3 X-uri castiga.
Care jucator ar trebui sa castige, cel care incepe primul sau al doilea jucator?
Problema 3
Jocul lui Nim se joaca dupa cum urmeaza:
Incepe cu 3 (sau mai multe) randuri de bete, care contin un numar arbitrar specificat de bete (de obicei inegal). Cei doi jucatori pot sa ridice, pe rand, un numar de bete de pe oricare dintre randuri, pana la limita maxima de bete existente pe acel rand, dar nu poate sa ridice bete de pe randuri diferite la aceiasi “mutare”. Jucatorul care ridica ultimul bat castiga.
- O versiune comerciala a jocului incepe cu trei randuri de bete, care contin 3, 5 si respectiv 7 bete. In aceasta versiune e mai bine sa incepi primul, sau sa cedezi randul, si care e strategia care ar trebui urmata?
- Generalizati pentru jocul care contine trei gramezi cu x, y si respectiv z bete.
Problema 4
Dintr-un pachet de carti scoatem cei 4 asi, 4 de 2, 4 de 3 si 4 de 4 si le pune cu fata in sus pe o masa. Jucatorul A alege una din carti, spune valoarea cartii (asii conteza ca 1) si o intoarce cu fata in jos. Jucatorul B alege si el una dintre cartile ramase, aduna valoarea ei la valoarea precedenta spusa de jucatorul A si o intoarce cu fata in jos. Cartea urmatoare aleasa de jucatorul A este adunata, la el, la total s.a.m.d. Jucatorul care ajunge la suma de 22, sau reuseste sa-si faca adversarul sa depaseasca aceasta suma castiga.
Analizati jocul.
Problema 5
Pe un zar normal numarul 1 e opus numarului 6, 2 e opus lui 5, si 3 lui 4. Jucatorul A aseaza un zar pe masa si spune numarul care se afla pe fata de deasupra. Jucatorul B trebuie sa rasuceasca zarul astfel incat fata respectiva sa se afle pe una din partile laterale (nu dedesubt). Noul numar obtinut de pe fata de deasupra este adaugat la numarul precedent, s.a.m.d. Jucatorul care ajunge la suam de 26, sau cel care reuseste sa-si faca adversarul sa depaseasca aceasta suma castiga. Daca jucatorul A poate sa aseza initial zarul cum doreste analizati jocul (de notat ca, de exemplu, daca 1 este pe fata de deasupra, jucatorul urmator poate sa aseze zarul astfel incat pe fata de sus sa se afle 2, 3, 4 sau 5, dar nu poate sa lase zarul cu 1 sau 6 deasupra).
7 Comentarii
Problema 1
Multe probleme de acest gen se rezolva cu urmatoarea strategie. Se determina o proprietate P astfel:
a. configuratia finala(cea castigatoare) are proprietatea P
b. din orice configuratie ce are proprietatea P orice mutare s-ar efectua se ajunge intr-o configuratie ce nu are proprietatea P (se dezechilibreaza)
c. in orice configuratie ce nu are proprietatea P exista cel putin o mutare astfel incat sa conduca la o configuratie ce are proprietatea P. (echilibrare)
Daca configuratia initiala nu are proprietatea P atunci primul jucator are strategie de castig intrucat efectueaza o mutare astfel incat sa lase o configuratie ce are prop. P, iar cel de-al doilea orice mutare ar efectua lasa o configuratie ce nu are proprietatea P si astfel numai jucatorul a poate ajunge la configuratia finala care are proprietatea P.
Daca initial configuratia are proprietatea P, atunci jucatorul B castiga intrucat primul orice ar muta ajunge intr-o configuratie de dezechilibru, care este apoi echilibrata de cel de-al doilea jucator.
1. starea finala este cea cu 0 bete, deci este divizibila cu 3. Primul jucator extrage un bat si lasa 27 de pietre (divizibil cu 3). orice ar muta jucatorul doi lasa o configuratie ce nu e divizibila cu 3. jucatorul 1 de fiecare data poate lasa o configratie div. cu 3
2. se aplica divizibilitatea cu 4. De data aceasta jucatorul 1 prin orice mutare strica echilibrul, iar jucatorul doi poate extrage un numar de bete astfel sa lase o configuratie divizibila cu 4. etc.
3. se aplica divizibilitatea cu y+1.
august 19, 2009 - 10:01 pmProblema 3
august 19, 2009 - 10:14 pmLa fel ca la problema 1 se determina proprietatea (P: a^b^c = 0) (rezultatul prin “sau exclusiv” a numerelor de bete din cele 3 gramezi a, b, c este 0). Problema nu este usor de inteles pentru cei care nu sunt familiarizati cu operatiile binare (in baza 2). O demonstratie poate fi gasita aici.
Problema 2
august 20, 2009 - 2:30 pmVoi arata ca jocul este remiza. Nu voi desena toate punctele(nici nu le voi numara pe cele desenate) voi schita doar ideea. Jucatorul O poate forta tot timpul remiza. La inceput efectueaza X o mutare de genul …….X…….., iar O plaseaza intr-una din pozitiile vecine(care este libera(dupa cum X-ul este in colt sau nu) sau la intamplare daca amblele sunt libere) un O si situatia arata astfel ………OX……….. Acum strategia lui o este de a elimina posibilitatile de atac ale adversarului cu mutarile deja efectuate. Astfel la o mutare de genul ………..OX……….X………, O va juca astfel ………..OX…………OX………… (sau ……..OXXO……. dupa cum a fost pus X-ul), iar la o mutare de genul ………..X……OX…………. va muta ………OX……….OX…………. (exceptie facand amplasarea X-ului in colt caz in care O va fi plasat imediat in dreapta). dupa cum se poate observa intre orice doua X de fiecare data se afla cel putin un O si deci X nu poate castiga pt ca nu poate construi 3 X-uri consecutive.
De asemenea si jucatorul X poate forta remiza plasand la inceput un X in coltul din stanga X……………………., iar la fiecare amplasare a unui O are grija sa plaseze un X fix langa mutarea deja efectuata astfel incat sa elimine viitoarele conectari cu mutarile O deja efectuate(se aplica strategia prezentata anterior); de ex.: la X………O………. poate muta X…………XO………… iar la X……XO……O………. va muta X…….XO……..XO…… etc. Cum ambii jucatori pot forta remiza, rezulta clar ca nu exista strategie de castig la un joc corect. Jocul trebuie sa se finalizeze cu remiza.
Problema 2
august 20, 2009 - 8:08 pmImi cer scuze, am citit gresit problema(am crezut ca se pun si X-uri si 0-uri). In cazul de fata primul jucator are strategie de castig punand in mijloc X iar apoi jucand simetric fata de mutarile adversarului. Astfel adversarul nu poate castiga niciodata, deoarece pentru castig este nevoie de existenta unei configuratii de forma X.X sau XX. sau .XX, insa numai jucatorul 2 poate crea astfel de configuratii. Daca apare o astfel de configuratie primul jucator plaseaza X-ul corespunzator si castiga. Daca prin absurd primul jucator ar crea o configuratie de tipul celor mentionate inseamna ca la mutarea de dinainte jucatorul 2 a creat si el o astfel de configuratie (datorita simetriei)si in acest caz jucatorul 1 ar fi putut obtine castigul mutand corect.
Jocul Nim cu doua gramezi
august 21, 2009 - 2:26 pmA observat in arhiva o problema cu turnuri pe care o puteti citi aici . Solutia nu e foarte dificila. Se poate observa ca pozitia e simetrica. De fiecare data primul jucator strica simetria. Daca primul jucator a putut muta atunci si jucatorul 2 poate muta, facand mutarea simetrica corespunzatoare. Strategia este de a muta simetric(proprietatea P = “pozitia este simetrica” 🙂 ).
Insa, ceea ce voiam sa mentionez este ca problema este o varianta ascunsa de Nim. Fie O, respectiv V distanta dintre turnuri pe orizontala, respectiv verticala. Ce se intampla cand unul dintre turnuri este mutat? De exemplu daca este mutat pe verticala 3 pozitii atunci cuplul (O, V) devine (O, V-3). Practic una si numai una dintre componente este modificata(se micsoareaza). Cand una dintre componente e 0 atunci insemana ca turnurile sunt vecine pe verticala, sau orizontala (in functie de componenta). Pozitia finala este (0, 0). A muta turnurile insemana a juca jocul Nim cu doua gramezi(in cazul de fata cele doua gramezi sunt (7,7)). Practic nu conteaza pozitia turnurilor ci doar distanta dintre ele pe fiecare dintre cele doua dimensiuni(ambele se indreapta unul catre celalalt). Strategie pentru jocul cu doua gramezi este de a mentine simetria. Daca initial gramezile sunt egale, jucatorul 2 are strategie (va juca simetric), iar daca sunt inegale jucatorul 1 va castiga (egaland de fiecare data gramezile). Strategia e mai usor de ghicit in cazul cu doua gramezi de aceea de cele mai multe ori pentru a creste dificultatea jocul Nim este asociat cu cel putin 3 gramezi. De asemenea, din demonstratia generala a jocului (cea cu sau exclusiv (^))se poate deduce usor faptul ca trebuie jucat simetric intrucat a^b = 0 doar daca numerele sunt egale(se observa ca pe fiecare pozitie bitii trebuiesc sa fie egali, pentru ca altfel avem 0 si 1 sau 1 si 0 si prin ^ se obtine 1 deci rezultatul nu mai poate fi 0). Frumoasa “camuflare”!
P1 si P2 sunt corect rezolvate.
august 22, 2009 - 1:14 pmRezolvare corecta si la Problema 1 a “episodului” 9.
august 22, 2009 - 1:23 pm