星期一, 11月 05, 2007

數學好好玩

GMAT中我最喜歡算數學,因為它大部分都是國中程度。大學曾有好一段時間都在教國中生數學,舉凡因式分解、方程式、簡單幾何(三角形、圓形等)的全等相似與角邊關係,以及排列組合、機率等,涵蓋了數學這領域的基本觀念及四則運算。當然,都是用手算。尤其研究所以後,幾乎我所需的運算都是透過電腦執行,但親手算數學才能體會數學在你掌心中把玩的樂趣,不斷練習還能增加對數字的靈敏度,感覺聰明了一倍!國中數學當然簡單,但也不是那麼理所當然。想當年我們從考卷、參考書和補習班中也一定做過不少艱澀的難題,這麼難,對國中生來說多做無益,但那是一種挑戰,至少我就見過不少優秀學生不吃飯不休息也拼了命要解一道題,終於解出來後,在他們臉上一定高掛兩條得意的眉毛,兼裂一口笑容。其實數字有很多特性都是在一些很有意思的題目中才發現的,比如底下這道題:

A student has a balance scale and five metal weights of 1,2,4,8, and 16 ounces, respectively. If the student can determine the exact weights of n objects, each of a different weight, by using one or any combination of these five metal weights, what is the maximum value of n?

老師說了三種解法。第一種:想五顆砝碼可以任取一顆、二顆到五顆,所以n等於C5取1加C5取2加到C5取5,等於31。第二種:想五顆砝碼每一顆都可以選擇要【取】或【不取】,所以答案為2連乘五次(2的五次方)減掉五顆都不取的情況,等於31。但這兩種方法都不能保證每一種取法所得到的砝碼重量不會重複,重複的話n就不是31了,到最後還是得回去檢查。第三種:一個一個算。所以老師有說等於沒有說,總之就是要逐數字去算。難道真是如此嗎?

砝碼可以堆出1,2,3盎司的重量,這一眼就可以看出來了。接下來我們有一顆4盎司的砝碼,這表示到7盎司之前的重量我們都能秤出來,因為大於4盎司的重量可以分解成4盎司+1,2,3盎司,最多可以加到7。同理,既然1到7盎司的重量都能秤,我們又有一顆8盎司的砝碼,所以15盎司之前的重量也都沒問題,最後再加上16盎司的砝碼,我們可以秤到31。

如果你對數字還算敏感,一定注意到砝碼的重量為:2的0次方、2的1次方、2的2次方……,也只有砝碼成2的次方排列才能準確無誤地秤出每一種重量,但為什麼呢?

一個公式:2的0次方+2的1次方+……+2的n次方=2的n+1次方-1。

直覺告訴我可以從上述公式出發,只是我也還沒有想到一個完整的解釋,就由大家來動動腦筋吧!

語:用MathType打出來的公式貼不上來,只好請大家辛苦些。

外一章:
費曼所處的時代電腦有一個房間大,所以他們常常得用雙手計算龐雜的數字,也因此鍛鍊出超強的計算能力,如何在很短的時間內猜對答案是大師們必備的功夫。很難想像原子彈是在那樣的年代中「算」出來的!

6 則留言:

小熊 提到...

學長:

我個人覺得這邊的邏輯是這樣的:

首先,你有了 {1, 2} 這兩個法碼之後,我們便可以組成 3 公斤重量,所以在有了 1, 2, 3 之後,在 多了 {4} 這法碼之下,我們最多便可以組到 7, 並且其中的 5, 6, 7 的組成都沒有重複用到 1, 2, 4 的法碼,因為 5 = {1}+{4}, 6={2}+4, 7=3+{4}={1}+{2}+{4}。所以,

在上面情況之下,我們利用了 1, 2, 4 這三個法碼組成了一條 [1,7] 的數列,並且每一個重量的組成不會用到同一個法碼兩次。

所以在有了 [1, 7] 這樣子沒問題的數值下,並且其中的數值確定完全由 {1, 2, 4} 這三個法碼組成,所以在多了 {8} 這法碼之下,我們最多可以新得到 [9, 15] 這些數值,並且可以很放心其中的數值符合題目要求,所以配上原本就有的 [1, 7] 還有新的法碼 {8} 跟新得到的數列 [9, 15] ,我們便可以得到[1, 15] 的數列了,並且 [1, 15] 數值符合題目要求。亦即,在原本就有的數值 [1, 7] 之下,多了 {8}, 我們便可以組成 [1, 15] 的數值。

