※ 引述《adamchi (adamchi)》之銘言：
: 2.有900個實數,每個數的絕對值不超過2/3且它們的立方和是0,
: 求它們和的最大值
: 答:200
這問題我還挺感興趣給中學生是怎麼做的。因為我用的手段不是中學生的範疇了


假設那900個實數為 X1, X2 ...... , X900
用 X = [X1, X2 ...... , X900] 來表示這900個數

900
定義 f(X) = ΣXi
i=1

那我們想要做的問題就是

maximum f(X)

subject to ΣXi^3 = 0 ,

Xi^2 - 4/9 <= 0


首先，X的 domain 是 closed and bounded， 所以X絕對存在極大值

接著，對於這個問題列出 KKT condition，可以得到，達成極大值的 X 必須滿足
Link:https://bit.ly/3n1tuya

存在 {λi | 1<=i<=900} 和 μ>= 0 使得

-1 + 2λiXi + 3μXi^2 = 0 for all i ....... (1)
λi(Xi^2 - 4/9) = 0 for all i ....... (2)
ΣXi^3 = 0 ........(3)

這些等式同時成立

(i) 如果 μ= 0
從 (1) 可得知 2λiXi = 1 → λi ≠ 0
而 λi ≠ 0 則可以從 (2) 得出 Xi 們要不是 2/3 就是 -2/3
那麼從 (3) 我們可以知道這情況下各自是 450 個，f(X) = 0

看得出來這並不是太有趣的結果

(ii) 假設 μ> 0 (這邊才會得到比較有趣的結果，但也比較長)

這次我們從 (2) 切入。對於任意 i in {1,2,3,...,900}，
λi ≠ 0 → Xi = 2/3 or -2/3

那 λi = 0 呢？ 這個就可以從 (1) 得到 Xi = 1/√(3μ) or -1/√(3μ)

這邊開始比較有趣囉
https://i.imgur.com/ot2Iyi8.png

如果我們令 α = 1/√(3μ), 那麼在 μ >0 的情況下，
滿足 KKT condition 的 Xi們的數值只能是 α,-α,2/3,-2/3

這個 α 本身要大於零，而且我們還可以進一步限制 α < 2/3。
為什麼呢？ 因為如果 α = 2/3 ，就跟 (a) 的結果一樣了

假設這些 Xi中，有 a 個是 α
b 個是 -α
c 個是 2/3
d 個是 -2/3

這時候 f(X) = α(a-b) + 2/3*(c-d) ......(4)

ΣXi^3 = α^3(a-b) +8/27*(c-d) = 0 ......(5)
a+b+c+d = 900 ......(6)
a,b,c,d are non-negative intergers

(5)可以得到 2/3(c-d) = -α^3(a-b)*9/4
把這個結果帶入 (4) 可以得到

f(X) = (a-b)α(1-9/4α*2) .....(7)

到目前為止沒用到 (6) 的限制，這樣能弄出東西就見鬼了。

從(6)可以得到:

900 = a+b+c+d = (a-b) + 2b + (d-c) + 2c

= (a-b) + 27/8*α^3*(a-b) + 2b+2c by (5)
→ (a-b)(1+27/8*α^3) = 900-2b-2c
→ (a-b) = 900-2b-2c / (1+27/8*α^3) ......(8)

將(8)帶入(7)可得到

f(X) = (900-2b-2c)*α(1-9/4α*2)/(1+27/8*α^3) ...... (9)

這裡呢，我們也不用考慮 900-2b-2c <= 0 的情況，
因為這還不如(i)看到的 f(X) 的情況

讓我們把(9)裡面 α 的部分拿出來看

α(1-9/4α*2)/(1+27/8*α^3)
= α(1-3/2α)(1+3/2α)/[(1+3/2α)(1-3/2α+9/4α^2)]

= α(1-3/2α)/(1-3/2α+9/4α^2)

= -2/3 + 1/( 27/4*(α-1/3)^2 + 9/8 )

上面這個α的部分，在 α = 1/3 的時候會有最大值 2/9

也就是說

f(X) = (900-2b-2c)*α(1-9/4α*2)/(1+27/8*α^3)

<= (900-2b-2c)*2/9

<= 900 * 2/9 (畢竟 b,c 都要 >=0)

= 200

我這樣在(ii)寫了一大串，到底寫了什麼？綜合起來就是在說，

在滿足 KKT condition (1)(2)(3) 且 μ> 0 的情況下，
Xi們只能是 1/√(3μ),-1/√(3μ),2/3,-2/3 其中一種數值
而且 f(X) 不會超過 200

那f(X)到底有沒有可能在這種情況下達到 200？
有，就是 800 個 1/√(3μ) = 1/3 和 100 個 -2/3


所以這個問題的極大值就是 200

--
角卷綿芽首次個人Live： Watame Night Fever!! in Zepp Tokyo
https://pbs.twimg.com/media/E9PIgJ7VkAUExEa.jpg
入場時間：台灣時間 2021/10/12 (星期二) 下午 4:30
官網購票連結：https://watame1stlive.hololive.tv/tickets/

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.135.233 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1634515284.A.599.html
以他的做法，是要湊出這個沒錯
那個做法問題在於他多用了一個 Xi必須要是 -2/3 和 2p/3 的條件，
但並沒有證明考慮這樣的Xi就足夠
※ 編輯: arrenwu (98.45.135.233 美國), 10/18/2021 18:21:55