四萬高手過招，這份阿里全球數學競賽試題你真的不要看嗎

雷鋒網 AI 科技評論按，今年下半年，阿里巴巴舉辦了一場全球數學競賽，在短短 6 天的報名時間中，有 4 萬多名來自國內外的選手報名了這次競賽，其中海外選手占了三分之一，并且有 77% 的參賽者是學生，超過一半的學生選手是碩士在讀或者碩士以上學歷，高中生比例也占據 8%。

來自于 11 個國家和地區的選手參加了比賽，而年齡最小的僅 13 歲，年紀最大的年近五旬。最終，有 328 位選手通過了預選賽，進入決賽。其中有很多在國際數學競賽中取得優異成績的「大神」。

經過激烈角逐，共有 51 名選手在決賽中脫穎而出，下面是阿里巴巴官方公布的決賽獲獎名單：

官網獲獎名單圖

• 金獎獲得者 4 人：Allen Liu，張鉞，楊亦銳，韋東奕
  

• 銀獎獲得者 6 人：Ashwin Sah、張盛桐、聶子佩、張海翔、蘇煒杰、龍吉昊
  

• 銅獎獲得者 10 人：林中一攀、周勝鉉、鄭志偉、葉帆、王煒飚、鄭靈超、黃政宇、鐘逸嶠、周康杰、鄭凡
  

• 優秀獎獲得者 31 人：王彬、陳澤坤、丁力煌、Aoxiang Cui、David Stoner、歐陽銘暉、趙斌、Huan Xiong、蔡毓麟、彭柯堯、Christian Bernert、余佳弘、程良偉、Guolong li、林偉南、劉宇航、茆凱、張馳麟、時代、肖納川、李文博、李冠淳、劉熙、李正一、張少杰、李夢龍、Zhiqi Huang、楊洪鑫、Mehtaab Sawhney、胡衛、顧陳琳；

全球「最強 51 人」分布圖

可以看到，從全球4萬多名參賽者中脫穎而出的「最強 51 人」來自 20 多所全球一流大學，國內選手 28 人，海外選手 23 人。其中北京大學貢獻了 13 位獲獎選手，是獲獎人數最多的高校，麻省理工學院次之，貢獻 4 名獲獎選手。獲獎者中年齡最小的獲獎者僅有 18 歲。

這 51 人均將獲得由多位國際著名數學家領銜授課的數學大師班門票。同時，獲得金銀銅獎的 20 名選手將會共同分享總額 100 萬元的獎學金。

據悉，本次數學大賽組委會在決賽舉辦前一個月就單獨成立命題小組，其中包括應用數學領域最高成就——高斯獎獲得者 Stanley Osher。決賽出題者之一北京大學數學系教授董彬表示，決賽題目水平相當于美國 top  20 高校博士入學考試的水平，需要綜合運用高年級本科及低年級研究生課程的數學知識。在賽題選擇上，大賽更關注選手們對實際數學知識應用的考察，而非過去競賽所偏重的數學技巧。預選賽和決賽都是線上答題，題目都是英文，解答既可以用中文也可以用英文。其中，預選賽的題目比較貼近個人生活，決賽更注重對數學基礎知識的考察。

目前決賽的試題解析還沒有公布，雷鋒網整理了預選賽試題和答案，讓我們來看看吧~

預選賽具體形式是應用題&建模題&數學基礎題，共三題，每題三問，需要提供解題步驟。第一題 30 分，第二題 40 分，第三題 30 分，全部正確解決問題得滿分。組委會會選擇前 300 名進入決賽。

• 第一題

在下面的所有小題中，不考慮退貨

A.「雙十一」期間，一家電商店鋪 A 有滿 60 返 5 塊的優惠券，可疊加使用（比如，買 120 塊的東西，用兩張優惠券，只需付 120-5*2=110 塊）。此外，電商平臺全場提供滿 299 減 60 的優惠券（可湊單），每單限用一張，可與店鋪的優惠券疊加使用（比如，原價 299 塊的一單，最終價格是 299-5*4-60=219）。原價不滿 299 則不能減去全場折扣 60，不足 299 時，用戶可以在別家商店湊單。
請問：小明打算在這家店鋪買一款 250 塊的耳機和 600 塊的音箱，怎么買最劃算？

