猜数字没有“一定1次猜中的方法”。因为第1次猜测时,没有任何提示。不过,有“无论什么答案,都一定能在固定次数以内猜中的方法”。如果把这叫作必胜法,那么最多几次以内一定能猜中呢?

这里用和App“猜数字”相同的规则(符号是0到9共10种,答案和猜测都是各不相同的符号),对3位和4位的所有答案,计算了各个策略用几次猜中。次数把猜中的那一次也算作1次。

3种策略

  • 策略A(按顺序选不矛盾的排列):在与目前所有提示都不矛盾的排列中,猜最小的那个。比较接近人用纸玩时的做法。
  • 策略B(把最坏情况压小):每次猜测时,看出现的各种提示如何划分答案候选,选“剩得最多的那一组最小”的排列。
  • 策略C(把平均压小):每次猜测时,选使剩余候选数的平均(候选数的平方和)最小的排列。

策略B和C,也会用与提示矛盾的排列来猜。即使已知猜不中,只要能把候选分得好,也是划算的。第1次猜测选哪个都一样,所以3位从“012”、4位从“0123”开始(因为任何排列,只要互换符号和位置,都会变成同样的形态)。

3位的结果(720种答案全部)

策略平均最坏
A 按顺序选不矛盾的排列约5.27次9次
B 把最坏情况压小约5.12次6次
C 把平均压小约5.07次6次

用策略B和C,无论什么答案都能在6次以内猜中。策略A平均也约5.3次,但运气不好的答案会用到9次。

4位的结果(5040种答案全部)

策略平均最坏
A 按顺序选不矛盾的排列约5.56次9次
B 把最坏情况压小约5.34次7次
C 把平均压小约5.27次7次

4位时,用策略B和C,无论什么答案都能在7次以内猜中。策略C中,用了7次的答案在5040种中只有86种,接近一半在5次猜中。

策略C的次数答案数
1次1
2次4
3次59
4次568
5次2423
6次1899
7次86

这里给出的,是这3种策略的结果。如果有更巧妙的策略,平均还有可能更小。

第2次不一定“全用新符号”最好

人玩的时候,第1次和第2次只用不同的符号来猜,容易理解,也推荐这样做(猜数字的窍门)。不过,计算之后发现,它并不总是最好的。

4位时,第1次的“0123”得到0A1B(剩下1440种),比较第2次的候选,结果如下。

第2次剩余的平均最坏的剩余
4567(全是新符号)约295504
1045(2个旧符号+2个新符号)约254408

一边挪动旧符号的位置,一边混进新符号,更能把候选分得好。可能是因为,知道第1次里有符号在答案里之后,把它换个位置再用,能同时得到位置方面的信息。另一方面,第1次是0A0B(剩下360种)时,计算结果也是“4567”这样的全新符号最好。

人可以用的“必胜法”的思路

要在脑子里直接照搬电脑的策略很辛苦,但思路可以用。

  1. 第1次随便猜。
  2. 第2次,把第1次已知在答案里的符号换个位置使用,并混进新符号。
  3. 从第3次起,选与提示不矛盾的排列。候选变少后,写出来比较。

App的目标次数(3位6次、4位7次),和上面计算中巧妙策略一定能做到的次数相同。如果能在目标以内猜中,就相当有水平了。包含5到7位在内的平均次数,请看平均几次能猜中?;把策略写成程序的方法,汇总在用电脑来解中。