三數之和 - 拼圖

※ 引述《Ryow (哈扣)》之銘言：
: 可能還要多算幾項才能找到x^n+y^n+z^n的一般式吧 我放棄 O_Q
又是數學課時間啦 XD

這題六年半前在數學版有一個很漂亮 (而且可以推廣) 的解答 #1I3wFtCD (Math)

(原發問者刪文了, 但由這篇回文所留下來的原文可以知道是一模一樣的題目

差在發問者問四次方, 這裡 (因為一些原因) 是問五次方)

我有試著解釋過他的答案 (在 #1I3ySPhw (Math) )

而這個回答者後來在 #1I4A6Hwc (Math) 有解釋過他的做法

這裡我就來重新敘述一下他這個很漂亮的答案 XD

那麼以下是防雷頁































回答者提到的這個東西稱做 Newton's Identities

https://en.wikipedia.org/wiki/Newton's_identities

它是將 n 個數的 k 次方和和這 n 個數的基本對稱多項式關連起來的關係式

這裡用和這題有關的 3 個數來寫

3 個數 x y z 的對稱多項式有以下這幾個:

e1 = x+y+z, e2 = xy+yz+zx, e3 = xyz

為了後面延伸起見, e4 以後定為 0 (等下會說為什麼)

如果把 k 次方和也給個名字:

p1 = x+y+z, p2 = x^2+y^2+z^2, p3 = x^3+y^3+z^3, ...

那麼 Newton's Identities 就可以寫作:

1*e1 = p1
2*e2 = e1*p1 - p2
3*e3 = e2*p1 - e1*p2 + p3
4*e4 = e3*p1 - e2*p2 + e1*p3 - p4
...

(上面這串式子只要對 n 個數做和上面類似的 e_k p_k 定義那式子依然成立)

這式子是怎麼來的呢? 這裡以 3 個數為例:

考慮以 x y z 為根的 t 的三次多項式 (t-x)(t-y)(t-z) = 0

它的展開式就是大家熟知的根與係數關係 t^3 - (x+y+z)t^2 + (xy+yz+zx)t - xyz = 0

或者用上面的 e 代號寫成 t^3 - e1*t^2 + e2*t - e3 = 0

那因為 x y z 代入成立, 所以有

{x^3 - e1*x^2 + e2*x - e3 = 0
{y^3 - e1*y^2 + e2*y - e3 = 0
{z^3 - e1*z^2 + e2*z - e3 = 0

然後把這三條式子加起來, 看出什麼了嗎 XD

加起來的結果可以用 p 代號代換成 p3 - e1*p2 + e2*p1 - e3*3 = 0

把 e3 寫到右邊去就是上面的第三條式子了

(這就是我在 #1I3ySPhw (Math) 所給出的解釋)

其他條式子可以可以對更多個數進行同樣的操作導出來

例如四個數 x y z w 可以導出第四條 p4 - e1*p3 + e2*p2 - e3*p1 + e4*4 = 0

而有趣的是, 這個第四條式子若令 w = 0 則有

(x^4+y^4+z^4) - e1*(x^3+y^3+z^3) + e2*(x^2+y^2+z^2) - e3*(x+y+z) = 0

這個關係式也可以用另一種方式導出來:

上面提到 x y z 成立的關係式 t^3 - e1*t^2 + e2*t - e3 = 0

全式乘以 t 變成 t^4 - e1*t^3 + e2*e^2 - e3*t = 0

然後和上面一樣, 代入 x y z 之後三式相加, 就得到了四行前的那條關係式了!

這個代法一方面解釋了為什麼上面 e_k 在超過 n 之後要定為 0 的理由

另一方面也給出了對 n 個數計算後面的 p 項的遞迴關係式

可以看到, 如果中間改乘 t 的其他次方的話

會得到對三個數來說的這一系列的關係式:

p4 = e1*p3 - e2*p2 + e3*p1 (同時也能看到這其實根本就是把原來的關係式中
p5 = e1*p4 - e2*p3 + e3*p2
p6 = e1*p5 - e2*p4 + e3*p3 e_k = 0 的項給去掉所得到的式子)
....

也就是說, 只要能求出 e1 = x+y+z, e2 = xy+yz+zx, e3 = xyz 的值

那就可以用這個關係式一項一項把後面的項給求出來

那麼回到原題, 要怎麼求這些對稱多項式的值呢?

對三個數可能大家還是可以直接平方展開集項

不過這裡我們可以再次回到一開始的關係式

e1 = p1 這沒問題

2*e2 = e1*p1 - p2 把它寫開其實會發現大家跟它應該熟到不行:

2*(xy+yz+zx) = (x+y+z)*(x+y+z) - (x^2+y^2+z^2)

而 3*e3 這條式子上面解釋過了, 這個方法也即是一個求出 xyz 的方法

題目的條件 p1 = 1, p2 = 2, p3 = 3

所以 e1 = 1, e2 = (1*1 - 2)/2 = -1/2, e3 = ((-1/2)*1 - 1*2 + 3)/3 = 1/6

因此對這題而言, 遞迴關係式就是 p_k = 1*p_{k-1} + (1/2)*p_{k-2} + (1/6)*p_{k-3}

於是就能依序求出

p4 = 1*3 + (1/2)*2 + (1/6)*1 = 25/6
p5 = 1*(25/6) + (1/2)*3 + (1/6)*2 = 6
p6 = 1*6 + (1/2)*(25/6) + (1/6)*3 = 103/12
...

那至於這題為什麼要求五次方?

大概只是因為接下來的數列正好在五次方和有個整數吧 XD

稍微用個軟體算了一下, 再後面的項看起來是沒有整數了

====

常在解遞迴關係式的人可能會對上面這一大篇感到似曾相識, 這並不是錯覺

因為上面這些步驟其實和解遞迴關係式的方法是正好相反的運算方向:

如果從上面這條遞迴關係式開始

p_k = 1*p_{k-1} + (1/2)*p_{k-2} + (1/6)*p_{k-3}

列出它的特徵方程 t^3 - t^2 - (1/2)t - 1/6 = 0

解出它的三根 x y z 然後寫出 p_k 的通式 a*x^k + b*y^k + c*z^k

再由給定的 p_1 = 1, p_2 = 2, p_3 = 3 求得係數是 a = b = c = 1

從遞迴式推得通式的底數

而這題 (以及 Newton's Identities) 則是由通式和初始項推得遞迴式

這兩個操作是同一件事的兩個不同運算方向



























: → charlie1667: 這雇主真黑，居然有負的報酬 12/22 03:16
: → charlie1667: 好我錯了，並不能算負數 雇主真會鑽法律漏洞 12/22 03:18
那麼就用個推文當做頁末防雷頁

我個人是覺得這比負的還黑就是了 XD

--
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.

--