猜數字沒有「保證一次就猜中的方法」。因為第 1 次猜測時,沒有任何提示。不過,有「不管答案是什麼,一定能在固定次數以內猜中的方法」。如果把這個叫做必勝法,那麼最多幾次以內一定能猜中呢?
這裡用和 App「猜數字」相同的規則(符號是 0 到 9 共 10 種,答案和猜測都是各不相同的符號),針對 3 位和 4 位數的所有答案,計算各種策略要幾次才能猜中。次數把猜中的那一次也算進去。
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 位數的平均次數,整理在平均幾次能猜中?,把策略做成程式的方法,整理在用電腦來解題。