B. 現在您開了一家電商店鋪，賣與 A 店同款的耳機和音箱，標價相同，您計劃提供滿 99 返 x 的優惠券，x 為大于 0，小于 99 的整數，與 A 店不同的是，您的優惠券每單限用一張（比如，買 250 塊需付 250-x 塊，而不是 250-2x 塊）。雙 11 期間，電商平臺全場滿 299 減 60 依然適用。
請問：x 至少等于多少時，小明在您的店鋪買耳機和音箱其中一種會更便宜（至少 1 元）？又請問：x 至少等于多少時，小明在您的店鋪既買耳機又買音箱總和會更便宜（至少 1 元）？

C. 建模題。對比單賣和捆綁銷售下的利潤期望。假設耳機（產品 1）和音箱（產品 2）的單件銷售的單位成本分別是 c₁ 和 c₂（包含生產、存儲、運輸、促銷等所有成本）。一個訪問店鋪的客戶對兩件產品的心理價值分別是均勻分布在 [0，u₁]，[0，u₂] 的區間上隨機變量 S₁ 和 S₂。假設 S₁ 和 S₂ 相互獨立。本題有三小問。

1. 如何分別設定產品價格 p₁ 和 p₂，以最大化每個到訪客戶帶來的利潤期望。這里假設 c₁<u₁；當且僅當 p₁<=S₁ 時，客戶會購買一件商品 1；用戶不買的話不計損失。對產品 2 做類似假設。請以公式形式給出最優價格 p₁*和 p₂*以及對應的最大利潤期望 r₁*和 r₂*。
   

2. 現在假設產品 1 和 2 捆綁銷售，成本是 c₁₂=t（c₁+c₂）。因為節省了包裝和運輸成本，假設 0<t<1。其余的條件不變。請以公式形式給出捆綁下的最優價 p₁₂*。
   

3. 單賣和捆綁銷售，哪個利潤更優，還是不一定？為什么？
   

• 第二題
  

a. 附圖中有一個無向圖，其中圈內數字代表一個地點，邊 e 上的數字代表長度 L_e（雙向相同）。一位外賣小哥在起點 A，要去 3 個商家（B₁，B₂，B₃）取餐，送到 3 個對應的地方（C₁，C₂，C₃），即 B₁ 至 C₁，B₂ 至 C₂，B₃ 至 C₃。小哥的電動動力車的箱子同時最多裝下 2 份外賣。

請問：小哥該怎么走最短路徑？這個最短路徑的長度是多少，這里 A 是出發點，最后一餐（不限次序）送達地為終點。為了簡化問題，假設商家已經準備好了外賣，小哥取餐送餐不用等。又假設每份外賣重量大小一樣。

b. 此題與上圖無關，而是考慮一個一般的圖，圖中有很多點和邊。外賣小哥剛剛取了一份外賣，計劃通過圖上的邊 e₁、e₂...e_m 送給目的地，途中經過每條邊 e 的時候，以概率 P_e[0,1] 會收到送至相同地點的另一單外賣。（一條邊上收到另兩單及以上的概率小，暫忽略不計）。假設對應邊 e₁、e₂...e_m 的概率為 P₁、P₂...P_m。

請問：送一次外賣，小哥平均能收到幾個送去相同地址的新單（不考慮電動車的箱子容量）？小哥收到至少一個區相同地址的新單的概率是多少？

c. 此題延續上題，但不再固定路徑，而是對路線進行優化。假設小哥每送一單外賣有固定收益 r，但是總路徑長度 l（途中經過的每邊 e 的長度 l_e 之和）是成本。總收益是 r-l。（為了簡化，這里設成本系數為 L）。現在小哥剛剛出發，車上只有一份外賣，箱子最大容量仍設為兩份外賣，請問怎么走才能最大化收益？（提示：這里不但要考慮路徑長短，還要考慮可能收到送至相同地點的另一單外賣而帶來的無額外成本的收益 r。假設 0<=P_c<=min{l_e/r，1}）。

• 第三題
  

a. 馬教授的領域內有 n 個不同但是等價的邏輯陳述，A₁，A₂，...，A_n，現在需要證明它們是等價的。每個學期，馬教授選兩個不同的陳述 A_i 和 A_j，以「A_i->A_j」的證明作為研究課題，指導一位本科生完成。假設每個學期只完成一個證明。要注意的是，在「A_i->A_j」和「A_j->A_k」被證明之后，「A_i->A_k」也已經被自動的證明了，因此不能再作為一個新的課題讓學生去完成。總之，如果一個課題是之前若干學生已經完成課題的直接推論，則不能作為新課題發給另一個學生。隨著越來越多的推出關系被證明，剩下可選擇的課題也越來越少。請問，馬教授可以最多依次指導多少個學生呢？為什么？

