弱爆了的我求助數學大神


最近做的工作中涉及到一個小的數學問題,想把它記錄在這里。

這個問題可以簡化為這樣:有一個包含\(n\)個隨機實數(\(a_{1}, a_{2}, \ldots, a_{n}\))的集合\(A\)。我希望它滿足兩個條件。 條件1:所有元素都大於等於零。 條件2:所有元素之和(記為\(s\))小於等於某個大於零的實數\(p\)。由於這個集合\(A\)的元素都是隨機的,為了使它滿足這兩個條件,我對它進行兩個操作。操作1:使\(A\)的所有元素都減去一個非負的實數\(b\)。操作2:使\(A\)的所有為負數的元素變為零。要求進行完操作1和操作2之後集合A滿足條件1和條件2。求\(b\)的最小值(記為\(b_{\min}\))。

為了形象的說明問題,我舉個例子。比如現在這個隨機的集合\(A\)包含的元素是\(\{1,2,3\}\)。而我要求的\(p\)等於3。這時候發現\(A\)已經滿足條件1,但不滿足條件2。\(A\)所有元素的和\(s\)等於6,比3大。這時候我根據操作1對\(A\)的所有元素都減去一個數\(b\)。這裡顯然\(b\)的最小值是1。這樣減完之後\(A\)為\(\{0,1,2\}\)。\(s\)剛好等於3。操作2也不需要進行了因為\(A\)現在的元素沒有負數。

怎麼能證明例子中的\(b\)等於1就是\(b\)的最小值了呢?\(b\)比1稍微小一點,比如0.9,那么總和就會比3稍微大一點,於是也就不滿足條件了。而如果\(b\)比1稍微大一點,比如1.1,那么總和就比3小了,於是雖然滿足了條件但是我們有更小的\(b\)也可以滿足條件,所以1.1就不是最小值了。所以兩邊逼近的結果就是\(b\)等於1剛剛好滿足條件,也就是\(b\)的最小值。

然而這種描述既不算嚴謹的證明,也無法適用於更一般的情況。我們先不管如何嚴格找出\(b_{\min}\)的表達式,我們先來看看什麼是更一般的情況。

首先上面的例子根本沒有用到操作2。什麼時候需要用到呢?比如一個簡單的情況,\(A\)中原本就存在負數元素。這時候由於\(b\)是個非負數,所以所有元素減完\(b\)之後必定還存在負數元素。這時候就不符合條件1了。所以進行操作2,也就是使這些負數變為零。當然還有一種情況就是即使原本\(A\)中沒有負數元素,當進行完操作1之後,由於所有元素都減去了\(b\),就有可能會使一些元素變為負數。這時候也要通過操作2來保證\(A\)滿足條件1。請注意,這個操作2是會影響到\(b\)的選取的。為什麼呢?因為操作2的過程可能會使元素總和\(s\)增大。因為本來是負數的變為零了么。而我認為這個問題的難點也正在於此。試想一下,假如我們在不考慮操作2的情況下已經找到了最小的\(b\),然後減完發現有負數元素,不滿足條件1,於是進行操作2,然後發現總和\(s\)大於\(p\),不滿足條件2,於是需要讓一開始的\(b\)變得更大。但是大多少呢?更大之後會不會產生新的負數呢?如果產生了新的負數豈不是又要調整\(b\)?這種情況下有沒有\(b_{\min}\)的非遞歸表達式呢?如果沒有,如何證明沒有呢?又該怎麼求呢?

我一開始分析這個問題的時候並沒有清晰的看到這兩個操作互相之間的影響。我只是寫了幾個簡單的例子去分析不同情況下(初始的\(A\)不滿足1或不滿足2或兩個都不滿足)\(b\)的選取會隨操作2怎樣的變化。然後逐步調整\(b\)來達到最佳表達式。當我自以為分析了所有情況的時候我高興異常的寫了個程序去進行一般化驗算。然後不出意料的出現了各種錯誤。然後我想到了一些我想法中的漏洞。然後細思極恐。因為當我意識到這兩個操作實際上一個是會使\(s\)減小(操作1)而另一個是會使\(s\)增大的(操作2)。所以我直覺的感覺到應該是沒有一般性的代數解。只能不斷的搜索\(b_{\min}\)了。搜索的話倒是很簡單,我們設置一個\(b_{\min}\)的下限0,再設置一個\(b_{\min}\)的上限,然後用二分法不停的搜索\(b_{\min}\)就行了。這樣雖然簡單暴力,但是不精確。要知道我們題目中的元素可都是實數啊。但是我確實想不到什麼好辦法了。

說點題外話。

作為很弱的我經常分析問題都是憑直覺的。我並沒有什麼很好的數學能力,無論從經驗上還是邏輯上。眼下導師特別想讓我自己推導很多式子,分析很多問題。並且給我很多好的數學材料去閱讀并一再強調遇到問題不要遲疑想問就問,他會盡量解答。當然除了數學上的,導師還很熱衷於給我講通信網絡的知識(畢竟我們的課題就是干這些的)。每每當我覺得我的英語表達還是不盡人意讓我有種有力使不上的感覺的時候,我更多的是欣喜於通過和導師討論快速的得到知識的快感。這樣的環境使我這個弱爆了的懶蛋有了一絲進取的精神。這是我最最最缺乏的元素了。希望這是個好的開始吧。