﹝問題來源﹞
益玩社下學期接了一個國小益智教學的課，最近在準備課程時，想到了如下的問
題。
﹝問題背景﹞
不知何時，我懂了二進位後，知道若想在天平上，稱出重量為自然數的物體時，
只需準備1,2,4,8,16,32,64,...的砝碼各一顆。
日後，在翻牛頓雜誌時，意外的看到，利用砝碼放在天平的左右兩側時，只要準
備1,3,9,27,81...的砝碼各一顆，即可秤得所有重量為整數的物體。
由ax+by=1的整數解中，可知只要a,b互質時，只要準備足夠多的a克、及b克的砝
碼，即可秤得重為整數克的物體。
近在準備教材時，在《數學是啥玩意》一書中，看見這樣的問題，準備3個7克，
及足夠多的4克砝碼，就可稱出所有重量為整數克的物體。
﹝問題﹞
我試著想這樣的問題，若要稱出重為1,2,3,....,100克的物體，若只準備兩種砝
碼(如4g,7g)，要用那兩種砝碼各幾個，使得所需的砝碼數量最少。
﹝備註﹞
我直覺反應出的問題，也不太確定這問題解法是否有何技巧或有趣之處。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: zephyr (斷了線的風箏) 看板: puzzle
標題: Re: 【益智問題】天平稱重
時間: Sun Sep 1 22:38:28 2002
※ 引述《arist ( 川 )》之銘言：
[恕刪]
: 近在準備教材時，在《數學是啥玩意》一書中，看見這樣的問題，準備3個7克，
: 及足夠多的4克砝碼，就可稱出所有重量為整數克的物體。
這裡同理可以得到只要有 3個四克和夠多的七克就可以秤出所有的整數克物體
比如說 1~7克
1:( 2,-1) --> 1克可以用一邊放 2個四克, 一邊放一個七克量出來之意)
2:(-3, 2)
3:(-1, 1)
4:( 1, 0)
5:( 3,-1)
6:(-2, 2)
7:( 0, 1)
接下來秤8克只要用秤1克的方法再加上1個七克就可以
依此類推....
秤到 100克所需的砝碼數是 3個四克和 16個七克
100:(-3,16)
(可以看出每個 7k+2 和 7k+6 的需要最多的(k+2個)七克砝碼)
秤到7n克會需要 3個四克和n+1個七克
問題來了....有沒有比這種秤法更省砝碼數的方法呢?
如果用4個四克砝碼會怎麼樣呢?
首先可以節省的是16以後的7k+2
16:( 4, 0)
....
100:( 4, 12)
但是 7k+6 則無法節省
97:(-2, 15)
所以秤到100克需要 4個四克和15個七克
秤到7n克會需要 4個四克和n+1個七克
而到有5個四克砝碼的時候
連 20以後的 7k+6 也都可以節省了
20:( 5, 0 )
...
97:( 5, 11)
所以秤到100克需要 5個4克和14個七克
秤到7n克會需要 5個四克和n個七克
然後....就不用再討論下去了 ^_^
很容易可以發現,
增加1個4克的砝碼最多也只能節省1個七克砝碼
總共需要的砝碼數還是不變
: ﹝問題﹞
: 我試著想這樣的問題，若要稱出重為1,2,3,....,100克的物體，若只準備兩種砝
: 碼(如4g,7g)，要用那兩種砝碼各幾個，使得所需的砝碼數量最少。
結論
4g 3個, 7g 16個
或 4g 4個, 7g 15個
或 4g 5個, 7g 14個
或 4g 7個, 7g 12個
都是最省的作法....
--
我好像很閒的樣子....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.4.215
> -------------------------------------------------------------------------- <
作者: arist ( 川 ) 看板: puzzle
標題: Re: 【益智問題】天平稱重
時間: Sun Sep 1 23:07:31 2002
※ 引述《zephyr (斷了線的風箏)》之銘言：
: ※ 引述《arist ( 川 )》之銘言：
: [恕刪]
: : 近在準備教材時，在《數學是啥玩意》一書中，看見這樣的問題，準備3個7克，
: : 及足夠多的4克砝碼，就可稱出所有重量為整數克的物體。
: 這裡同理可以得到只要有 3個四克和夠多的七克就可以秤出所有的整數克物體
: 比如說 1~7克
: 1:( 2,-1) --> 1克可以用一邊放 2個四克, 一邊放一個七克量出來之意)
: 2:(-3, 2)
: 3:(-1, 1)
: 4:( 1, 0)
: 5:( 3,-1)
: 6:(-2, 2)
: 7:( 0, 1)
: 接下來秤8克只要用秤1克的方法再加上1個七克就可以
: 依此類推....
: 秤到 100克所需的砝碼數是 3個四克和 16個七克
: 100:(-3,16)
: (可以看出每個 7k+2 和 7k+6 的需要最多的(k+2個)七克砝碼)
: 秤到7n克會需要 3個四克和n+1個七克
: 問題來了....有沒有比這種秤法更省砝碼數的方法呢?
: 如果用4個四克砝碼會怎麼樣呢?
: 首先可以節省的是16以後的7k+2
: 16:( 4, 0)
: ....
: 100:( 4, 12)
: 但是 7k+6 則無法節省
: 97:(-2, 15)
: 所以秤到100克需要 4個四克和15個七克
: 秤到7n克會需要 4個四克和n+1個七克
: 而到有5個四克砝碼的時候
: 連 20以後的 7k+6 也都可以節省了
: 20:( 5, 0 )
: ...
: 97:( 5, 11)
: 所以秤到100克需要 5個4克和14個七克
: 秤到7n克會需要 5個四克和n個七克
: 然後....就不用再討論下去了 ^_^
: 很容易可以發現,
: 增加1個4克的砝碼最多也只能節省1個七克砝碼
: 總共需要的砝碼數還是不變
: : ﹝問題﹞
: : 我試著想這樣的問題，若要稱出重為1,2,3,....,100克的物體，若只準備兩種砝
: : 碼(如4g,7g)，要用那兩種砝碼各幾個，使得所需的砝碼數量最少。
: 結論
: 4g 3個, 7g 16個
: 或 4g 4個, 7g 15個
: 或 4g 5個, 7g 14個
: 或 4g 7個, 7g 12個
: 都是最省的作法....
嗯 蠻詳盡的
我這裡的另個疑問是 若用其他種方法
如 5g 6個 12g 10個 好像也可(我只大略計算 可能會有些誤差)
要選那兩種 才會使得 總砝碼數最少
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: zephyr (斷了線的風箏) 看板: puzzle
標題: Re: 【益智問題】天平稱重
時間: Mon Sep 2 04:15:14 2002
※ 引述《arist ( 川 )》之銘言：
: 我這裡的另個疑問是 若用其他種方法
: 如 5g 6個 12g 10個 好像也可(我只大略計算 可能會有些誤差)
: 要選那兩種 才會使得 總砝碼數最少
接著算 (我真是太閒了 >_< )
從前面的結論可以發現
當使用 p克和 q克兩種砝碼時 (p,q互質)
最節省的秤法之一是 floor(q/2) 個p克砝碼,
和 floor(N/q) + floor(p/2) 個砝碼
ex1. 4 和 7 的話, 需要 [7/2] = 3個 4g 和 [100/7]+[4/2] = 16 個 7g
ex2. 5 和 12的話, 需要 [12/2] = 6個 5g 和 [100/12]+[5/2] = 10 個 12g
(後面的數量可能會要再多一)
也就是 [p/2]越小越好 (p=2 or3)
而 q/2 + N/q >= 2(N/2)^0.5 (算幾不等式)
在這邊取個近似 有 q=13 or 14 or 15
考慮p,q互質, 較好的情況有 (3,13) (3,14) (2,13) (2,15)
比如說取 p=3 , q=13
這樣需要 6個3g和9個13g 共15個砝碼
又比如說取 p=2 , q=13
需要 6個2g和8個13g 共14個砝碼
取 p=2 , q=15
需要 7個2g和7個15g 也是14個砝碼
這應該就是最少的砝碼數了....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.7.13
※ 編輯: zephyr 來自: 61.224.7.13 (09/02 05:22)