PageRank



轉移公告

計劃把 http://blog.hoamon.info/ 文章全部轉移至 http://www.hoamon.info/blog/ 這裡,而本 Blogger 站台的文章近 500 篇,我預計在 2014-12-31 前移轉完畢,完成後 http://blog.hoamon.info/ 將只作代轉服務,一律把舊連結如 http://blog.hoamon.info/index.html 轉成 http://www.hoamon.info/blog/index.html ,敬請舊雨新知互相走告。

新文章只發佈在 http://www.hoamon.info/blog/

何岳峰 敬上

2007年7月20日 星期五

數學證明:S 為一有 k 個元素的自然數組合,其元素們的和、積依序為 a、b。若 T 亦為一有 k 個元素的自然數組合,其元素們的和、積亦依序為 a、b,則 S=T。

例如在 { 1, 2, 3, 4, 5, 6, 1, 1 } 自然數組合中,其積為 720,和為 23 ,是 { 1, 2, 3, 4, 5, 6, 1, 1 } 所獨有的,找不到其他同為 8 個數的組合,其積與和也等於 720 與 23 。

如果個數不同的話則有可能擁有相同的積與和,如: {3, 12} 與 {1, 1, 4, 9} 的積同為 36,和同為 15 。

證明方式如下:

首先證明在兩個個數的自然數組合中,其擁有獨特的積與和

在 X * Y = A ; X + Y = B 兩條方程式下,必定只有 1 或 2 個解或是沒有解。

本階段以函式圖說明。如下圖


兩線的交合點只有一個。而下圖


則有兩個交點,其解為 X=2, Y=3 或是 X=3, Y=2 ,但以組合的角度來看,這兩個解屬於相同的涵義。

基本上, X * Y = A 是一個凹向上的曲線,其於直線的交點只有 0, 1, 2 三種情形。又因為 X, Y 是我們任意選取的自然數,所以不會出現 0 個解的情形。所以我們可知在 2 個數的自然數組合中,必定擁有獨特的積與和。

接下來,證明在 3 個數的自然數組合中也具有相同的特性:

方程式改寫如下:
( X * Y ) * Z = A'
( X + Y ) + Z = B'
=>
A * Z = A'
B + Z = B'
=>
A * Z = A'
A + Z = B' + C
而 C = A - B

A 為自然數的積,所以它也會是自然數,於是我們得到 { A, Z } 的積 A' 與和 B' + C 是獨特的,除了 A 與 Z 之外,無法產生相同的積與和。

=> { X, Y, Z } 的積與和也會是獨特的。

最後 N+ 1 個數的自然數組合皆可由 N 個數的自然數組合推得。所以我們得知「相同個數的自然數組合,其和與積是惟一的」。

