note: This article comes from the Internet. Please contact me via lethic@163.com if there is any infringement.
lethic@163.com.

Nim

n1
NimPennies
34532145
Chales Leonard Bouton

11

K12

Nim

Nim
Nim(Combinatorial Games)Impartial Combinatorial GamesICGICG12(move)3 4ICG3

Nim

P-positionN-positionPPreviousNNextmoveP-positionmoveN-position1.terminal positionP-position2.P-positionN-position3.N-positionP-position
positionspositionP-positionN-position

NimP-position(3,3)PPP-position(3,3)(0,3)(1,3)(2,3)(x,y)(y,x) (0,3)(0,0)(0,1)(0,2)(0,0)P-position(0,3)N-positionP-positionN-position(1,3)(1,1)P-position(1,1)(0,1)N-position(1,3)N-position(2,3)N-position(3,3)N-positionP-positionP-position

P-positionDPNim(a1,a2,…,an)O(a1*a2*…*an)Nim

(Bouton’s Theorem)Nim(a1,a2,…,an)P-positiona1^a2^…^an=0^(xor)

position

position 1terminal positionP-position2N-positionP-position3P-positionP-position

terminal position00

(a1,a2,…,an)a1^a2^…^an!=0aiai’a1^a2^…^ai’^…^an=0a1^a2^…^an=kaik1k1ai^k<aiaiai’=ai^ka1^a2^…^ai’^…^an=a1^a2^…^an^k=0

(a1,a2,…,an)a1^a2^…^an=0aiai’a1^a2^…^ai’^…^an=0a1^a2^…^an=a1^a2^…^ai’^…^anai=ai’aiai’

O(n)NimN-positionO(n)Nim

Nim