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

這就是原問題的解了。