Pagina principala | Inscriere | Autentificare | Probleme | Clasament pe runde | Clasament | Anunturi | Echipa | Regulament


Vizualizare solutie

Titlul problemei: smart
Numarul problemei: 2
Runda: Runda 5
Solutie: Problema tine de teoria combinatoriala a jocurilor.

(Combinatorial Game Theory)

Jocul este o varianta mai simple a unui joc combinatorial cunoscut

in literatura de specialitate din strainatate sub denumirea de Green

Hackenbush.

Totul se reduce la jocul de Nim. La nim, doi jucatori

efectueaza mutari alternativ. Jocul se joaca cu N gramezi de

obiecte. O mutare consta in luarea oricator obiecte (cel putin 1)

dintr-o _singura_ gramada. Jucatorul care nu mai poate efectua nici

o mutare (toate gramezile s-au terminat) pierde.

Pentru mai multe detalii despre jocul de Nim si despre modul in

care Green Hackenbush se reduce la acest joc, puteti consulta:

http://www.math.ucla.edu/~tom/GameTheory/Contents.html

Ideea de baza la rezolvarea problemei este urmatoarea teorema:

- nodurile oricarui ciclu din graf pot fi _compactate_ intr-un

singur nod, fara a modifica rezultatul jocului. Prin compactare

se intelege stergerea nodurilor respective si crearea unui nou nod

care sa contina toate muchiile aferente nodurilor sterse (inclusiv

buclele).

In acest mod problema se reduce de la un graf cu radacina la un

arbore cu radacina (buclele nu conteaza, pot fi transformate in

muchii adaugand un nod fictiv).

O noua teorema reduce orice arbore la un arbore mai particular:

- cand mai multe ramuri de lungime (L1,L2,...LN) se unifica

intr-un nod, ele pot fi inlocuite cu o ramura de lungime

L1 xor L2 xor ... xor LN

Prin ramura se intelege o succesiune de noduri x1, x2, ..., xn

in care xi este adiacent cu xi+1, xn este frunza iar x2, ..., xn-1

au grad 2.

Ajungem astel la un caz particular. Un arbore format dintr-o radacina

si mai multe ramuri. Dar acest caz este clar echivalent cu jocul initial

de nim.

Daca in jocul de nim avem gramezi de dimensiune X1, X2, ..., XN

atunci jucatorul care este la mutare castiga daca si numai daca

X1 xor X2 xor ... xor XN este != 0.

Demonstratiile teoremelor de mai sus se gasesc pe pagina web de mai sus.

La implementare, pentru compactarea nodurilor, se pot gasi componentele

biconexe. Orice componenta biconexa poate fi compactificata intr-un

singur nod. Odata arborele construit, rezolvarea este simpla.

Inapoi

© 2002 - 2003 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com