最少秤幾次? - 拼圖

※ 引述《bb511 (我沒空打牌)》之銘言：
: 這問題搞不好大家都知道 也看過了
: 不過我查一下 好像沒po過??
: ---------------------------------------------
: 有十二袋裝滿金幣的袋子
: 每袋中的金幣一樣多
: 其中一袋裝滿假金幣
: 真金幣每枚10公克，假金幣每枚9公克。
: 最少要秤幾次才能秤出假金幣？

這題相信很多人知道答案了，不過為了向經典題目致敬，還是正式回答一下。

首先，這個題目重點在於，我們必須知道假幣與真幣間的重量差為多少。很多人會把它跟
「用天平找假幣」的題目弄混，認為只要知道「較輕」、「較重」的資訊即可，事實上這
樣是無解的（若要求一次秤出的話）。必須還要知道它「或輕、或重幾克」才行。

此外，本題通常不考慮每袋金幣是否有數量上的限制，也不考慮磅秤是否夠大，能讓我們
不管拿多少金幣都秤得了（我相信日後一定會有腦筋急轉彎的題目鑽此漏洞）。

言歸正傳

原始的問題很簡單，首先在十二袋金幣上分別編上一到十二的編號，再分別從裡頭拿出相
同數量的金幣。把這十二堆的金幣一起拿去秤，然後看它比標準重量差多少即可判斷假幣
在哪一袋裡。

如果假幣在第一袋裡，那秤出來的重量一定比標準重差１公克；若假幣在第二袋裡，由於
我們從裡頭拿出兩枚，所以秤出的重量一定比標準重少２公克，其餘依此類推。

這個問題的變形是，如果假幣可能不只一袋，能否在只秤一次的情況找出呢？

答案是肯定的。

首先一樣先編號，接著只要從每袋之中取出「２的（編號減一）次方」數量的金幣，一起
拿去秤即可。實際的數量如下：

１、２、４、８、１６、３２、６４、１２８、２５６、５１２、１０２４、２０４８

（２的０次方、２的１次方……２的１０次方、２的１１次方）

這些一共是４０９５（用〔２的Ｎ＋１次方〕－１算較快）

也就是標準重是４０９５０公克。

接著只要看秤出來的重量差幾克，然後再算它是由哪些數字組成即可。表面上這邊的計算
有點麻煩，但只要用「２進位」的觀念下去算就行了。

例如秤出來的重量是３９５８７克，那麼──

40950-39587=1363

把1363轉成２進位得：

2｜1363 ....餘 1
────
2｜681 ....餘 1
────
2｜340 ....餘 0
────
2｜170 ....餘 0
────
2｜85 ....餘 1
───
2｜42 ....餘 0
───
2｜21 ....餘 1
───
2｜10 ....餘 0
───
2｜5 ....餘 1
───
2｜2 ....餘 0
───
1

所以1363（10進位）＝010101010011（2進位。最前面補0，是為了湊齊12位數）

由於1在第1、第2、第5、第7、第9、第11位上，所以相應編號的金幣是假的。

1363＝1+2+16+64+256+1024


用第二種方法當然也可以用來解決起初的問題，但它的缺點就是必須要拿出許多金幣來測
量（例如本題需取出4095枚）不像第一個方法那樣「輕便」，可以說是各有利弊。

這些東西相信大家都知道，不過問題太經典，所以還是打來當做記錄。


puzzlez
2007/11/22

--