Re: [中學]高中數學

[arrenwu (不是綿芽的錯)]

※ 引述《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
推 Starvilo    : https://i.imgur.com/GcnEM6q.jpg
→ Starvilo    : 網路解法但看不懂如何想法。109學科能力中投題目
推 LPH66       : 上面第二行少等號, 9x^3-3x+2/3"="(x+2/3)(3x-1)^2
→ LPH66       : 然後我猜它的想法是設法湊出 ax^3+cx+d >= 0
以他的做法，是要湊出這個沒錯
→ LPH66       : 這樣全部求和後就有立方和跟總和可以套關係
→ LPH66       : 那至於為什麼要湊 (x+2/3)(x-1/3)(x-1/3) 就不知了
→ LPH66       : 從形式上猜, 或許是從 x>-2/3 起, 設法消掉二次項
→ LPH66       : 還要保持範圍內恆正
推 Starvilo    : 了解～
→ LPH66       : 再繼續猜下去的話, 前篇的設 -2/3 和 2p/3 可能也是
→ LPH66       : 類似的推算 (用 2p/3 去解出那個 1/3 來)
那個做法問題在於他多用了一個 Xi必須要是 -2/3 和 2p/3 的條件，
但並沒有證明考慮這樣的Xi就足夠
推 vectorlog   : 總感覺柯西可以
※ 編輯: arrenwu (98.45.135.233 美國), 10/18/2021 18:21:55