这个其实简单呀

格数若为2的幂，所有格编号为0到2^k-1，
记所有正面硬币所在格的编号的逻辑异或为a，钥匙所在格的编号为b
翻动编号为a XOR b的格的硬币之后，所有正面硬币所在格的编号的逻辑异或就会变成b

格数不是2的幂的情况，设为n。
记正面朝上的硬币为A，反面朝上的硬币为B，
设犯人看到所有的2^n种由A和B组成的字符串时
分别要猜钥匙在1~n号格中的某个格
则必有一格至多只对应int(2^n/n)种硬币状态
能通过一次翻动变成这int(2^n/n)种硬币状态之一的状态至多有n*int(2^n/n)种
从而对于剩下的2^n mod n种状态，如果钥匙在这一格，则无法猜对

【 在 littlestone9 (小石头) 的大作中提到: 】
: 标  题: Re: 囚徒猜钥匙问题
: 发信站: 水木社区 (Tue Mar  9 13:19:45 2021), 站内
:
: 大概明白你的意思，这句话可以忽略，不用管监狱长怎么做
: 只需要想囚徒是否有必胜策略就行了
: 【 在 GGGGDDDDK 的大作中提到: 】
: : 是没啥用呀，只要这个策略有非零概率不能成功找到就不是有效的
: : 而且问题是——对有些题目来说，“策略有漏洞”的理由是非构造性的
: : 所以我认为那句话可能反倒多余了——
: : ...................
:
: --
:
: ※ 来源:·水木社区 http://www.newsmth.net·[FROM: 117.107.131.*]
--
修改:GGGGDDDDK FROM 122.139.1.109
FROM 122.139.1.109