b.H 是一個 n x n 的方陣，其第 i 行第 j 列的元素是 h_ij，所有 h_ij的取值集合為{1，-1}，并且 H 的任意不同的兩行看作向量是相互垂直的（即，他們的標準內積為 0）。假設 H 有一個 a x b 的子矩陣（1<=a,b<=n），子矩陣內的元素均為 1。請證明 a，b<=n。

c.G 是一個群。e 是該群的單位元。定義 G 的一個子集：

F = { h 屬于 G | 存在自然數 m >= 1，使得 h^m = e }。

假設集合 F 內的元素是有限多個的。證明：存在一個自然數 n >= 1 使得對所有 g 屬于 G 和 h 屬于 F，我們都有：

以上就是全部預選賽試題，阿里巴巴數學競賽官方網站也給出了這些題目的參考答案。

• 第一題答案
  

A.709 元人民幣。

為了得到這個答案，我們必須要使用其它店鋪的優惠券。如果所有的優惠券都來自店鋪 A，那么付款金額可以減少到 705，但在實際中，這個是行不通的。下面是如何得到 709 人民幣的具體步驟：
下面我們來比較耳機和音箱一起買與耳機和音箱分開買這兩種購買方案，其中，分開購買可以獲得更小的支付金額，也就是 709 元。

在同一個訂單中購買耳機和音箱：

耳機 250 元，加上音箱的 600 元也就是 850 元，由于在店鋪 A 每滿 60 可以使用一張 5 元優惠券，60*14=840，因此可以在店鋪 A 使用 14 張優惠券。此外，電商平臺全場提供的滿 299 減 60 的優惠券也可以使用。

于是，在同一個訂單中購買耳機和音箱總共需要花費的金額為：

850-14*5-60=720 元

耳機和音箱分兩個訂單中購買：

這種方案最終的花費為 709，具體的購買方法如下：

耳機的價格是 250 元，因此可以湊單一件 49 元的商品，這樣就可以使用 4 張 5 元優惠券，以及一張滿 299 減 60 的優惠券。算下來需要的花費為 250+49-4*5-60=219 元。

音箱的價格是 600 元，可以使用 10 張滿 60 減 5 元的優惠券和 1 張滿 299 減 60 元的優惠券。于是需要花費的金額為 600-60-10*5=490 元。

因此，耳機和音箱分別購買需要的總花費為 219+490=709 元。

綜上所述，最小花費是 709 元，采用的方案是耳機和音箱分兩單購買，并且耳機那個訂單要湊單一件 49 元的商品。

B. 問題 1 答案為：如果使用其它店鋪的優惠券，那么 x 為 21；如果只使用店鋪 A 的優惠券，那么 x 為 25。

問題 2 答案為：如果使用其它店鋪的優惠券，那么 x 為 36；如果使用店鋪 A 的優惠券，那么 x 為 38。

具體步驟為：

問題 1：為了在你的店鋪里面買一副耳機，某個人需要支付的錢數為 250-x+49（湊單品價格）-60（平臺提供的滿 299 減 60 優惠券）=（239-x）元。對于音箱，我們也用同樣的方法計算，得到的這個人需要支付的金額為（540-x）元。為了減少你的店鋪在耳機上的花費，x 必須滿足的條件為 239-x<=219，或者 x>=21；為了讓你的店鋪減少在音箱上的花費，x 必須滿足 540-x<=490-1，或者 x>=51。當 x 為 21 時，我們可以保證購買耳機是便宜的，但是此時，音箱并不是最便宜的。

問題 2：如果在你的店鋪里面買耳機和音箱，那么分兩單分別購買耳機和音箱更劃算，因為這樣可以獲得的總折扣金額為 2x。這兩個訂單的金額分別為（239-x）和（540-x）。它們的總金額肯定比 709 元要小，那么第二個問題的答案是什么？在這里，x 滿足的條件為（239-x）+（540-x）<=709-1，或者 x>=35.5。因為 x 必須是整數，所以我們求得這個問題的答案為 x=36。

C. 題目 1 答案：最優價格為，期望利潤為，i=1，2。在 i 為 1 或者 2 的時候，步驟都是一樣的。我們用 R 表示利潤這個變量，它隨著 S 的變化而變化。公式為：

