<mark id="oztn4"></mark>
3
雷鋒網(wǎng) AI 科技評論按，今年下半年，阿里巴巴舉辦了一場全球數(shù)學(xué)競賽，在短短 6 天的報名時間中，有 4 萬多名來自國內(nèi)外的選手報名了這次競賽，其中海外選手占了三分之一，并且有 77% 的參賽者是學(xué)生，超過一半的學(xué)生選手是碩士在讀或者碩士以上學(xué)歷，高中生比例也占據(jù) 8%。
來自于 11 個國家和地區(qū)的選手參加了比賽，而年齡最小的僅 13 歲，年紀(jì)最大的年近五旬。最終，有 328 位選手通過了預(yù)選賽，進入決賽。其中有很多在國際數(shù)學(xué)競賽中取得優(yōu)異成績的「大神」。
經(jīng)過激烈角逐，共有 51 名選手在決賽中脫穎而出，下面是阿里巴巴官方公布的決賽獲獎名單：
官網(wǎng)獲獎名單圖
金獎獲得者 4 人：Allen Liu，張鉞，楊亦銳，韋東奕
銀獎獲得者 6 人：Ashwin Sah、張盛桐、聶子佩、張海翔、蘇煒杰、龍吉昊
銅獎獲得者 10 人：林中一攀、周勝鉉、鄭志偉、葉帆、王煒飚、鄭靈超、黃政宇、鐘逸嶠、周康杰、鄭凡
優(yōu)秀獎獲得者 31 人：王彬、陳澤坤、丁力煌、Aoxiang Cui、David Stoner、歐陽銘暉、趙斌、Huan Xiong、蔡毓麟、彭柯堯、Christian Bernert、余佳弘、程良偉、Guolong li、林偉南、劉宇航、茆凱、張馳麟、時代、肖納川、李文博、李冠淳、劉熙、李正一、張少杰、李夢龍、Zhiqi Huang、楊洪鑫、Mehtaab Sawhney、胡衛(wèi)、顧陳琳；
全球「最強 51 人」分布圖
可以看到，從全球4萬多名參賽者中脫穎而出的「最強 51 人」來自 20 多所全球一流大學(xué)，國內(nèi)選手 28 人，海外選手 23 人。其中北京大學(xué)貢獻了 13 位獲獎選手，是獲獎人數(shù)最多的高校，麻省理工學(xué)院次之，貢獻 4 名獲獎選手。獲獎?wù)咧心挲g最小的獲獎?wù)邇H有 18 歲。
這 51 人均將獲得由多位國際著名數(shù)學(xué)家領(lǐng)銜授課的數(shù)學(xué)大師班門票。同時，獲得金銀銅獎的 20 名選手將會共同分享總額 100 萬元的獎學(xué)金。
據(jù)悉，本次數(shù)學(xué)大賽組委會在決賽舉辦前一個月就單獨成立命題小組，其中包括應(yīng)用數(shù)學(xué)領(lǐng)域最高成就——高斯獎獲得者 Stanley Osher。決賽出題者之一北京大學(xué)數(shù)學(xué)系教授董彬表示，決賽題目水平相當(dāng)于美國 top 20 高校博士入學(xué)考試的水平，需要綜合運用高年級本科及低年級研究生課程的數(shù)學(xué)知識。在賽題選擇上，大賽更關(guān)注選手們對實際數(shù)學(xué)知識應(yīng)用的考察，而非過去競賽所偏重的數(shù)學(xué)技巧。預(yù)選賽和決賽都是線上答題，題目都是英文，解答既可以用中文也可以用英文。其中，預(yù)選賽的題目比較貼近個人生活，決賽更注重對數(shù)學(xué)基礎(chǔ)知識的考察。
目前決賽的試題解析還沒有公布，雷鋒網(wǎng)整理了預(yù)選賽試題和答案，讓我們來看看吧~
預(yù)選賽具體形式是應(yīng)用題&建模題&數(shù)學(xué)基礎(chǔ)題，共三題，每題三問，需要提供解題步驟。第一題 30 分，第二題 40 分，第三題 30 分，全部正確解決問題得滿分。組委會會選擇前 300 名進入決賽。
第一題
在下面的所有小題中，不考慮退貨
A.「雙十一」期間，一家電商店鋪 A 有滿 60 返 5 塊的優(yōu)惠券，可疊加使用（比如，買 120 塊的東西，用兩張優(yōu)惠券，只需付 120-5*2=110 塊）。此外，電商平臺全場提供滿 299 減 60 的優(yōu)惠券（可湊單），每單限用一張，可與店鋪的優(yōu)惠券疊加使用（比如，原價 299 塊的一單，最終價格是 299-5*4-60=219）。原價不滿 299 則不能減去全場折扣 60，不足 299 時，用戶可以在別家商店湊單。
請問：小明打算在這家店鋪買一款 250 塊的耳機和 600 塊的音箱，怎么買最劃算？
B. 現(xiàn)在您開了一家電商店鋪，賣與 A 店同款的耳機和音箱，標(biāo)價相同，您計劃提供滿 99 返 x 的優(yōu)惠券，x 為大于 0，小于 99 的整數(shù)，與 A 店不同的是，您的優(yōu)惠券每單限用一張（比如，買 250 塊需付 250-x 塊，而不是 250-2x 塊）。雙 11 期間，電商平臺全場滿 299 減 60 依然適用。
請問：x 至少等于多少時，小明在您的店鋪買耳機和音箱其中一種會更便宜（至少 1 元）？又請問：x 至少等于多少時，小明在您的店鋪既買耳機又買音箱總和會更便宜（至少 1 元）？
C. 建模題。對比單賣和捆綁銷售下的利潤期望。假設(shè)耳機（產(chǎn)品 1）和音箱（產(chǎn)品 2）的單件銷售的單位成本分別是 c1 和 c2（包含生產(chǎn)、存儲、運輸、促銷等所有成本）。一個訪問店鋪的客戶對兩件產(chǎn)品的心理價值分別是均勻分布在 [0，u1]，[0，u2] 的區(qū)間上隨機變量 S1 和 S2。假設(shè) S1 和 S2 相互獨立。本題有三小問。
如何分別設(shè)定產(chǎn)品價格 p1 和 p2，以最大化每個到訪客戶帶來的利潤期望。這里假設(shè) c1<u1；當(dāng)且僅當(dāng) p1<=S1 時，客戶會購買一件商品 1；用戶不買的話不計損失。對產(chǎn)品 2 做類似假設(shè)。請以公式形式給出最優(yōu)價格 p1*和 p2*以及對應(yīng)的最大利潤期望 r1*和 r2*。
現(xiàn)在假設(shè)產(chǎn)品 1 和 2 捆綁銷售，成本是 c12=t（c1+c2）。因為節(jié)省了包裝和運輸成本，假設(shè) 0<t<1。其余的條件不變。請以公式形式給出捆綁下的最優(yōu)價 p12*。
單賣和捆綁銷售，哪個利潤更優(yōu)，還是不一定？為什么？
第二題
a. 附圖中有一個無向圖，其中圈內(nèi)數(shù)字代表一個地點，邊 e 上的數(shù)字代表長度 Le（雙向相同）。一位外賣小哥在起點 A，要去 3 個商家（B1，B2，B3）取餐，送到 3 個對應(yīng)的地方（C1，C2，C3），即 B1 至 C1，B2 至 C2，B3 至 C3。小哥的電動動力車的箱子同時最多裝下 2 份外賣。
請問：小哥該怎么走最短路徑？這個最短路徑的長度是多少，這里 A 是出發(fā)點，最后一餐（不限次序）送達地為終點。為了簡化問題，假設(shè)商家已經(jīng)準(zhǔn)備好了外賣，小哥取餐送餐不用等。又假設(shè)每份外賣重量大小一樣。
b. 此題與上圖無關(guān)，而是考慮一個一般的圖，圖中有很多點和邊。外賣小哥剛剛?cè)×艘环萃赓u，計劃通過圖上的邊 e1、e2...em 送給目的地，途中經(jīng)過每條邊 e 的時候，以概率 Pe[0,1] 會收到送至相同地點的另一單外賣。（一條邊上收到另兩單及以上的概率小，暫忽略不計）。假設(shè)對應(yīng)邊 e1、e2...em 的概率為 P1、P2...Pm。
請問：送一次外賣，小哥平均能收到幾個送去相同地址的新單（不考慮電動車的箱子容量）？小哥收到至少一個區(qū)相同地址的新單的概率是多少？
c. 此題延續(xù)上題，但不再固定路徑，而是對路線進行優(yōu)化。假設(shè)小哥每送一單外賣有固定收益 r，但是總路徑長度 l（途中經(jīng)過的每邊 e 的長度 le 之和）是成本。總收益是 r-l。（為了簡化，這里設(shè)成本系數(shù)為 L）。現(xiàn)在小哥剛剛出發(fā)，車上只有一份外賣，箱子最大容量仍設(shè)為兩份外賣，請問怎么走才能最大化收益？（提示：這里不但要考慮路徑長短，還要考慮可能收到送至相同地點的另一單外賣而帶來的無額外成本的收益 r。假設(shè) 0<=Pc<=min{le/r，1}）。
第三題
a. 馬教授的領(lǐng)域內(nèi)有 n 個不同但是等價的邏輯陳述，A1，A2，...，An，現(xiàn)在需要證明它們是等價的。每個學(xué)期，馬教授選兩個不同的陳述 Ai 和 Aj，以「Ai->Aj」的證明作為研究課題，指導(dǎo)一位本科生完成。假設(shè)每個學(xué)期只完成一個證明。要注意的是，在「Ai->Aj」和「Aj->Ak」被證明之后，「Ai->Ak」也已經(jīng)被自動的證明了，因此不能再作為一個新的課題讓學(xué)生去完成。總之，如果一個課題是之前若干學(xué)生已經(jīng)完成課題的直接推論，則不能作為新課題發(fā)給另一個學(xué)生。隨著越來越多的推出關(guān)系被證明，剩下可選擇的課題也越來越少。請問，馬教授可以最多依次指導(dǎo)多少個學(xué)生呢？為什么？
b.H 是一個 n x n 的方陣，其第 i 行第 j 列的元素是 hij，所有 hij的取值集合為{1，-1}，并且 H 的任意不同的兩行看作向量是相互垂直的（即，他們的標(biāo)準(zhǔn)內(nèi)積為 0）。假設(shè) H 有一個 a x b 的子矩陣（1<=a,b<=n），子矩陣內(nèi)的元素均為 1。請證明 a，b<=n。
c.G 是一個群。e 是該群的單位元。定義 G 的一個子集：
F = { h 屬于 G | 存在自然數(shù) m >= 1，使得 hm = e }。
假設(shè)集合 F 內(nèi)的元素是有限多個的。證明：存在一個自然數(shù) n >= 1 使得對所有 g 屬于 G 和 h 屬于 F，我們都有：
以上就是全部預(yù)選賽試題，阿里巴巴數(shù)學(xué)競賽官方網(wǎng)站也給出了這些題目的參考答案。
第一題答案
A.709 元人民幣。
為了得到這個答案，我們必須要使用其它店鋪的優(yōu)惠券。如果所有的優(yōu)惠券都來自店鋪 A，那么付款金額可以減少到 705，但在實際中，這個是行不通的。下面是如何得到 709 人民幣的具體步驟：
下面我們來比較耳機和音箱一起買與耳機和音箱分開買這兩種購買方案，其中，分開購買可以獲得更小的支付金額，也就是 709 元。
在同一個訂單中購買耳機和音箱：
耳機 250 元，加上音箱的 600 元也就是 850 元，由于在店鋪 A 每滿 60 可以使用一張 5 元優(yōu)惠券，60*14=840，因此可以在店鋪 A 使用 14 張優(yōu)惠券。此外，電商平臺全場提供的滿 299 減 60 的優(yōu)惠券也可以使用。
于是，在同一個訂單中購買耳機和音箱總共需要花費的金額為：
850-14*5-60=720 元
耳機和音箱分兩個訂單中購買：
這種方案最終的花費為 709，具體的購買方法如下：
耳機的價格是 250 元，因此可以湊單一件 49 元的商品，這樣就可以使用 4 張 5 元優(yōu)惠券，以及一張滿 299 減 60 的優(yōu)惠券。算下來需要的花費為 250+49-4*5-60=219 元。
音箱的價格是 600 元，可以使用 10 張滿 60 減 5 元的優(yōu)惠券和 1 張滿 299 減 60 元的優(yōu)惠券。于是需要花費的金額為 600-60-10*5=490 元。
因此，耳機和音箱分別購買需要的總花費為 219+490=709 元。
綜上所述，最小花費是 709 元，采用的方案是耳機和音箱分兩單購買，并且耳機那個訂單要湊單一件 49 元的商品。
B. 問題 1 答案為：如果使用其它店鋪的優(yōu)惠券，那么 x 為 21；如果只使用店鋪 A 的優(yōu)惠券，那么 x 為 25。
問題 2 答案為：如果使用其它店鋪的優(yōu)惠券，那么 x 為 36；如果使用店鋪 A 的優(yōu)惠券，那么 x 為 38。
具體步驟為：
問題 1：為了在你的店鋪里面買一副耳機，某個人需要支付的錢數(shù)為 250-x+49（湊單品價格）-60（平臺提供的滿 299 減 60 優(yōu)惠券）=（239-x）元。對于音箱，我們也用同樣的方法計算，得到的這個人需要支付的金額為（540-x）元。為了減少你的店鋪在耳機上的花費，x 必須滿足的條件為 239-x<=219，或者 x>=21；為了讓你的店鋪減少在音箱上的花費，x 必須滿足 540-x<=490-1，或者 x>=51。當(dāng) x 為 21 時，我們可以保證購買耳機是便宜的，但是此時，音箱并不是最便宜的。
問題 2：如果在你的店鋪里面買耳機和音箱，那么分兩單分別購買耳機和音箱更劃算，因為這樣可以獲得的總折扣金額為 2x。這兩個訂單的金額分別為（239-x）和（540-x）。它們的總金額肯定比 709 元要小，那么第二個問題的答案是什么？在這里，x 滿足的條件為（239-x）+（540-x）<=709-1，或者 x>=35.5。因為 x 必須是整數(shù)，所以我們求得這個問題的答案為 x=36。
C. 題目 1 答案：最優(yōu)價格為
，期望利潤為
，i=1，2。在 i 為 1 或者 2 的時候，步驟都是一樣的。我們用 R 表示利潤這個變量，它隨著 S 的變化而變化。公式為：
同樣的，我們也可以算出期望利潤作為產(chǎn)品的利潤，（p-c），購買的可能性為 (u-p)/u。
函數(shù) 
是一個凹二次曲線函數(shù)，因此它的極大值點 p*如果在 [0，u] 這個區(qū)間取得，則滿足條件
，此時，p*=(u+c)/2，如果 c<=u，那么在該點處函數(shù)取得最大值。否則，在 p*=u 處取得最大值。
當(dāng) p*=(u+c)/2 時，我們可以得到
。
題目 2 答案：價格 
的最大值為：
注意到 
是關(guān)于 
的分段函數(shù)，分成了三段，我們可以算出每個鄰域內(nèi)的邊界點。
同樣我們注意到，計算結(jié)果并不是唯一的，學(xué)生可以畫出函數(shù)的曲線圖，根據(jù)這個曲線圖來找出正確答案。
不管用什么方法，我們需要三步來計算出 
。
步驟 1：定義變量 
，計算 
的分布并記為 
，這個分布并不是均勻分布。
步驟 2：計算期望利潤，為
對于
，當(dāng)
時，有
。
步驟 3：對于每個區(qū)間來說，最大值就是期望利潤，也就是說，必須要找到 
在每個區(qū)間的最大值。
當(dāng) 
的取值區(qū)間為 [0，u1] 時，
的倒數(shù)為
畫出函數(shù)的曲線或者檢查它的二階導(dǎo)數(shù)，可以很容易地看出上面的 
的極大值。從 
，可以得到 
，在這種情況下，
是期望利潤的最大值。
采用相同的步驟，我們可以求出在另外兩種情況下的 
值和它對應(yīng)的 
的值。
題目 3 答案：不一定，沒有哪一種策略比其余的策略好。
可以使用兩個例子來證明這一點，第一個策略采用的方法比第二個好，第二個策略采用的方式比第一個好。有很多這樣的例子，我們就不具體舉例了。
第二題答案
題目 a 答案： 最短的路徑長度是 16。獲得這個數(shù)值的方法是采用下面的順序進行送餐：
A -> B2 -> C2 -> B1 -> B3 -> C3 -> C1
具體來說，有兩種送餐路線可以使路徑長度為 16，它們有輕微的不同，即：
路線1：
路線2：
這兩條路線都可以經(jīng)過所有的取餐點。
羅列出所有的路線并計算他們的路徑長度是一件非常繁瑣的工作，然而，在這個題目里面我們不需要這樣做。因為這個圖是一個平面圖，并且路線的方向和目的地的距離總是 90 度。這就意味著，任意兩個點之間的最短路徑都是很容易求得的。
要手動計算出這個問題的答案，首先可以大致估算一下 {B1,C1,B2,C2,B3,C3} 的順序并計算出路徑長度。實際上，有很多排序方式可以讓路徑的長度為 17，如果你算出的值比這個稍微高一點兒，那么就是一個好的排列順序。這個距離是最短距離的上限。然后羅列 {B1,C1,B2,C2,B3,C3}的順序并計算出路徑長度，一旦長度達到 17，就排除這個路線。當(dāng)你找到一條總長度為 16 的路線時，上限改為 16，這個策略叫做分支界限法。
題目 b 答案：對于問題 1 來說，P1 + P2 + ... + Pm。我們讓 
的取值為 0 或者 1，邊界為 
，對于 i = 1,2,...,m 來說，我們可以通過下面的方法來計算答案：
對于問題 2 來說，是
。在這里，（1-Pi）是在 ei 處沒有外賣的概率，并且我們可以根據(jù)概率論知識知道，
是整個路線上都沒有外賣的概率，因此，1 減去這個概率值是最少可以在這條路線上取到一個外賣的概率。同時，可以使用條件概率來得到的遞歸公式為，在e1之后最少可以獲得一單新外賣的概率為
，也就是
，通過不斷的遞歸，可以得到最終的式子為
，這個遞歸也是一個正確答案。
上面的兩個答案都可以和下面這個式子等同：
題目 c 答案： 假設(shè)我們不考慮一般性的情況，現(xiàn)在有 T 個節(jié)點，并且 T 是目的節(jié)點。首先，對于每個節(jié)點 i，找到去 T 的最短路線和對應(yīng)的路線長度 
（如果具有相同長度的不同路線之前有相互關(guān)系，一定要解除他們之間的關(guān)系）。對于 i=T，我們有
。
接下來，使用 
，在每個節(jié)點計算最優(yōu)預(yù)期回報 
，使用下面給出的極大值公式（3）來計算。對于 
，假設(shè) 
是 i 的相鄰節(jié)點，并且在該點處能取得極大值（同樣地，如果節(jié)點之間有關(guān)聯(lián)，打破這個關(guān)聯(lián)）。
外賣小哥的最優(yōu)路線被下面的每個點決定了：在節(jié)點 i 的時候，如果外賣小哥還沒有拿到額外的一單，那么移動到
；如果外賣小哥拿到了額外的一單，那么他車上的外賣箱子已經(jīng)裝滿了，因此只需要走從 i 到 T 的最短路線。
注意到上面的路線并不是事先計劃好的，而是由外賣小哥自己決定的。也就是說，這是一個策略問題。這種方式比事先計劃好路線要好，因為是否會有額外的外賣單是未知的，而這會影響路線、影響到 T 的距離。
當(dāng)外賣小哥在節(jié)點 i 并且取到了第二個外賣的時候，外賣小哥決定去哪里采用的方法是去這個地方獲得的收益的期望值，這個收益值又被獲取外賣的可能性和到 T 節(jié)點的距離所影響。
定義在取到額外的外賣前，在節(jié)點 i 的最優(yōu)預(yù)期收益為
。當(dāng) i=T 時，我們讓
，這個是固定的收益。假設(shè)我們計算了 i 的相鄰節(jié)點
。在節(jié)點 i 的時候，如果我們要移動到節(jié)點 j，那么預(yù)期收益將會變成：
，如果在 i、j 兩點之間出現(xiàn)外賣；
，如果在 i、j 兩點之間不出現(xiàn)外賣。
設(shè) i、j 之間的邊長度為 
，則有：
（3）
這就是眾所周知的貝爾曼方程。
根據(jù)
和式子（3），我們可以計算出 
，你可以使用動態(tài)規(guī)劃或者更具體的圖，貝爾曼·福特算法或者迪杰特斯拉算法（請看下面的說明）。它們都從
開始，并且決定了 
這個集合里面的元素。
對于 
或者 
，必須要避免「正面獎勵」的存在，這可以避免外賣小哥為了獲得額外的報酬而不停地在這些路線走來走去，直到取到額外的一單外賣這種不現(xiàn)實的情況。
我們注意到，在實際中，學(xué)生們更傾向于使用迪杰特斯拉算法。這種算法要求邊長必須是非負的值。因此，如果一個人使用這個算法去計算 ，必須要滿足這個條件。對于我們的這個問題，這里必須要滿足：
（4）
在滿足假設(shè)條件 的條件下，這種情況確實存在。為什么呢？既然最壞的情況也就是外賣小哥沿著最短路徑到達 T 節(jié)點處（而不是選擇使收益最大化的節(jié)點），我們可以得到：
于是可以得到第二個不等式：
第一個不等式的假設(shè)條件是 
不大于
，我們可以結(jié)合上面的不等式得到式子（4）。
第三題答案
題目 a 答案：我們首先指導(dǎo) 0.5(n+2)(n-1) 個學(xué)生，下面，我們將證明這個答案。
解釋：首先，(n-1) 個學(xué)生證明 A1->Ai，其中 i 為 2 到 n 的整數(shù)；然后，(n-2) 個學(xué)生證明 A2->Ai，其中 i 為 3 到 n 的整數(shù)。一直這樣做，直到最后一個學(xué)生證明 An-1->An。
然后，(n-1) 個學(xué)生證明 An->An-1，An-1->An-1，...，A2->A1。它們的總數(shù)為：
讓 
。
最優(yōu)性證明：假設(shè)圖 G=（N，E）的節(jié)點為 N={1,2，...，n}，其有向邊為 E={（i，j）|Ai -> Aj已經(jīng)被證明了}。完成一個課題，意味著給 E 加上一條邊。
假設(shè) E': = { （i, j ) | 其中，Ai -> Aj 和 Aj -> Ai在前面已經(jīng)被證明了 } 是對偶邊，是集合 E 的子集，子圖 G’=（N，E'）最多有 2(n-1) 個有向邊；否則，必然存在一些對偶邊包含無效課題。
G 最多有 n(n-2)/2 對節(jié)點，去掉對偶邊上的節(jié)點，正如前面所證明的，此時最多有 2(n-1) 個有向邊，因此最多有 (n-1) 對有向邊，也就是說，有 n(n-1)/2 - (n-1) = (n-2)(n-1)/2 對節(jié)點之間是單向邊或者是沒有邊的。因此，最多有 (n-2)(n-1)/2 個單向邊。因此，加上單向邊和對偶邊的最大數(shù)得：
題目 b 答案：對于任何 a 行 b 列的矩陣 A ，都有：
（5）
設(shè) ||A|| 為矩陣的譜范數(shù)，
為矩陣的 Frobenius 范數(shù)。
在我們的題目中，既然 H 是 n 行 n 列的正交矩陣，則有
。對于 H 的任何子矩陣 A來說，都有
。當(dāng)子矩陣 A 為 a 行 b 列矩陣，且其元素全部為 1 時，則有
和 rank(A) = 1，于是可以得到：
題目 c 答案：證明：取
。設(shè)
滿足
，讓
。由于：
由 F 的定義，我們可以得到：
因此，可以得到
，
。對于
來說也是一樣的。F 是有限的，對于每個 h，存在
，使得
。取
，對任何屬于 F 的 h，n 是
的倍數(shù)，也就是說，
。因此，從
，我們可以得到：
進而可以得到：
雷鋒網(wǎng)
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
