2007年11月25日 星期日

Mahalanobis 的問題

在 Wikipedia 上介紹數學天才 Ramanujan 的文章中,提到一個有趣的問題:

假設你在一條街道上,有 n 間房子,路牌號碼是 1 ~ n。其中有一間房子(號碼 x),它的左邊所有房子的路牌號碼總和,和它右邊的房子的路牌號碼總和相同。如果 n 在 50 至 500 之間,那麼 n 和 x 各是多少?

文章中提到 Ramanujan 很快就利用連分數解出了這個問題,讓他的室友 Mahalanobis 非常驚訝。

當然,Ramanujan 是數學天才。不過這個問題讓我覺得很有意思:它看起來算是相當簡單,我想可能小學生也能聽懂。不過這個問題倒底要怎麼解呢?

考慮 x 左邊的房子,即號碼 1 ~ x-1 的房子,其路牌號碼總和就是 x(x-1)/2。它右邊的房子,路牌號碼總和是 n(n+1)/2 - x(x+1)/2。這兩個數字要一樣,所以:

x(x-1)/2 = n(n+1)/2 - x(x+1)/2

-> x^2 = n(n+1)/2

所以,問題變成,要找出一個平方數(即 x^2),它同時也是一個三角數(即 n(n+1)/2)。

這個問題其實就蠻古老的,例如有名的阿基米德分牛問題,也有類似的要求。解法的關鍵是,一個正整數 m 若是三角數,則 8m+1 會是一個平方數,反之亦然。所以,因為 x^2 是一個三角數,所以 8x^2 + 1 會是一個平方數,設它為 y^2,這樣會得到一個 Pell's equation:

y^2 - 8x^2 = 1

解 Pell's equation 的確是會用到連分數,這個例子中會需要用到 sqrt(8) 的連分數。不過這個式子倒是有個很明顯的解,就是 y = 3, x = 1。

要求出更多的解,除了用連分數之外,也可以用下面的方法:

y^2 - 8x^2 = (y + sqrt(8) x) (y - sqrt(8) x) = 1

因此

(y + sqrt(8) x)^n (y - sqrt(8) x)^n = 1

n 是任意正整數。也就是說,假設已經有一組解(例如 y = 3, x = 1),就可以很容易計算出更多的解。比如說:

(3 + sqrt(8))^2 = 17 + 6 sqrt(8)

所以 y = 17, x = 6 也是一組解。

現在有了 x,就需要算出 n,因為題目要求 n 是 50 ~ 500 之間。算出 n 就容易多了:因為

n(n+1)/2 = x^2

-> n^2 + n = 2x^2

所以要算出 n,只需要把 x 乘上 sqrt(2),再取整數部份即可(因為 n^2 < 2x^2 且 (n+1)^2 > 2x^2)。所以,x = 6 的時候 n = 8。很容易驗證這個答案是正確的(1 + 2 + ... + 5 = 15,7 + 8 = 15)。另外也可以注意到因為 y^2 = 8x^2 + 1,所以

y^2 - 1 = 8x^2

-> (y + 1) (y - 1) / 4 = 2x^2

-> (y + 1) / 2 * (y - 1) / 2 = 2x^2

所以如果 n = (y - 1) / 2 則 n (n + 1) = 2x^2,也就是要求得的 n。

要計算出 50 ~ 500 之間的 n,需要再找更大的 x:

(3 + sqrt(8))^3 = 99 + 35 sqrt(8) -> x = 35, n = 49

(3 + sqrt(8))^4 = 577 + 204 sqrt(8) -> x = 204, n = 288

這就是原問題的解了。