同樣的，我們也可以算出期望利潤作為產品的利潤，（p-c），購買的可能性為 (u-p)/u。
函數 是一個凹二次曲線函數，因此它的極大值點 p*如果在 [0，u] 這個區間取得，則滿足條件，此時，p*=(u+c)/2，如果 c<=u，那么在該點處函數取得最大值。否則，在 p*=u 處取得最大值。

當 p*=(u+c)/2 時，我們可以得到。

題目 2 答案：價格  的最大值為：

注意到 是關于 的分段函數，分成了三段，我們可以算出每個鄰域內的邊界點。
同樣我們注意到，計算結果并不是唯一的，學生可以畫出函數的曲線圖，根據這個曲線圖來找出正確答案。

不管用什么方法，我們需要三步來計算出 。

步驟 1：定義變量 ，計算  的分布并記為 ，這個分布并不是均勻分布。

步驟 2：計算期望利潤，為

對于，當時，有。

步驟 3：對于每個區間來說，最大值就是期望利潤，也就是說，必須要找到 在每個區間的最大值。
當 的取值區間為 [0，u1] 時，的倒數為

畫出函數的曲線或者檢查它的二階導數，可以很容易地看出上面的 的極大值。從 ，可以得到 ，在這種情況下， 是期望利潤的最大值。

采用相同的步驟，我們可以求出在另外兩種情況下的 值和它對應的 的值。

題目 3 答案：不一定，沒有哪一種策略比其余的策略好。

可以使用兩個例子來證明這一點，第一個策略采用的方法比第二個好，第二個策略采用的方式比第一個好。有很多這樣的例子，我們就不具體舉例了。

• 第二題答案
  

題目 a 答案： 最短的路徑長度是 16。獲得這個數值的方法是采用下面的順序進行送餐：

A -> B2 -> C2 -> B1 -> B3 -> C3 -> C1

具體來說，有兩種送餐路線可以使路徑長度為 16，它們有輕微的不同，即：

路線1：

路線2：

這兩條路線都可以經過所有的取餐點。

羅列出所有的路線并計算他們的路徑長度是一件非常繁瑣的工作，然而，在這個題目里面我們不需要這樣做。因為這個圖是一個平面圖，并且路線的方向和目的地的距離總是 90 度。這就意味著，任意兩個點之間的最短路徑都是很容易求得的。

要手動計算出這個問題的答案，首先可以大致估算一下 {B₁,C₁,B₂,C₂,B₃,C₃} 的順序并計算出路徑長度。實際上，有很多排序方式可以讓路徑的長度為 17，如果你算出的值比這個稍微高一點兒，那么就是一個好的排列順序。這個距離是最短距離的上限。然后羅列 {B₁,C₁,B₂,C₂,B₃,C₃}的順序并計算出路徑長度，一旦長度達到 17，就排除這個路線。當你找到一條總長度為 16 的路線時，上限改為 16，這個策略叫做分支界限法。

題目 b 答案：對于問題 1 來說，P₁ + P₂ + ... + P_m。我們讓 的取值為 0 或者 1，邊界為 ，對于 i = 1,2,...,m 來說，我們可以通過下面的方法來計算答案：

對于問題 2 來說，是。在這里，（1-P_i）是在 e_i 處沒有外賣的概率，并且我們可以根據概率論知識知道， 是整個路線上都沒有外賣的概率，因此，1 減去這個概率值是最少可以在這條路線上取到一個外賣的概率。同時，可以使用條件概率來得到的遞歸公式為，在e₁之后最少可以獲得一單新外賣的概率為，也就是，通過不斷的遞歸，可以得到最終的式子為，這個遞歸也是一個正確答案。

上面的兩個答案都可以和下面這個式子等同：

題目 c 答案： 假設我們不考慮一般性的情況，現在有 T 個節點，并且 T 是目的節點。首先，對于每個節點 i，找到去 T 的最短路線和對應的路線長度 （如果具有相同長度的不同路線之前有相互關系，一定要解除他們之間的關系）。對于 i=T，我們有。

接下來，使用 ，在每個節點計算最優預期回報 ，使用下面給出的極大值公式（3）來計算。對于 ，假設 是 i 的相鄰節點，并且在該點處能取得極大值（同樣地，如果節點之間有關聯，打破這個關聯）。

外賣小哥的最優路線被下面的每個點決定了：在節點 i 的時候，如果外賣小哥還沒有拿到額外的一單，那么移動到；如果外賣小哥拿到了額外的一單，那么他車上的外賣箱子已經裝滿了，因此只需要走從 i 到 T 的最短路線。

