球馆里有一排球瓶,凯尔先生最爱考较来客:每轮您出手,可以击倒任意一根瓶(直球),也可以击倒两根相邻的瓶(双瓶球)——但绝不能碰倒不相邻的两根。击倒的地方留下缺口,瓶列就此断成两段,此后两段各自为政。谁击倒最后一根瓶谁赢。
这个游戏叫 Kayles,名字来自法语 quilles——正是「球瓶」的意思。
凯尔斯游戏由英国最伟大的谜题大师 Henry Dudeney(1857–1930)发明,收在他的名著《坎特伯雷谜题集》(The Canterbury Puzzles)第 73 题里。Dudeney 与美国的 Sam Loyd 并称 19 世纪两大谜题家,他喜欢把纯数学藏进小游戏里——凯尔斯就是最经典的一件。
凯尔斯是「无偏博弈」:双方走法完全相同,轮到谁无子可动谁就输。这类游戏有统一的理论——每个局面都对应一个整数 Grundy 值(也叫 nimber):
局面必败 ⟺ Grundy 值 = 0。
而一个「拼起来」的局面(比如被击断的两段瓶列、或几条球道),其 Grundy 值就是各部分的按位异或。
设瓶列长 n。第一手把瓶列从正中劈成两段等长的:n 为奇数就击倒正中间那根,n 为偶数就击倒正中间相邻的两根。此后无论对手在左边怎么打,您就在右边照做同样的一手(镜像策略)。
于是每一轮对手都有得打、而您永远跟得上——最后一根瓶必落在您手里。n≥1 的单道,先手稳赢。
单列长度 n 的 Grundy 值 G(n) 满足递推:把这一手拆成左右两段,取它们 Grundy 值的异或,再对所有这些可能取「最小未出现值」(mex)。算出来是这样一串(OEIS A002186):
Guy 与 Smith 在 1956 年给出了完整分析,证明这串值从 n=71 起周期为 12——无限长的序列,竟由 12 个数循环讲完。
凯尔斯不只是一道谜题。在 Dots and Boxes(点格棋)这类经典对局里,残局的「长链」争夺常常可以化简成凯尔斯局面——所以想真正下好点格棋,就得先懂凯尔斯。
这也解释了它为何在组合博弈论教材里长盛不衰。
把「2 根相邻」改成「2 根任意」就得到 Dawson's Kayles(八进制博弈 0.07);把胜负条件倒过来(无法出手者赢)是「反规则版」,由业余数学家 William Sibert 于 1973 年解出、1989 年才发表。凯尔斯本体则是八进制博弈 0.77,成为这一类游戏的标杆样本。