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

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$}.
_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$}.
(vmenu)* _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:
 
# exista un joc $i$ astfel incat {$w(x{~i~}) = SP$}
# pentru oricare subjoc i w(xi) ≠ SP, w(xi) ≠ SC si w(x1) ⊕ w(x2) ⊕ ... ⊕ w(xn) = 0
 
unde x ∈ X si xi ∈ Xi.
 
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.