猜數字的答案,是從 10 種符號(這裡是 0 到 9 的數字)中,挑出各不相同的符號排列而成。來數數看有幾種。
算法
以 3 位數為例。
- 第 1 個數字,0 到 9 共有 10 種。
- 第 2 個數字不能和第 1 個相同,所以有 9 種。
- 第 3 個數字不能和第 1、第 2 個相同,所以有 8 種。
全部是 10 × 9 × 8 = 720 種。每多一位,就再乘上剩下的數字個數(7、6、5……)。
各位數的候選數
| 位數 | 算式 | 候選數 |
|---|---|---|
| 3 位(★1) | 10×9×8 | 720 |
| 4 位(★2) | 10×9×8×7 | 5040 |
| 5 位(★3) | 10×9×8×7×6 | 30240 |
| 6 位(★4) | 10×9×…×5 | 151200 |
| 7 位(★5) | 10×9×…×4 | 604800 |
7 位數的答案超過 60 萬種。隨便亂猜一次就猜中的機率,小於 60 萬分之 1。
可以重複數字的情況
如果規則是同一個數字可以用好幾次,每一位都是 10 種,所以 3 位數是 10 × 10 × 10 = 1000 種,4 位數是 10000 種。
| 位數 | 數字不重複 | 數字可重複 |
|---|---|---|
| 3 位 | 720 | 1000 |
| 4 位 | 5040 | 10000 |
猜數字「符號各不相同」的規則,不只是讓候選稍微變少,也讓 A 和 B 的算法更容易理解。因為如果有兩個相同的數字,就很難分辨哪一個算 B(和 Mastermind 的差別)。
提示會讓候選怎麼減少?
猜一次之後,只有與出現的提示不矛盾的答案會留下來。3 位數猜「012」時,把各種提示下剩下的候選數全部數出來,結果如下。
| 提示 | 剩下的候選 |
|---|---|
| 0A0B | 210 |
| 0A1B | 252 |
| 0A2B | 63 |
| 0A3B | 2 |
| 1A0B | 126 |
| 1A1B | 42 |
| 1A2B | 3 |
| 2A0B | 21 |
| 3A(猜中) | 1 |
加起來剛好是 720。最常出現的是「0A1B」,720 種裡有 252 種(35%)。猜一次之後剩下的候選,最多也只有 252 種。
這樣的減少重複幾次,即使是 720 種,只要猜得聰明,一定能在 6 次以內猜中(猜數字有必勝法嗎?)。
位數增加,會難多少?
候選數從 3 位數到 7 位數增加了 800 倍以上。但猜中所需的次數並沒有增加那麼多。這大概是因為提示的種類隨位數增加,一次猜測能得知的資訊也變多。App「猜數字」的目標次數,3 位數是 6 次,7 位數是 10 次。
