日誌2013-11-13 20:40

數學問題－沒有刻度的尺(解答)

在昨天的貼文"數學問題－沒有刻度的尺"中, 小樣提到一本書中的某個數學問題, 這個問題希望我們算出 4 把尺的長度, 使得這 4 把尺可以利用相加相減的方式, 來得到 1 公分到 40 公分間的任意整數長度. 那本書上只有解答: 4 把尺長度分別為 1 公分, 3 公分, 9 公分及27 公分. 但卻沒有任何解答過程的說明. 以下是我自己補上的解答過程.

若4把尺的長度分別為x, y, z, w, 且 x > y > z > w. 則題目的量測方式, 相當於我們必須用以下的方式組合出介於1到40間的任意整數.

利用1把尺: w	只能表示w長度
利用2把尺: z (+- w)	能表示z, z+w, z-w等3種長度
利用3把尺: y (+- z) (+- w)	能表示9種長度
利用4把尺: x (+-y) (+- z) (+- w)	能表示27種長度

其中, 像(+-w)這種寫法, 表示可以是空白, +w 或 -w.

由上表可以發現, 這4把尺所能組成的長度, 根本就是40種, 因此要用4把尺表示出1到40公分的所有長度, 必須是尺的所有種組合均表示某個1到40間的長度, 且不可重複.

又因為尺的組合長度只有40種, 且觀察可知其中最長的是 x + y + z + w, 因此 x + y + z + w 必須等於40, 且 x + y + z  為次大的數, 因此它必須為39, 故 w = 1.

再觀察 z + w, z, z - w, w, 它們表示 4 種不同的長度, 且其中可以肯定的大小關係為 z + w > z > w, 但 z - w 與 w 的大小關係無法確定, 若 z - w > w 則 z > 2w, 否則 z < 2w. 但是 w = 1 且 z 為正整數, 所以 z < 2w 必不成立, 故 z - w > w, 故知 z + w > z > z - w > w.

因為 x + y + z + w = 40, 且  z + w > z > z - w > w, 故知
x + y + (z + w) = 40  (最大的數: 40)
x + y +    z       = 39  (次大的數, 須為39)
x + y + (z - w)  = 38  (第3大的數)
x + y +    w      = 37  (第4大的數)
(因為尺的所有種組合均表示某個1到40間的長度, 且不可重複)

故知 z = 3, x + y = 36. 又 y - z - w = 5 (它是加入y後最小的數), 故 y = 9, x = 27.

---

事實上小樣不是這樣想到的, 我是先發現它的解答中, 前面的短尺必能形成 1 到某數的連續長度, 例如 1, 3 可以形成 1到4, 而1, 3, 9可以形成1到13的連續整數長度, 因此發現了以下規則:
(算是從解答反推的, 有點作弊嫌疑)
將短尺標號為 1 到 k, 且其長度為L1, L2, ..., Lk, 若這k把尺可以形成 1 到 n 間的任意整數長度, 今添加 k+1 號尺, 且其長度為 2n + 1, 則 1 到 k+1 號尺可形成 1 到 3n+1 間的任意整數長度.
證明(數學歸納法):
當 k = 1 時, 1把尺僅能量出一個長度, 因此 L1 = 1, n = 1.
   k + 1 = 2, 2號尺的長度為 2n+1=3, 此時1, 2號尺一起用可量出 1 到 3n+1=4 間的任意長度
故 k = 1 時以上敘述成立.
假設有 k 把尺時, 以上敘述成立.
當加入第 k+1 把尺, 且其長度為 2n+1 時
  (a) 第 k+1 把尺不使用, 由上面的假設得知此時可量出 1 到 n 間的長度
  (b) 使用第 k+1 把尺, 此時可量出的長度為 L(k+1) - n 到 L(k+1) + n 間的長度,
       又L(k+1) = 2n + 1, 故可量出 n+1 到 3n+1 間的長度
由(a), (b)兩部份可知, 假設有 k 把尺時, 以上敘述成立.
由數學歸納法可知, 當 k 為自然數時, 以上敘述均成立.

7

13

LINE 分享

相關創作

Gard of War漫畫翻譯-[HololiveEN短漫]不是只有數學

LeetCode - 1492. The kth Factor of n　解題心得

LeetCode - 1104. Path In Zigzag Labelled Binary Tree　解題心得

留言

• 2013-11-13 20:46風雲破：
  很厲害的人尊稱神人..而您是女生..我能尊稱您神女嗎?嘻嘻..被揍飛..緊酸....

  2013-11-13 20:49小樣：這是高中數學, 加上閒閒亂想的時間, 哪是什麼神人.. [e24]

  2013-11-13 20:50小樣：最近有很多古怪的新聞, 看來小雲你會很忙喲..

• 2013-11-13 21:01風雲破：
  哈哈 我才沒管那麼多呢..又不住海邊..現在我只關心那條狗何時會下台而已..投票投了國民黨一輩子..現在居然希望那條狗下臺..真諷刺

  2013-11-13 22:42小樣：反正一定是2016年呀.

• 2013-11-13 21:04そうたつ：
  完全看不懂.............[e27]

  2013-11-13 21:11小樣：數學歸納法好像國三還高一教的, 我自己也忘了. 其他的就是一些不等式跟邏輯推理..

• 2013-11-13 21:18小鳥：
  啊，神厲害

  2013-11-13 22:40小樣：弄超久, 如果是考試早就掛掉了.

• 2013-11-13 21:31҉紳҉士҉：
  跨謀0.0 高一真的會教到這個嗎!?

  2013-11-13 22:40小樣：會教數學歸納法, 至於這種有些變種的題目應該是不會出現, 數學歸納法在高中是跟數列級數一起出來的, 題目也都是數列級數的:
  http://goods.ruten.com.tw/item/show?21204277530722
  在高一下 [e24]

• 2013-11-13 21:3319750401：
  我們只有教三角函數六個 跟一堆公式...

  2013-11-13 22:40小樣：http://goods.ruten.com.tw/item/show?21204277530722
  在高一下 [e24]

• 2013-11-13 22:4219750401：
  那本我有
  P.S.我讀高職
• 2013-11-13 23:13小鳥：
  數學老師看完題目5秒就有答案了= =

  2013-11-13 23:17小樣：哇哦, 可真強.. 不愧是數學老師 [e24]

  2013-11-13 23:18小樣：你怎麼會這麼晚還聯絡數學老師呢?

• 2013-11-13 23:19小鳥：
  補習班的，我問老師為什麼，他說自己慢慢想= =

  2013-11-13 23:23小樣：啊, 那我違背了老師的好意.. [e27]
  鳥兒沒練習到.

• 2013-11-13 23:24小鳥：
  沒關係的@@
• 2013-11-14 08:41風雲破：
  其實是老師只背過答案..算法其實也不會..所以叫鳥兒自己想..我猜應該是這樣
• 2013-11-14 08:42風雲破：
  ㄚ就是無法忍受到2016阿
• 2013-11-15 11:49小鳥：
  老師：只能加-用二進位。能加減-用三進位

• 送出