8 則留言:

  1. 一、請把題目改成:
    在相同個數的自然數子集合中,其子集合的積、和數對解惟一。例如:{ 1, 2, 3, 4, 5, 6, 1, 1 }的積、和數對解為{720, 23}。

    二、後半段證明可以直說為:數學歸納法。前半段不是證明,因為只簡單的用兩個特例的圖形說明,無法證明當 X、Y 為任意數字時是正確的。

    其實前半證明也很簡單,國中數學基礎就夠了。
    我用反證法如下:
    X * Y = A, X + Y = B 若存在 m, n 屬於自然數且不同於 X、Y 任一數,而且 m * n = A, m + n = B
    則 X * Y = m * n → m = X * Y/n
    因為 X + Y = m + n
    所以 X + Y = X * Y/n + n
    (X + Y)n = X * Y + n^2
    n^2 - (X + Y)n + X * Y = 0
    (n - X)(n - Y) = 0
    n = X or n = Y 與假設矛盾
    故不存在自然數 m 與 n 符合題意

    給你參考。

    回覆刪除
  2. 我的前段證明是利用直線與一條凹向上曲線來作說明的,因為它們的交點只會有 0、1、2 個的三種情況。

    因為我們的題型設計所以不會出現 0 個交點的情形,而出現 1 個交點時代表 X = Y ,出現 2 個交點時,表示 X, Y 互換。

    既然不會出現 3 個以上交點,所以表示積、和數對解符合惟一的特性。

    這樣不算證明嗎?或者我只是文筆不好,沒讓你看懂。

    但你的證法的確比較簡潔。

    回覆刪除
  3. 有人問我,為什麼要寫這個無聊的證明呢!我與它有什麼關係?

    這關係可大了,如果沒有這個特性,我的研究所入學考試會少 20 分,這樣,我就得去唸朝陽營管,或許我會學的是 VB + 基因演算法,或許我永遠遇不到 Linux 及 Open Source 了。

    回覆刪除
  4. 數學的嚴格證明是需要說出因為這樣,所以所有的情況都適用的。意思就是要窮舉,你只舉出了兩個例子:X=3, Y=3和X=2, Y=3,對一篇報告來說都嫌少,所以我才會說不算證明。或者我應該說不算嚴格的證明,只能算是個合理的猜測而已。

    但是對你而言只要猜的對、用的好大概已經夠了,其實也不太需要什麼嚴格證明(要知道微積分這東西是大家先用了近百年才有嚴格證明出現的)。但是因為你要我找出你證明上有沒有漏洞,所以我才提出來的。

    回覆刪除
  5. 集合裡面的元素應該是不重覆的,所以 { 1, 2, 3, 4, 5, 6, 1, 1 } 這個集合應該寫成 {1,2,3,4,5,6}。但是從 hoamon 站長的文章看來,他的意思應該是希望元素可以重覆出現的,建議可以使用有限項的自然數數列來取代原來所說的集合。另外一個集合的和、積沒有一般性的定義,所以應該特別說明是元素相加、相乘。

    為了方便,在這邊先假設集合裡的元素是可以重覆出現的。在原來的題目裡似乎邏輯順序倒了過來,我想題目應該改為:「S 為一有 k 個元素的自然數子集,其元素們的和、積依序為 a、b。若 T 亦為一有 k 個元素的自然數子集,其元素們的和、積亦依序為 a、b,則 S=T。」

    同時站長整篇文章的兩個步驟合起來才算得上是數學歸納法,而不是只有後半段。因為數學歸納法就像在推骨牌,除了確定前一個骨牌倒下會推倒後一個骨牌以外,還要確定第一個骨牌會倒下,而站長的前半段就在做這件事。

    所以我想在前半段的證明中,可以先假設已有 S={x,y},其中 x*y=a、x+y=b,再假設 T={m,n},其中 m*n=a、m+n=b,再想辦法解釋 S=T。

    基本上我認為站長的想法是行得通的,只是在文字解釋不清而已。因為 x、y 為 t^2-bt+a=0 這個一元二次方程式的兩根,m、n 也是 t^2-bt+a=0 的兩根,因為 x、y 為已知數,故 t^2-bt+a=0 不會無解,所以 {x,y}={m,n}。直接跳到結論 {x,y}={m,n} 是快了點,就證明而言應該再把 case 細分,但我只是想表示我覺得站長原來的想法是個不錯的想法,只因為其中帶有幾何的直觀。

    對於小龍的反證我有個不解想請問小龍,就是為什麼要假設 m, n 不同於 X、Y 任一數?因為我看不出需要這樣假設的理由。

    我在 Ubuntu TW 看到站長的文章,剛好有興趣就跑過來回了一大堆,希望站長不要見怪啊 :-)

    回覆刪除
  6. cookeyholder的見解果然仔細,我個人受教了。

    關於您第一段的解說我一開始也有想要以n維自然數的定義域對應到二維自然數值域來取代,不知道您的看法怎麼樣?

    數學歸納法的說明只是為了要能精簡站長的證明,也就是說將後半段的證明改以數學歸納法說明比較省事,並非要把前半段割裂或除去,否則也不完整。

    至於我的證明方式只是在強調唯一性時常用的方法,就是假定非唯一,但和事實矛盾,因此唯一。並不是非得如此,因cookeyholder您用二次方程式的解法應該只能說明必定存在,而無法說明唯一的性質吧?

    另外關於站長的幾何直觀想法的確是不錯的,我自己也常常利用這種方法,但是畢竟不能算是嚴格的證明過程(也不能說錯,這點我想我已經修正),希望我的理解不會和您差太多,謝謝您的指教!

    回覆刪除
  7. to cookeyholder: 我比較希望有人指教我的文章,所以感謝你了。

    回覆刪除

Related Posts Plugin for WordPress, Blogger...