猜数字没有“一定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(全是新符号) | 约295 | 504 |
| 1045(2个旧符号+2个新符号) | 约254 | 408 |
一边挪动旧符号的位置,一边混进新符号,更能把候选分得好。可能是因为,知道第1次里有符号在答案里之后,把它换个位置再用,能同时得到位置方面的信息。另一方面,第1次是0A0B(剩下360种)时,计算结果也是“4567”这样的全新符号最好。
人可以用的“必胜法”的思路
要在脑子里直接照搬电脑的策略很辛苦,但思路可以用。
- 第1次随便猜。
- 第2次,把第1次已知在答案里的符号换个位置使用,并混进新符号。
- 从第3次起,选与提示不矛盾的排列。候选变少后,写出来比较。
App的目标次数(3位6次、4位7次),和上面计算中巧妙策略一定能做到的次数相同。如果能在目标以内猜中,就相当有水平了。包含5到7位在内的平均次数,请看平均几次能猜中?;把策略写成程序的方法,汇总在用电脑来解中。
