IBM Ponder This #077 · 2004 年 9 月

这是 2004 年 7 月和 2002 年 11 月转盘游戏的两个推广。给定 N,K≥2，隐藏状态 V 是长度为 N 的向量，各分量属于 {0,…,K-1}。

每一步你提出同样取值范围的向量 W。精灵秘密选择 J∈{0,…,N-1}，把 W 循环移动 J 位：Rot(W,J) 为 W 的后 N-J 项接上前 J 项。随后逐分量令 V=(V+Rot(W,J)) mod K。若 V 全为零，你获胜；否则继续。

第一部分（Joe Fendel）：哪些整数对 (N,K) 允许一个预先固定的有限 W 序列，无论初态和精灵选择如何，都保证执行过程中获胜？证明分类完整。

第二部分（Dan Dima）：固定 K=2，放宽目标为某一步 V 至少有 M 个零分量。对每个 N，能够保证实现的最大 M 是多少？研究 N 与 M 的关系。原题接受任意一部分的解答。

解答

认真尝试后再打开

待补充。