預(yù)選賽題 7.

這是最優(yōu)停止問題，但是比賽的時(shí)候忙著趕論文，題都沒看就潤了。下面直接用動(dòng)態(tài)規(guī)劃來解決一般的?。

設(shè)??為正在考慮的候選者，?為其排名的隨機(jī)變量，?為該候選者是否接受 offer 的隨機(jī)變量。所有策略狀態(tài)都可以用??表示，其中??為??的排名，?表示候選者是否接受 offer。

顯然，若?，?就不會(huì)被選為最優(yōu)者，此時(shí)應(yīng)該考慮?。設(shè)??是狀態(tài)??下選到最優(yōu)者的最大概率，則

其中??是狀態(tài)??即為最優(yōu)者的概率，顯然當(dāng)??時(shí)?，否則?。當(dāng)??時(shí)，問題的邊界條件為當(dāng)??時(shí)?，否則?。

現(xiàn)在尋找??應(yīng)當(dāng)滿足的遞推關(guān)系（注意它和??無關(guān)）。

當(dāng)??時(shí)，繼續(xù)考慮第??個(gè)候選人所獲得的概率比直接選擇第??個(gè)候選人所獲得的概率更大，此時(shí)最優(yōu)策略應(yīng)當(dāng)為考慮第??個(gè)候選人，因此?。此時(shí)代入上式可得?，代入遞推式可得?。因此對第??個(gè)候選者而言，也應(yīng)當(dāng)繼續(xù)考慮第??個(gè)候選人。

因此，最優(yōu)策略滿足如下條件：如果第??個(gè)候選人不會(huì)被選，則第??個(gè)候選者也不會(huì)被選；如果第??個(gè)候選人可以被考慮，那么第??個(gè)候選人也應(yīng)當(dāng)被考慮。

如果想在??狀態(tài)選擇第??個(gè)候選人，則?，因此

其中??為使得??的最小??值。現(xiàn)在代入邊界條件，就得到

綜上所述，我們只需要考慮狀態(tài)?，此時(shí)選擇第??個(gè)候選人當(dāng)且僅當(dāng)?。設(shè)??是第一個(gè)滿足上述條件的?，則最優(yōu)策略即為從第??個(gè)候選人開始考慮發(fā) offer，選擇第一個(gè)??的候選人。

下面求出?。這也即尋找

由??不等式，

另一方面，

故

因此

故

兩側(cè)同取極限得

當(dāng)??時(shí)，上述極限即趨于?。

決賽我選的主分析副應(yīng)用與計(jì)算?，F(xiàn)在看來選得還行。

分析題 1.?數(shù)列??滿足

證明：對任意正整數(shù)??都有?。

沒什么想法，就硬估計(jì)的。自然會(huì)想到利用歸納法，

再用??問題放縮。不過從??開始不太行，計(jì)算到??之后就可以了：

分析題 2.?設(shè)??是平面閉區(qū)域??上由連續(xù)函數(shù)構(gòu)成的??維線性空間，證明：存在函數(shù)??使得

取??范數(shù)下的標(biāo)準(zhǔn)正交基?。則對任意?，有?。

先考慮讓?，不難知道?，故?。

另一方面，由于?，則由積分中值定理可知存在??使得?。此時(shí)由??不等式可知?，且等號(hào)顯然可以取到。此時(shí)的??即滿足題目條件。

總感覺以前做過這題，但是翻了翻還存著的 TD 沒找著。