Nim游戏

例:

我们拥有 (n) 堆石子,每次可以选择一堆石子,从中取走至少一颗石子。规定两个人轮流取石子,取走最后一枚石子的人是获胜者。

结论 : 当且仅当 (a_1oplus a_2oplusdotsoplus a_{n-1}oplus a_n = 0) 时,先手必输,否则先手必胜。

有两条结论可以帮助我们理解证明这个结论:

(a_1oplus a_2oplusdotsoplus a_joplus dots oplus a_{n-1}oplus a_n = 0) 时,对于 (forall j in left[ 1,n ight] , forall a_j' < a_j) 都有 (a_1oplus a_2oplusdotsoplus a_j'oplus dots oplus a_{n-1}oplus a_n eq 0)

(a_1oplus a_2oplusdotsoplus a_joplus dots oplus a_{n-1}oplus a_n eq 0) 时,(exists j in left[1,n ight] , a_j' < a_j) 使得 (a_1oplus a_2oplusdotsoplus a_j'oplus dots oplus a_{n-1}oplus a_n = 0)

咕~

原文地址:https://www.cnblogs.com/nao-nao/p/13774303.html