Re: [中學] 一個最小總合的證明
※ 引述《coldlian (coldlion)》之銘言：
: 想請問一下各位先進，
: 當我今天有n筆record，以及m個selectivity {S}
: 我該如何證明說
: sum = (n*S1)+(n*S1*S2)+....+(n*S1*S2*S3*....Sm)
: S1,S2,...,Sm 為 {S}中的元素，而且並不重複
: 當我欲取得最小的sum值時，
: S1,S2,S3,...,Sm 的順序為從 {S} 依序從最小的元素取到最大的元素
: 式子不知道該如何列比較恰當，也不知道該如何證明才好
: 感謝各位板友 :)
若存在連續兩個 S 元素 S_i S_{i+1} 有 S_i > S_{i+1}
則
sum1 = n*S1 + n*S1*S2 + ...
+ n*S1*S2*...*S_i + n*S1*S2*...*S_i*S_{i+1} + ...
+ n*S1*S2*...*Sm
跟
sum2 = n*S1 + n*S1*S2 + ...
+ n*S1*S2*...*S_{i+1} + n*S1*S2*...*S_{i+1}*S_i + ...
+ n*S1*S2*...*Sm
相比 (後者是對調 S_i S_{i+1} 的結果)
由於 S_i > S_{i+1} 故 sum1 > sum2
因此前一種排列不可能為最小
故使 sum 最小的排列不可能有連續元素前項大於後項
也就是這排列只能是非嚴格遞增順序 #
--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.32
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1406629677.A.A0F.html
討論串 (同標題文章)