上一道數學謎題
下一道數學謎題

需要幾隻豬數學謎題

答對率:50%
有1000桶給豬喝的水,其中一桶有劇毒,外觀及氣味均無法分辨劇毒水是哪一桶,而豬喝到了劇毒的水15分鐘後會死亡,若要保證在一小時以內找到哪一桶水含有劇毒,至少需要幾隻豬?
cheny2017-04-30提供(2017-05-17修改)
來源:朋友
看答案
5隻豬

解析

我要編輯
bbbnnn(奇風), Sept_w...等 3 人共同編輯 | 歷史版本
答案已作修正,5隻豬即可。
 
已知使用 n 隻豬測試 m 次,
最多能從 (m+1)ⁿ 桶水中找出有毒的那一桶。
(詳細證明請看下方 george617 的留言,這裡不贅述)
忽略思考與操作的時間的話,一共能測 4 次,
4 隻豬只足夠從 625 桶水中找出來,
5 隻豬則能夠從 3125 桶水中找出來,
不過其實 5 隻豬可以只測 3 次就好,
因為 1024 仍然超過 1000。

至於實際操作的方法,
在證明公式的過程中其實已經有詳細描述了,
這裡就直接舉個例子來試著幫助大家理解好了。

====== 第一次測試 ======
水桶先編號成 1~1000, 假設其中的第 880 桶有毒。
由於第一次測試有 5 隻豬活著,先把這些水分成 32 組:
  • 第 32 組:最多 243 桶,
    包含第 1~243 桶,有 243 桶。
  • 第  1, 2, 4, 8, 16 組:每組最多 81 桶,
    依序包含第 244~324 桶, 第 325~405 桶, ..., 第 568~648 桶,都有 81 桶。
  • 第 3, 5, 6, 9, 10, 12, 17, 18, 20, 24 組:每組最多 27 桶,
    依序包含第 649~675 桶, 第 676~702 桶, ..., 第 892~918 桶,都有 27 桶。
  • 第 7, 11, 13, 14, 19, 21, 22, 25, 26, 28 組:每組最多 9 桶,
    依序包含第 919~927 桶, 第 928~936 桶, ..., 第 1000~1008 桶,
    不過水桶只有 1000 桶,第 28 組其實只有第 1000 桶。
  • 第 15, 23, 27, 29, 30 組:每組最多 3 桶,
    依序包含第 1009~1011 桶, 第 1012~1014 桶, ..., 第 1021~1023 桶,
    不過水桶只有 1000 桶,所以這裡每組都沒有水桶。
  • 第 31 組:最多 1 桶,
    包含第 1024 桶,不過水桶只有 1000 桶,所以這組其實沒水桶。
把豬編號成 1~5,
第 1 隻豬喝第 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 組的所有水桶的水,
第 2 隻豬喝第 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31 組的所有水桶的水,
第 3 隻豬喝第 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31 組的所有水桶的水,
第 4 隻豬喝第 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31 組的所有水桶的水,
第 5 隻豬喝第 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 組的所有水桶的水。
經過 15 分鐘後,發現第 3,5 隻豬死了,
可以回推出有毒的水在第 20 組中,也就是第 865~891 桶中。

====== 第二次測試 ======
把這組內的水桶重新編號成 1~27,所以現在變成是第 16 桶有毒。
這次只剩 3 隻豬活著,所以把這些水分成 8 組:
  • 第 8 組:最多 8 桶,
    包含第 1~8 桶,有 8 桶。
  • 第  1, 2, 4 組:每組最多 4 桶,
    依序包含第 9~12 桶, 第 13~16 桶, 第 17~20 桶,都有 4 桶。
  • 第  3, 5, 6 組:每組最多 2 桶,
    依序包含第 21~22 桶, 第 23~24 桶, 第 25~26 桶,都有 2 桶。
  • 第 7 組:最多 1 桶,
    包含第 27 桶,有 1 桶。
把豬編號成 1~3,
第 1 隻豬喝第 1, 3, 5, 7 組的所有水桶的水,
第 2 隻豬喝第 2, 3, 6, 7 組的所有水桶的水,
第 3 隻豬喝第 4, 5, 6, 7 組的所有水桶的水。
經過 15 分鐘後,發現第 2 隻豬死了,
可以回推出有毒的水在第 2 組中,也就是第 13~16 桶中。

====== 第三次(最後一次)測試 ======
把這組內的水桶重新編號成 1~4,所以現在變成是第 4 桶有毒。
這次只剩 2 隻豬活著,就把豬編號成 1~2,
第 1 隻豬喝第 1, 3 桶水,
第 2 隻豬喝第 2, 3 桶水。
經過 15 分鐘後,發現豬都還活著,
可以回推出第 4 桶的水是有毒的。
 
根據 下方 platinum500a 提出的另一種證明計算公式的方法,
則可以得到一個可能比較簡明的測試辦法。

已知使用 5 隻豬已足夠,
先把這 1000 桶水編號成 0~999,
接著轉為五進制的五位數(不足五位則補 0),
接著看這個數的每一位,
第 i 高位的數字如果是一個正整數 d,
代表要在第 d 次測試時混入要給第 i 隻豬喝的水。

例如:編號是 485 的那桶水,轉五進制得到 (03420)₅
代表這桶水第 1 隻豬不會喝到
第 2 隻豬在第 3 次喝到,第 3 隻豬在第 4 次喝到
第 4 隻豬在第 2 次喝到,第 5 隻豬不會喝到

最後,要找出是哪一桶水有毒應該就不是件難事了。
假如第 1 隻豬在測 1 次後死,第 2,3 隻豬測完沒事,
第 4 隻豬在測 4 次後死,第 5 隻豬在測 1 次後死,
就代表是編號 (10041)₅=646 的那桶水有毒。
3,932
上一道數學謎題
下一道數學謎題