問題描述:
有13個球和一個沒有刻度的天平,已知13個球中有一個球重量和其他12個球不一樣,當然
另外12個球等重.而且這13個球的外觀一模一樣,不能從外觀上分辨.要求稱最少的次數,
將這個重量不同的球找出來
Darkness:其實就這些東西要解答的話是很考記憶力的,如果你需要的話,可以找一支筆
在球上做標記哦..
解答如下:
{H=Heavy Ball L=Light Ball O=Unknown Information S=Standard Ball}
將13球分成 4個 4個 5個 3組.將兩組4個球稱1次 則
1> 若不平衡,則目標球必在兩組4個球中 HHHH--LLLL OOOOO _F(8,2)
2> 若平衡,則目標球必在5個1組中 SSSSSSSS OOOOO _F(5,2)
<1 將重球(沉下天平一邊的球)組4個球編為H 輕球組4個球編為L. 另5個球編為標準球S
1.2> 從4個重球中隨機選2個H 輕球中選一個L 標準球中選一個S 編為一組 HHLS
從剩下2個重球中選一個H 3個輕球中選一個L 4個標準球中選一個S 編為一組HLSS
剩下的重球輕球編為一組 HLL
<1.2 HHLS--HLSS 稱第2次
1) 若左重右輕,則可能為左的HH重或右的L輕 1.2.1>
2)若右重,則可能為左的L輕或右的H重 1.2.2>
3)若平衡,則目標球在剩下的HLL三球中 1.2.3>
<1.2.1 將HHL中的H,H 拿出稱第3次,其中重的即為目標球 (想想為什么)
若平衡,則L為目標球 ...解法<1.2.1>
{注:解法<1.2.1>對HLL三球問題也適用}
<1.2.2 將HL中任一個與標準球S稱,平衡為另一球,不平衡為該球
<1.2.3 解法見 解法<1.2.1> 略
則F(8,2)問題討論完畢
<2 F(5,2) 問題 OOOOO 5個球均無已知信息
2.1> 5球分為3組
取5個球中2個與一個標準球組成一組 OOS
取剩下3個球中1個與2個標準球組成一組 OSS
剩下兩個球一組 OO
OOS--OSS 稱一次
可能左重右輕(HHS--LSS) 2.1.1>
或可能左輕右重(LLS--HSS) 2.1.2>
或平衡(SSS-SSS) 2.1.3>
<2.1.1 即有HH及L 參考解法<1.2.1>
<2.1.2 即有LL及H 參考解法<1.2.1>
<2.1.3 將LL中任一個與標準球S稱,平衡為另一球,不平衡為該球
則F(5,2)問題討論完畢
而有F(8,2)及F(5,2)解決有F(13,3)問題解決
故最少稱量次數為 3
此上即為13球問題解答過程
P.S. 該問題是由F(12,3)問題解答推廣來的,雖多了一個球,不過核心
思想還是換湯不換藥:把一個大的問題劃分成若干個子問題,然后通過
對每個子問題的解決,得到大問題的解決.. 有點神似動歸哈....
個人認為不可能再推廣到F(14,3)問題,不過不會證明.敬請高人指教.