Re: [問題] 硬幣交易
※ 引述《LPH66 (-858993460)》之銘言：
: ※ 引述《EIORU ()》之銘言：
: : 某個地方的市場
: : 規定東西交易時
: : 買賣雙方最多可拿出兩個硬幣
: 先理解為雙方可"各"拿出兩個硬幣
: : Q1
: : 當貨物價額為1~10元
: : 則該地方的貨幣面額必須有哪些
: : 使得貨幣種類最少
: 很容易證明兩種硬幣不夠
: 因為最多只會有 a, b, 2a, a+b, 2b, |a-b|, |a-2b|, |2a-b|, |2a-2b| 九種
: 所以至少要三種 而原推文已有 {2,3,7} 一解
: : Q2
: : 當貨物價額為1~30元
: 我剛剛找到一組解: {3,5,14,21}
: 1 = 3 + 3 - 5 16 = 5 + 14 - 3
: 2 = 5 - 3 17 = 3 + 14
: 3 = 3 18 = 21 - 3
: 4 = 5 + 5 - 3 - 3 19 = 5 + 14
: 5 = 5 20 = 5 + 21 - 3 - 3
: 6 = 3 + 3 21 = 21
: 7 = 5 + 5 - 3 22 = 14 + 14 - 3 - 3
: 8 = 3 + 5 23 = 5 + 21 - 3
: 9 = 14 - 5 24 = 3 + 21
: 10 = 5 + 5 25 = 14 + 14 - 3
: 11 = 14 - 3 26 = 5 + 21
: 12 = 3 + 14 - 5 27 = 14 + 21 - 3 - 5
: 13 = 5 + 14 - 3 - 3 28 = 14 + 14
: 14 = 14 29 = 14 + 21 - 3 - 3
: 15 = 21 - 3 - 3 30 = 14 + 21 - 5
: 其實只是從「一定要兩元硬幣嗎」的想法出發的 (因為 2 在後面其實受限滿大的)
: 一開始的 {3,5} 可以得到 1~8 和 10
: 下一個數字要把範圍弄大一點所以選了 9+5=14 (正好讓 14-4 = 10 和 5+5 互補)
: 再往上在 15 停了 所以這次為了補多一點選了 15+6=21
: 然後後面多利用兩大找兩小就出來了
: 是不是有三種硬幣的解要再看看了...
三種硬幣的解不存在
證明：延用LPH66的方法
: 很容易證明兩種硬幣不夠
: 因為最多只會有 a, b, 2a, a+b, 2b, |a-b|, |a-2b|, |2a-b|, |2a-2b| 九種
以上文字我改用圖形表示
●●●
●●●● Ｏ 是座標原點，紅點是a，綠點是b，則黃點是a+b，藍點是-a-b
●●Ｏ●● 每個點都有對應的幾a加減幾b的值，總共18個點
●●●● 但是像黃點跟藍點必一正一負，最多只能有9個正數。
●●●
那三個硬幣可能有
●●● ●● ●
●●● ●●●● ●●● ●●
●●● ●●●● ●●Ｏ●● ●●●● ●●●
●● ●●● ●●●● ●●●
● ●● ●●●
C=2 C=1 C=0 C=-1 C=-2
總共54/2=27個點，小於30。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.25.198
討論串 (同標題文章)