Diferente pentru teoria-jocurilor/w-numere intre reviziile #10 si #14

Nu exista diferente intre titluri.

Diferente intre continut:

Altfel spus, pozitiile superpierzatoare vor avea asociat indicatorul $SP$, iar cele supercastigatoare indicatorul $SC$. Eliminand toate aceste pozitii speciale vom obtine un graf in care toate pozitiile sunt normale. Daca aplicam algoritmul functiei $mex$ de determinare a valorilor Sprague-Grundy pe pozitiile ramase obtinem chiar valorile returnate de functia {$w$} pentru aceste pozitii.
Asemanator cu functia {$mex$}, o pozitie $x$ este pierzatoare daca si numai daca {$w(x) = SP$} sau {$w(x) = 0$}.
p{padding:0.1em 0.5em 0.5em 0.5em; margin:0.5em; border: 1px solid #666666;background-color:#E2E2E2}.
_Teorema_: Asemanator cu functia {$mex$}, o pozitie $x$ este pierzatoare daca si numai daca {$w(x) = SP$} sau {$w(x) = 0$}.
_Demonstratie_: Daca {$w(x) = SP$}, atunci evident $x$ este o pozitie de pierdere. Daca {$w(x)$} este numar natural si {$w(x) > 0$}, atunci este posibil ca jucatorul la mutare sa mute intr-o pozitie $y$ cu {$w(y) = 0$} (conform definitiei). Dintr-o pozitie {$w(x) = 0$} se poate muta numai in pozitii supercastigatoare sau in pozitii cu {$w(x) > 0$} (intr-o stare superpierzatoare nu se poate muta, deoarece in aceste stari se poate ajunge doar din stari supercastigatoare). Dat fiind faptul ca jocul este finit, se va ajunge la situatia in care din pozitia {$w(x) = 0$} nu mai exista decat mutari in pozitii {$SC$}.
p{padding:0.1em 0.5em 0.5em 0.5em; margin:0.5em; border: 1px solid #666666;background-color:#E2E2E2}.
_Teorema_: Fie un joc $G$ definit ca adunarea de tip $WTIA$ a jocurilor {$G{~1~}$}, {$G{~2~}$}, ... {$G{~p~}$}. Pozitia {$x$} din jocul {$G$}, care este un {$p$}-uplu de forma {$(x{~1~}, x{~2~}, ... x{~p~})$}, unde {$x{~i~}$} este starea din jocul {$G{~i~}$}, este pierzatoare daca si numai daca cel putin una din urmatoarele conditii este indeplinita:
 
1. exista un joc $i$ astfel incat {$w(x{~i~}) = SP$}
2. pentru orice joc $i$, {$w(x{~i~})$} este numar natural. In plus, {$w(x{~1~}) xor w(x{~2~}) xor ... xor w(x{~p~}) = 0$}.
 
_Demonstratie_: Vom verifica daca pentru aceasta impartire sunt indeplinite conditiile pentru $P$-pozitii si $N$-pozitii, prezentate 'aici':teoria-jocurilor/notiuni#pozitii. Daca exista un joc $i$ astfel incat {$w(x{~i~}) = SP$}, atunci starea $x$ este una terminala si este de pierdere. Mai mult, din orice pozitie pierzatoare neterminala conform impartirii de mai sus, oricum am efectua o mutare, vom ajunge intr-o pozitie castigatoare.
 
Toate pozitiile terminale x au un subjoc xi care este SP, altfel s-ar mai putea efectua mutari. Daca un jucator este intr-o pozitie pierzatoare atunci w(x) = SP sau {$w(x{~1~}) xor w(x{~2~}) xor ... xor w(x{~p~}) = 0$}. Primul caz a fost analizat mai sus. Daca un jucator muta in orice subjoc k atunci fie va muta intr-o pozitie supercastigatoare in acel joc, fie va muta intr-o pozitie y cu w(y) � w(xk). In abele cazuri va muta in pozitii castigatoare.
Daca un jucator este intr-o pozitie castigatoare atunci w(x) = SC sau w(x1) xor w(x2) xor ... xor w(xp) diferit de {$0$}. In primul caz va exista un subjoc xk astfel incat w(xk) = SC. Un jucator va putea muta in acest subjoc intr-o pozitie superpierzatoare. Daca suma nim a w-numerelor subjocurilor este diferita de 0 atunci un jucator poate gasi cu usurinta o mutare care sa o modifice in 0, procedand similar jocului Nim.
 
h4. Aplicatie pe jocul NIM pe nivele
 
 
p{margin:1em; padding: 0.5em; height: 45px; border-top: 1px solid silver;}=.
'Notiuni de baza':teoria-jocurilor | 'Jocul NIM':teoria-jocurilor/jocul-nim | 'Numere Sprague-Grundy':teoria-jocurilor/numere-SG |
'Adunarea jocurilor':teoria-jocurilor/adunarea-jocurilor | '*w-numere*':teoria-jocurilor/w-numere | 'Aplicatii si probleme':teoria-jocurilor/probleme

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.