所以,再給定了 {1, 2, 4, 8} 之下,我們又得到了一條可以放心的數列 [1, 15],所以同理可知,我們在多了 {16} 之下,我們便又可以得到 [17, 31] ,所以在多了 {16} 之下,我們共可以得到 {1, 31} 的數字。

所以依此類推下去,在有了 {32} 之後,我們可以累積到 [1, 63] ,在有了 {64} 之後,我們便可以累積到 [1, 127], 之後便可以依此類推。

所以我的想法是說, {1, 4, 8, 16, ...} 是題目給定的,如果我們可以從一開始就確定 [1, 2, 3] 沒問題,則自然的 [5, 6, 7] 也沒問題,因為只是題目給的 {4} 加上這些令人放心的 [1, 2, 3] 而已,所以在多了 {8} 之下,我們便可以很自然的延伸到 15 去,後面就可以放心了。所以我只是想說,只要一開始沒問題,多了題目給的值延伸的新數列自然也沒問題,所以便可以依照這邏輯一直延伸下去。

所以這是我的想法,不知道有沒有問題?

小熊 提到...

學長:

我補充一下,就是因為 2 這數字具有2的0次方+2的1次方+……+2的n次方=2的n+1次方-1 這樣子的特性,所以我們才有辦法再得到 3 的時候碰上題目給定的 {4} 而可以繼續延伸,在得到 7 的時候碰到給定的 {8} 而可以繼續延伸,後面依此類推。

localki 提到...

小熊:

我的第四段基本上就是你的意思,只是為什麼2具有2的0次方+2的1次方+……+2的n次方=2的n+1次方-1的特性,可以幫助我們推論出「每一種排列方式的重量都不會重複」的結論?

我後來想想答案很簡單。因為按2次方排列的N顆砝碼共有2的n+1次方-1種排列方式(或說是取法),同時我們又發現砝碼共可以排出2的n+1次方-1個相異的數字,不就表示一種取法對一個數字而互不重複嗎!

小熊 提到...

學長:

我是想去證明說,他們彼此是不會重複的,就是因為我們知道他們彼此是不會重複的情況,才可以知道的是因為排法共有2次方排列的N顆砝碼 2的n+1次方-1 種,又因為剛好是會有2的n+1次方-1 個數字,所以可以知道是一對一的。但是前提是我覺得,我們得先證明出來其不會重複才是。

而2具有2的0次方+2的1次方+……+2的n次方=2的n+1次方-1的這公式,我覺得是因為在我們知道了2次方排列的N顆砝碼會有 2 的n+1次方-1 種排法,又因為剛好是會有2的n+1次方-1 個數字之下,我們便可以利用這公式 知道只要幾個法碼就可以有幾個不重複的數字。

localki 提到...

小熊:

我同意你對於如何「不重複」的論證,那跟我的想法一樣。但你的邏輯順序似乎有些紊亂。你看,我們是先證明:(1)有2 的n+1次方-1 種排法;(2)有2的n+1次方-1 個相異數字。所以得到「不會重複」的結論。

但你回文第一段卻說要【先】「知道他們彼此是不會重複的」,【才】「可以知道…排法共有…2的n+1次方-1 種」,【又】「剛好…有2的n+1次方-1 個數字」,【所以】「可以知道是一對一的」。而你最後一對一的結論不就是你說要先知道的不重複嗎?

其實重不重複不影響排法。假設現在有1,3,4 ounces三顆砝碼,排法為C3取1+C3取2+C3取3=7種,但只能得到6個相異數字,所以必有重複。

小熊 提到...

學長:

事實上我們的說法是一樣的,只是我表達的不好,像【先】「知道他們彼此是不會重複的」中的「重複」指的是數字組成得符合題目要求,不是指一對一,而我們知道一對一是因為知道了有了有2 的n+1次方-1 種排法又加上剛好有著符合題目要求的數字2的n+1次方-1 個,所以才知道一對一。

我那一段話的【先】「知道他們彼此是不會重複的」只是想去說明我們得先證明出數字的組成符合題目要求。而後面的」,【才】「可以知道…排法共有…2的n+1次方-1 種」,【又】「剛好…有2的n+1次方-1 個數字」才是證明過程。

問題出在我表達上面用了不適合的詞語「重複」來形容 「題目的要求」。

我想,等到有機會當面聊,也許可以更清楚吧。