由AMC10题目延伸出组合博弈论的经典问题

 

本年的AMC10 B卷中,出现了一道背景较深刻的问题:

每月一讲:由AMC10题目延伸出组合博弈论的经典问题

来看看机构的老师怎样带领我们破题:

 

每月一讲:由AMC10题目延伸出组合博弈论的经典问题

 Kayles Game

事实上,此问题是组合博弈论当中的一个经典问题:Kayles Game。它是Henry Dudeney在1908年发明的,最初是说击打保龄球,而Kayles的发音与法语“quilles”很接近,故后称为Kayles Game。Kayles Game与Nim很类似,Nim指的是两个玩家轮流从不同的堆 ( piles ) 取走或移除物体。

每一回合 ( round ) 每个玩家必须移走至少一个物体,并且可以移除任意数量的物体,只要它们来自一堆。

事实上,组合博弈论有一个非常重要的定理刻画了这种相似性,也即著名的Sprague-Grundy定理。它陈述:“Every impartial game under the normal play convention is equivalent to a one-heap game of Nim, or to an infinite generalization of Nim.”(其中impartial指player 1与player 2之间唯一区别是轮次,而normal play convention指拿走最后一个者判胜,one-heap指Nim中的一堆,在有限博弈中,大可以忽略infinite generation)。

使用Nim-value和Nim-sum的计算方法,我们可以递归地找到Kayles问题的Nim序列:

每月一讲:由AMC10题目延伸出组合博弈论的经典问题

 

每月一讲:由AMC10题目延伸出组合博弈论的经典问题

 

有了Nim-value,就可以知道所有Nim-sum非0的初始条件都是先手必胜,原因在于Kayles Game中若只有一堆砖头,先手可以造出镜像局面给后手从而不败

而 ( B ) 中 ( 6 , 2 , 1 ) 的Nim-sum = 3 ⊕ 2 ⊕1 = 0

 

每月一讲:由AMC10题目延伸出组合博弈论的经典问题

学会了Nim方法和Sprague-Grundy定理后,老师为大家留下了一道课后作业,来试试看求如下游戏的Nim值:

On a rectangular board, 2 players take turns placing dominoes either horizontally or vertically until no more dominoes (1×2) can be placed. The first player unable to make a move loses.

(Hint: 2×n board has a nimber of 0 for 2/n and nimber of 1 for 2+n)

 

【竞赛报名/项目咨询请加微信:mollywei007】

上一篇

从斐波那契数列看线性递推数列通项公式的求法

下一篇

从韦东奕不等式看中国不等式界的卧虎藏龙

你也可能喜欢

  • 暂无相关文章!

评论已经被关闭。

插入图片
返回顶部