注意到上面的路線并不是事先計劃好的，而是由外賣小哥自己決定的。也就是說，這是一個策略問題。這種方式比事先計劃好路線要好，因為是否會有額外的外賣單是未知的，而這會影響路線、影響到 T 的距離。

當外賣小哥在節點 i 并且取到了第二個外賣的時候，外賣小哥決定去哪里采用的方法是去這個地方獲得的收益的期望值，這個收益值又被獲取外賣的可能性和到 T 節點的距離所影響。

定義在取到額外的外賣前，在節點 i 的最優預期收益為。當 i=T 時，我們讓，這個是固定的收益。假設我們計算了 i 的相鄰節點。在節點 i 的時候，如果我們要移動到節點 j，那么預期收益將會變成：

• ，如果在 i、j 兩點之間出現外賣；
  

• ，如果在 i、j 兩點之間不出現外賣。

設 i、j 之間的邊長度為 ，則有：

        （3）

這就是眾所周知的貝爾曼方程。

根據和式子（3），我們可以計算出 ，你可以使用動態規劃或者更具體的圖，貝爾曼·福特算法或者迪杰特斯拉算法（請看下面的說明）。它們都從開始，并且決定了 這個集合里面的元素。

對于 或者 ，必須要避免「正面獎勵」的存在，這可以避免外賣小哥為了獲得額外的報酬而不停地在這些路線走來走去，直到取到額外的一單外賣這種不現實的情況。

我們注意到，在實際中，學生們更傾向于使用迪杰特斯拉算法。這種算法要求邊長必須是非負的值。因此，如果一個人使用這個算法去計算 ，必須要滿足這個條件。對于我們的這個問題，這里必須要滿足：
             （4）

在滿足假設條件 的條件下，這種情況確實存在。為什么呢？既然最壞的情況也就是外賣小哥沿著最短路徑到達 T 節點處（而不是選擇使收益最大化的節點），我們可以得到：

于是可以得到第二個不等式：

第一個不等式的假設條件是 不大于，我們可以結合上面的不等式得到式子（4）。

• 第三題答案
  

題目 a 答案：我們首先指導 0.5(n+2)(n-1) 個學生，下面，我們將證明這個答案。

解釋：首先，(n-1) 個學生證明 A₁->A_i，其中 i 為 2 到 n 的整數；然后，(n-2) 個學生證明 A₂->A_i，其中 i 為 3 到 n 的整數。一直這樣做，直到最后一個學生證明 A_n-1->A_n。
然后，(n-1) 個學生證明 A_n->A_n-1，A_n-1->A_n-1，...，A₂->A₁。它們的總數為：

讓 。

最優性證明：假設圖 G=（N，E）的節點為 N={1,2，...，n}，其有向邊為 E={（i，j）|A_i -> A_j已經被證明了}。完成一個課題，意味著給 E 加上一條邊。

假設 E': = { （i, j ) | 其中，A_i -> A_j 和 A_j -> A_i在前面已經被證明了 } 是對偶邊，是集合 E 的子集，子圖 G’=（N，E'）最多有 2(n-1) 個有向邊；否則，必然存在一些對偶邊包含無效課題。

G 最多有 n(n-2)/2 對節點，去掉對偶邊上的節點，正如前面所證明的，此時最多有 2(n-1) 個有向邊，因此最多有 (n-1) 對有向邊，也就是說，有 n(n-1)/2 - (n-1) = (n-2)(n-1)/2 對節點之間是單向邊或者是沒有邊的。因此，最多有 (n-2)(n-1)/2 個單向邊。因此，加上單向邊和對偶邊的最大數得：

題目 b 答案：對于任何 a 行 b 列的矩陣 A ，都有：

                              （5）

設 ||A|| 為矩陣的譜范數，為矩陣的 Frobenius 范數。

在我們的題目中，既然 H 是 n 行 n 列的正交矩陣，則有。對于 H 的任何子矩陣 A來說，都有。當子矩陣 A 為 a 行 b 列矩陣，且其元素全部為 1 時，則有和 rank(A) = 1，于是可以得到：

 題目 c 答案：證明：取。設滿足，讓。由于：

由 F 的定義，我們可以得到：

因此，可以得到，。對于來說也是一樣的。F 是有限的，對于每個 h，存在，使得。取，對任何屬于 F 的 h，n 是的倍數，也就是說，。因此，從，我們可以得到：

進而可以得到： 

雷鋒網

雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。