• Nim 游戏
    • 内容：nn 堆石子，两个玩家，轮流选一堆取走若干，无法操作者败
    • 结论：当且仅当石子数量异或和为 00，先手必败，否则先手必胜
    • 归纳证明：
      • 异或和为 00 为必败状态，没有石子异或和为 00
      • 当前状态异或和非 00，则下一步一定可以走到异或和为 00 的状态
      • 当前状态异或和为 00，则下一步一定不能走到异或和为 00 的状态
  • 有向图游戏与 SGSG 函数
    • SG(u)=mex(SG(v1),SG(v2),SG(v3),SG(v...))SG(u)=mex(SG(v_1),SG(v_2),SG(v_3),SG(v_{...}))
    • 当前状态 SGSG 函数为 00，则为必败状态，否则为必胜状态
    • 证明：
      • 向 SGSG 值更大的点走是无用的：对方玩家可以走回当前 SGSG 值
      • 向 SGSG 值更小的点走：与 Nim 游戏等价
    • 结论：有 nn 个有向图游戏，先手必胜当且仅当 nn 个游戏起点 SGSG 函数值异或和非 00
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. Edited & Maintained by sstzer
  3. Worker 0, 25ms
  4. Powered by Hydro v4.19.1 Community