Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

谁能帮解释一下下面这段话? 怎么找到the nim-value that each position of every Impartial Game has

Posted by alpc04 at 2006-07-02 16:01:35 on Problem 2425
In Reply To:是不是根据已知的图推出一个公式,然后把初始位置带进去得到答案,那个公式就是SG? Posted by:alpc04 at 2006-07-02 14:20:37
Nim-Value 
Every position of every Impartial Game has a nim-value, making it equivalent to a Nim-Heap. To find the nim-value (also called the Sprague-Grundy Number), take the Mex of the nim-values of the possible moves. The nim-value can also be found by writing the number of counters in each heap in binary, adding without carrying, and replacing the digits with their values mod 2. If the nim-value is 0, the position is Safe; otherwise, it is Unsafe. With two heaps, safe positions are  where . With three heaps, (1, 2, 3), (1, 4, 5), (1, 6, 7), (2, 4, 6), (2, 5, 7), and (3, 4, 7). 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator