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

來自于 11 個(gè)國家和地區(qū)的選手參加了比賽，而年齡最小的僅 13 歲，年紀(jì)最大的年近五旬。最終，有 328 位選手通過了預(yù)選賽，進(jìn)入決賽。其中有很多在國際數(shù)學(xué)競(jìng)賽中取得優(yōu)異成績(jī)的「大神」。

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

官網(wǎng)獲獎(jiǎng)名單圖

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

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

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

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

全球「最強(qiáng) 51 人」分布圖

可以看到，從全球4萬多名參賽者中脫穎而出的「最強(qiáng) 51 人」來自 20 多所全球一流大學(xué)，國內(nèi)選手 28 人，海外選手 23 人。其中北京大學(xué)貢獻(xiàn)了 13 位獲獎(jiǎng)選手，是獲獎(jiǎng)人數(shù)最多的高校，麻省理工學(xué)院次之，貢獻(xiàn) 4 名獲獎(jiǎng)選手。獲獎(jiǎng)?wù)咧心挲g最小的獲獎(jiǎng)?wù)邇H有 18 歲。

這 51 人均將獲得由多位國際著名數(shù)學(xué)家領(lǐng)銜授課的數(shù)學(xué)大師班門票。同時(shí)，獲得金銀銅獎(jiǎng)的 20 名選手將會(huì)共同分享總額 100 萬元的獎(jiǎng)學(xué)金。

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

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

預(yù)選賽具體形式是應(yīng)用題&建模題&數(shù)學(xué)基礎(chǔ)題，共三題，每題三問，需要提供解題步驟。第一題 30 分，第二題 40 分，第三題 30 分，全部正確解決問題得滿分。組委會(huì)會(huì)選擇前 300 名進(jìn)入決賽。

• 第一題

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

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

B. 現(xiàn)在您開了一家電商店鋪，賣與 A 店同款的耳機(jī)和音箱，標(biāo)價(jià)相同，您計(jì)劃提供滿 99 返 x 的優(yōu)惠券，x 為大于 0，小于 99 的整數(shù)，與 A 店不同的是，您的優(yōu)惠券每單限用一張（比如，買 250 塊需付 250-x 塊，而不是 250-2x 塊）。雙 11 期間，電商平臺(tái)全場(chǎng)滿 299 減 60 依然適用。
請(qǐng)問：x 至少等于多少時(shí)，小明在您的店鋪買耳機(jī)和音箱其中一種會(huì)更便宜（至少 1 元）？又請(qǐng)問：x 至少等于多少時(shí)，小明在您的店鋪既買耳機(jī)又買音箱總和會(huì)更便宜（至少 1 元）？

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

1. 如何分別設(shè)定產(chǎn)品價(jià)格 p₁ 和 p₂，以最大化每個(gè)到訪客戶帶來的利潤(rùn)期望。這里假設(shè) c₁<u₁；當(dāng)且僅當(dāng) p₁<=S₁ 時(shí)，客戶會(huì)購買一件商品 1；用戶不買的話不計(jì)損失。對(duì)產(chǎn)品 2 做類似假設(shè)。請(qǐng)以公式形式給出最優(yōu)價(jià)格 p₁*和 p₂*以及對(duì)應(yīng)的最大利潤(rùn)期望 r₁*和 r₂*。
   

2. 現(xiàn)在假設(shè)產(chǎn)品 1 和 2 捆綁銷售，成本是 c₁₂=t（c₁+c₂）。因?yàn)楣?jié)省了包裝和運(yùn)輸成本，假設(shè) 0<t<1。其余的條件不變。請(qǐng)以公式形式給出捆綁下的最優(yōu)價(jià) p₁₂*。
   

3. 單賣和捆綁銷售，哪個(gè)利潤(rùn)更優(yōu)，還是不一定？為什么？
   

• 第二題
  

a. 附圖中有一個(gè)無向圖，其中圈內(nèi)數(shù)字代表一個(gè)地點(diǎn)，邊 e 上的數(shù)字代表長(zhǎng)度 L_e（雙向相同）。一位外賣小哥在起點(diǎn) A，要去 3 個(gè)商家（B₁，B₂，B₃）取餐，送到 3 個(gè)對(duì)應(yīng)的地方（C₁，C₂，C₃），即 B₁ 至 C₁，B₂ 至 C₂，B₃ 至 C₃。小哥的電動(dòng)動(dòng)力車的箱子同時(shí)最多裝下 2 份外賣。

請(qǐng)問：小哥該怎么走最短路徑？這個(gè)最短路徑的長(zhǎng)度是多少，這里 A 是出發(fā)點(diǎn)，最后一餐（不限次序）送達(dá)地為終點(diǎn)。為了簡(jiǎn)化問題，假設(shè)商家已經(jīng)準(zhǔn)備好了外賣，小哥取餐送餐不用等。又假設(shè)每份外賣重量大小一樣。

b. 此題與上圖無關(guān)，而是考慮一個(gè)一般的圖，圖中有很多點(diǎn)和邊。外賣小哥剛剛?cè)×艘环萃赓u，計(jì)劃通過圖上的邊 e₁、e₂...e_m 送給目的地，途中經(jīng)過每條邊 e 的時(shí)候，以概率 P_e[0,1] 會(huì)收到送至相同地點(diǎn)的另一單外賣。（一條邊上收到另兩單及以上的概率小，暫忽略不計(jì)）。假設(shè)對(duì)應(yīng)邊 e₁、e₂...e_m 的概率為 P₁、P₂...P_m。

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

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

• 第三題
  

a. 馬教授的領(lǐng)域內(nèi)有 n 個(gè)不同但是等價(jià)的邏輯陳述，A₁，A₂，...，A_n，現(xiàn)在需要證明它們是等價(jià)的。每個(gè)學(xué)期，馬教授選兩個(gè)不同的陳述 A_i 和 A_j，以「A_i->A_j」的證明作為研究課題，指導(dǎo)一位本科生完成。假設(shè)每個(gè)學(xué)期只完成一個(gè)證明。要注意的是，在「A_i->A_j」和「A_j->A_k」被證明之后，「A_i->A_k」也已經(jīng)被自動(dòng)的證明了，因此不能再作為一個(gè)新的課題讓學(xué)生去完成?？傊绻粋€(gè)課題是之前若干學(xué)生已經(jīng)完成課題的直接推論，則不能作為新課題發(fā)給另一個(gè)學(xué)生。隨著越來越多的推出關(guān)系被證明，剩下可選擇的課題也越來越少。請(qǐng)問，馬教授可以最多依次指導(dǎo)多少個(gè)學(xué)生呢？為什么？

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

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

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

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

以上就是全部預(yù)選賽試題，阿里巴巴數(shù)學(xué)競(jìng)賽官方網(wǎng)站也給出了這些題目的參考答案。

• 第一題答案
  

A.709 元人民幣。

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

在同一個(gè)訂單中購買耳機(jī)和音箱：

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

于是，在同一個(gè)訂單中購買耳機(jī)和音箱總共需要花費(fèi)的金額為：

850-14*5-60=720 元

耳機(jī)和音箱分兩個(gè)訂單中購買：

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

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

音箱的價(jià)格是 600 元，可以使用 10 張滿 60 減 5 元的優(yōu)惠券和 1 張滿 299 減 60 元的優(yōu)惠券。于是需要花費(fèi)的金額為 600-60-10*5=490 元。

因此，耳機(jī)和音箱分別購買需要的總花費(fèi)為 219+490=709 元。

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

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

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

具體步驟為：

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

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

C. 題目 1 答案：最優(yōu)價(jià)格為，期望利潤(rùn)為，i=1，2。在 i 為 1 或者 2 的時(shí)候，步驟都是一樣的。我們用 R 表示利潤(rùn)這個(gè)變量，它隨著 S 的變化而變化。公式為：

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

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

題目 2 答案：價(jià)格  的最大值為：

注意到 是關(guān)于 的分段函數(shù)，分成了三段，我們可以算出每個(gè)鄰域內(nèi)的邊界點(diǎn)。
同樣我們注意到，計(jì)算結(jié)果并不是唯一的，學(xué)生可以畫出函數(shù)的曲線圖，根據(jù)這個(gè)曲線圖來找出正確答案。

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

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

步驟 2：計(jì)算期望利潤(rùn)，為

對(duì)于，當(dāng)時(shí)，有。

步驟 3：對(duì)于每個(gè)區(qū)間來說，最大值就是期望利潤(rùn)，也就是說，必須要找到 在每個(gè)區(qū)間的最大值。
當(dāng) 的取值區(qū)間為 [0，u1] 時(shí)，的倒數(shù)為

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

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

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

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

• 第二題答案
  

題目 a 答案： 最短的路徑長(zhǎng)度是 16。獲得這個(gè)數(shù)值的方法是采用下面的順序進(jìn)行送餐：

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

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

路線1：

路線2：

這兩條路線都可以經(jīng)過所有的取餐點(diǎn)。

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

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

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

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

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

題目 c 答案： 假設(shè)我們不考慮一般性的情況，現(xiàn)在有 T 個(gè)節(jié)點(diǎn)，并且 T 是目的節(jié)點(diǎn)。首先，對(duì)于每個(gè)節(jié)點(diǎn) i，找到去 T 的最短路線和對(duì)應(yīng)的路線長(zhǎng)度 （如果具有相同長(zhǎng)度的不同路線之前有相互關(guān)系，一定要解除他們之間的關(guān)系）。對(duì)于 i=T，我們有。

接下來，使用 ，在每個(gè)節(jié)點(diǎn)計(jì)算最優(yōu)預(yù)期回報(bào) ，使用下面給出的極大值公式（3）來計(jì)算。對(duì)于 ，假設(shè) 是 i 的相鄰節(jié)點(diǎn)，并且在該點(diǎn)處能取得極大值（同樣地，如果節(jié)點(diǎn)之間有關(guān)聯(lián)，打破這個(gè)關(guān)聯(lián)）。

外賣小哥的最優(yōu)路線被下面的每個(gè)點(diǎn)決定了：在節(jié)點(diǎn) i 的時(shí)候，如果外賣小哥還沒有拿到額外的一單，那么移動(dòng)到；如果外賣小哥拿到了額外的一單，那么他車上的外賣箱子已經(jīng)裝滿了，因此只需要走從 i 到 T 的最短路線。

注意到上面的路線并不是事先計(jì)劃好的，而是由外賣小哥自己決定的。也就是說，這是一個(gè)策略問題。這種方式比事先計(jì)劃好路線要好，因?yàn)槭欠駮?huì)有額外的外賣單是未知的，而這會(huì)影響路線、影響到 T 的距離。

當(dāng)外賣小哥在節(jié)點(diǎn) i 并且取到了第二個(gè)外賣的時(shí)候，外賣小哥決定去哪里采用的方法是去這個(gè)地方獲得的收益的期望值，這個(gè)收益值又被獲取外賣的可能性和到 T 節(jié)點(diǎn)的距離所影響。

定義在取到額外的外賣前，在節(jié)點(diǎn) i 的最優(yōu)預(yù)期收益為。當(dāng) i=T 時(shí)，我們讓，這個(gè)是固定的收益。假設(shè)我們計(jì)算了 i 的相鄰節(jié)點(diǎn)。在節(jié)點(diǎn) i 的時(shí)候，如果我們要移動(dòng)到節(jié)點(diǎn) j，那么預(yù)期收益將會(huì)變成：

• ，如果在 i、j 兩點(diǎn)之間出現(xiàn)外賣；
  

• ，如果在 i、j 兩點(diǎn)之間不出現(xiàn)外賣。

設(shè) i、j 之間的邊長(zhǎng)度為 ，則有：

        （3）

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

根據(jù)和式子（3），我們可以計(jì)算出 ，你可以使用動(dòng)態(tài)規(guī)劃或者更具體的圖，貝爾曼·福特算法或者迪杰特斯拉算法（請(qǐng)看下面的說明）。它們都從開始，并且決定了 這個(gè)集合里面的元素。

對(duì)于 或者 ，必須要避免「正面獎(jiǎng)勵(lì)」的存在，這可以避免外賣小哥為了獲得額外的報(bào)酬而不停地在這些路線走來走去，直到取到額外的一單外賣這種不現(xiàn)實(shí)的情況。

我們注意到，在實(shí)際中，學(xué)生們更傾向于使用迪杰特斯拉算法。這種算法要求邊長(zhǎng)必須是非負(fù)的值。因此，如果一個(gè)人使用這個(gè)算法去計(jì)算 ，必須要滿足這個(gè)條件。對(duì)于我們的這個(gè)問題，這里必須要滿足：
             （4）

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

于是可以得到第二個(gè)不等式：

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

• 第三題答案
  

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

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

讓 。

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

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

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

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

                              （5）

設(shè) ||A|| 為矩陣的譜范數(shù)，為矩陣的 Frobenius 范數(shù)。

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

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

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

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

進(jìn)而可以得到： 

雷鋒網(wǎng)

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。