阿里巴巴全球數(shù)學(xué)競賽2021年預(yù)選賽試題及參考答案

1第三屆阿里巴巴全球數(shù)學(xué)競賽預(yù)賽部分參考答案1,2.在一個虛擬的世界中,每個居民(設(shè)想為沒有大小的幾何點)依次編號為1,2,···.為了抗擊某種疫情,這些居民要接種某疫苗,并在注射后在現(xiàn)場留觀一段時間?，F(xiàn)在假設(shè)留觀的場所是平面上的一個半徑為的圓周。為了安全,要求第m號居民和第n號居民之間的距離dm,n滿足(m+n)dm,n≥1,這里我們考慮的是圓周上的距離,也就是兩點間劣弧的弧長。那么1選擇題(4分)下列選項()符合實際情況。A這個留觀室最多能容納8個居民;B這個留觀室能容納的居民個數(shù)有大于8的上限;C這個留觀室可以容納任意多個居民。2證明題(6分)證明你的論斷。2R1答案.選項C符合實際情況.R2答案.解法一.我們可以按下述方式安排第1,2,...號居民的位置.首先,任意安排慮第n號居民不能在哪些位置。對于1≤m≤n1,由dm,n≥,我們知道,從第m號居民的位置開始,沿順、逆時針方向各走的距離,所形成的長度為的圓弧內(nèi)部是不可以安排第n號居民的.而這些圓弧的總長度因此,這些圓弧的并集的總長度不超過2ln2,而整個圓周長為·2π=.熟知1.5>2ln2,故這些圓弧不能覆蓋整個圓周,因此第n號居民總可以選擇一個合適的位置,使得他與第1,2,...,n—1號居民之間的距離均滿足題目條件.由數(shù)學(xué)歸納法可知,這個圓周可以容納任意多個居民.解法二.我們以圓周的圓心為原點建立平面直角坐標系,并將第1,2,3,4號居民分別居民的距離不小于故此時的4名居民滿足題目條件.我們使用數(shù)學(xué)歸納法證明下面命題:對整數(shù)k>2,可以將第1,2,...,2k號居民安置于圓周上一個內(nèi)接正2k邊形的各個頂點處,使得它們互相之間(在圓周上的)距離滿足題目條件,且編號為1,2,...,2k-1號的居民在圓周上兩兩不相鄰.上述命題對k=2成立.若其對k成立,即前2k號居民的位置都已確定.考慮他們將圓周分成的2k段弧.我們要將第2k+1,2k+2,...,2k+1號居民放置在這些弧的中點.現(xiàn)在來證明可以適當放置使得涉及第2k+1,2k+2,...,2k+1號居民的距離均滿足題目條件.我們將第2k+1,2k+2號居民放置在與第2k-1號居民相鄰的位置(即與第2k-1號居民的輻角差為將第2k+3,2k+4號居民放置在與第2k-1—1號居民2k+1號居民放置在與第1號居民相鄰的位置.由于前2k-1號居民在圓周上兩兩不相鄰,這樣的放置是可行的.現(xiàn)在考慮任意兩名居民的距離(只需考慮至少一位居民是“新”的情形).因為圓周被分成了2k+1段,每段弧長為對于兩位編號分別為m>2k和n的居民,若它們之間至少有兩段若他們之間的距離恰為一段弧長,設(shè)n∈{2k+2a—1,2k+2a},則m>2k-1—a+1,因3此所以?第1,2,...,2k+1號居民兩兩之間的距離均滿足題目條件.由數(shù)學(xué)歸納法知,可以安排任意多名居民.43,4.2019年第一屆阿里巴巴數(shù)學(xué)競賽的優(yōu)勝者們在參加集訓(xùn)營的時候,集體送給主辦方負責(zé)人的禮物,是一個有60個全等的三角形面的多面體。從圖中我們可以看到,這個多面體的表面是60個全等的空間四邊形拼接而成的。一個空間n邊形是指由一個平面n邊形沿若干條對角線做適當翻折(即在選定的對角線處形成適當?shù)亩娼?后得到的空間圖形。兩個空間圖形全等指的是它們可以通過R3中的一個等距變換完全重合。一個多面體指的是一個空間有界區(qū)域,其邊界可以由有限多個平面多邊形沿公共邊拼接而成。3判斷題(4分)我們知道2021=43×47.那么是否存在一個多面體,它的表面可以由43個全等的空間47邊形拼接而成?4問答題(6分)請對你的判斷給出邏輯的解釋。5R3答案.可以.R4答案.我們只需要舉一個例子即可.考慮一個標準的環(huán)面T,其上的點可以由兩個參數(shù)來表示:T={θ,?:0≤θ,?<2π}.我們可以認為這個環(huán)面以z-軸為對稱軸:(θ,?)對應(yīng)于空間中的((R+rcos?)cosθ,(R+rcos?)sinθ,rsin?).對于1≤k≤43,我們考慮環(huán)面上的區(qū)域直觀地說,把環(huán)面分成全等的43份之后,每一份沿{?=0}切開,將切開處的一側(cè)保持不動,另一側(cè)扭轉(zhuǎn)一定角度.現(xiàn)在,把{?=0}這個圓變形成一個正43邊形,各個頂點分別對應(yīng)于θ.這樣Dk有四條“邊”(其中兩條位于{?=0}上),四個頂點(兩個位于正43邊形的頂點處,兩個位于邊的中點處,我們還要標記出這兩個中點之間的正43邊形的頂點).記為在?Dk的另一條邊上取21個點,例如然后繞z-軸旋轉(zhuǎn)后得到另21個點,記為Bk,i,i=1,...,21.連結(jié)線段Ck,0Ck,1,Ck,0Ak,1,Ck,1Bk,1,Ak,iAk,i+1,Bk,iBk,i+1,Ak,iBk,i,Ak,iBk,i+1(i=1,...,21),以及Ak,21Dk,0,Bk,21Dk,1,Ak,21Ek,Bk,21Ek,Dk,0Ek和EkDk,1.我們得到一個空間47邊形.這樣我們就得到了43個全等的(上述構(gòu)造與k無關(guān))空間47邊形,它們能夠拼出一個多面體.說明:一個典型的錯誤是誤認為這些空間多邊形的頂點(邊)都是多面體的頂點(邊),從而根據(jù)“每條邊都算兩次”和“2021是奇數(shù)”得到“矛盾”,由此認為本題的解答是否定的.65.去年,張師傅因為多旋圈面爆紅,今年他來到了達摩院給掃地僧做面。某天,軟件工程師小李跟張師傅吐槽工作。小李主要研究和設(shè)計算法用于調(diào)節(jié)各種產(chǎn)品的參數(shù)。這樣的參數(shù)一般可以通過極小化Rn上的某個損失函數(shù)f求得。在小李最近的一個項目中,這個損失函數(shù)是另外一個課題組提供的;出于安全考慮和技術(shù)原因,該課題組難以向小李給出此函數(shù)的內(nèi)部細節(jié),而只能提供一個接口用于計算任意x∈Rn處的函數(shù)值f(x)。所以,小李必須僅基于函數(shù)值來極小化f。而且,每次計算f的值都消耗不小的計算資源。好在該問題的維度n不是很高(10左右)。另外,提供函數(shù)的同事還告知小李不妨先假設(shè)f是光滑的。這個問題讓張師傅想起了自己收藏的一臺古董收音機。要在這臺收音機上收聽一個節(jié)目,你需要小心地來回擰一個調(diào)頻旋鈕,同時注意收音效果,直到達到最佳。在這過程中,沒有人確切地知道旋鈕的角度和收音效果之間的定量關(guān)系是什么。張師傅和小李意識到,極小化f不過就是調(diào)節(jié)一臺有多個旋鈕的機器:想象x的每一個分量由一個旋鈕控制,而f(x)表示這臺機器的某種性能,只要我們來回調(diào)整每個旋鈕,同時監(jiān)視f的值,應(yīng)該就有希望找到最佳的x。受此啟發(fā),兩人一起提出了極小化f的一個迭代算法,并命名為“自動前后調(diào)整算法”(AutomatedForward/BackwardTuning,AFBT,算法1)。在第k次迭代中,AFBT通過前后調(diào)整xk的單個分量得到2n個點{xk±tkei:i=1,...,n},其中tk為步長;然后,令yk為這些點中函數(shù)值最小的一個,并檢查yk是否使f充分減小;若是,取xk+1=yk,并將步長增倍;否則,令xk+1=xk并將步長減半。在算法1中,ei表示Rn中的第i個坐標向量,它的第i個分量為1,其余皆為0;1(·)為指示函數(shù)—–若f(xk)?f(yk)至少為tk之平方,則1[f(xk)?f(yk)≥t]取值為1,否則為0。算法1自動前后調(diào)整算法(AFBT)輸入x0,執(zhí)行以下循環(huán)。1:yk:=argmin{f(y):y=xk±tkei,i=1,...,n}#計算損失函數(shù)。2:sk:=1[f(xk)?f(yk)≥t]#是否充分下降?是:sk=1;否:sk=0。3:xk+1:=(1?sk)xk+skyk#更新迭代點。4:tk+1:=22sk-1tk#更新步長。sk=1:步長增倍;sk=0:步長減半。現(xiàn)在,我們對損失函數(shù)f:Rn→R作出如下假設(shè)。假設(shè)1.f為凸函數(shù),即對任何x,y∈Rn與Q∈[0,1]都有f((1?Q)x+Qy)≤(1?Q)f(x)+Qf(y).假設(shè)2.f在Rn上可微且?f在Rn上L-Lipschitz連續(xù)。假設(shè)3.f的水平集有界,即對任意λ∈R,集合{x∈Rn:f(x)≤λ}皆有界。7基于假設(shè)1與假設(shè)2?可以證明對任何x;y∈Rn成立;假設(shè)1與假設(shè)3則保證f在Rn上取到有限的最小值f*"凸函數(shù)的更多性質(zhì)可參考任何一本凸分析教科書"證明題(20分)在假設(shè)1–3下?對于AFBT?證明8R5證明.假設(shè)f(xk)。f*"因{f(xk)}不增,故infk≥0[f(xk)?f*]>0"記gk=?f(xk),*使f(x*)=f*,則f之凸性保證〈gk,xk?x*〉≥f(xk)?f*;同時?{f(xk)}之單調(diào)性與f之水平集有界性保證{xk?x*}有界"故infk≥0ⅡgkⅡ>0)"換言之?存在ε>0使ⅡgkⅡ≥ε對所有k≥0成立"任給k≥0,可取ik∈{1,...,n}滿足k其中h=1/√故所以?只要我們就有f(yk)≤f(xk)?t,從而sk=1,進而有tk+1=2tk"由此?易見對所有k≥0成立"故存在無窮個k使得sk=1(否則tk→0);對每一個這樣的k,f(xk)?f(xk+1)≥t2"這與f下方有界相矛盾"故所論成立"96.令n為正整數(shù)"對任一正整數(shù)k,記0k=diag為k×k的零矩陣"令為一個(2n+1)×(2n+1)矩陣,其中A=(xi,j)1≤i≤n,1≤j≤n+1是一個n×(n+1)實矩陣且At記A的轉(zhuǎn)置矩陣?即(n+1)×n的矩陣?(j,i)處元素為xi,j.(i)證明題(10分)稱復(fù)數(shù)λ為k×k矩陣X的一個特征值,如果存在非零列向量v=(x1,...,xk)t使得Xv=λv.證明:0是Y的特征值且Y的其他特征值形如±√λ,其中非負實數(shù)λ是AAt的特征值"(ii)證明題(15分)令n=3且a1,a2,a3,a4是4個互不相等的正實數(shù)"記,其中δi,j={.證明:Y有7個互不相等的特征值"R6證明記In=diag為n×n恒同矩陣.作初等變換可證ndet(λI2n+1—Y)=λdet(λ2In—AAt).所以,0是Y的特征值且Y的其他特征值形如±√λ,其中λ是AAt的非負實數(shù)特征值.計算得AAt=diag{a,...,a}+utu—vtv.設(shè)f(s)=det(sIn—AAt)為AAt的特征多項式.計算得234經(jīng)重排后得到的遞減序列.由f(x)的a>b1>a>b2>a>b3>a的正實數(shù).因此,由(i)得Y有7個互不相等的特征值.7.對于R上的連續(xù)且絕對可積的復(fù)數(shù)值函數(shù)f(x),定義R上的函數(shù)(Sf)(x):(i)問答題(10分和的顯式表達式"(ii)問答題(15分)對任意整數(shù)k,記fk(x)=(1+x2)-1-k.假設(shè)k≥1,找到常2使得函數(shù)y=(Sfk)(x)滿足二階常微分方程xyII+c1yI+c2xy=0.R7答案:(i)且(ii)c1=-2k且c2=-4π2.解答記V為R上的復(fù)數(shù)值、連續(xù)、絕對可積的函數(shù)組成的線性空間.Lemma0.1.(i)若f(x)∈V,fI(x)∈V且limx→∞f(x)=0,則(SfI)(x)=-2πix(Sf)(x).(5)(ii)若f(x)∈V且xf(x)∈V,則(Sf)I=2πiS(xf(x)).(6)引理0.1的證明.(i)=-2πix(Sf)(x)=(Sf)(b)-(Sf)(a).這樣,(Sf)I=2πiS(xf(x)).引理0.1有如下推論.Corollary0.2.(i)假設(shè)f,fI,Sf,x(Sf)(x)∈V且若(S(Sf))(x)=f(-x),則(S(SfI))(x)=fI(-x).(ii)假設(shè)f(x),xf(x),Sf,(Sf)I∈V且若(S(Sf))(x)=f(-x),則S(S(xf(x)))=-xf(-x).Lemma0.3.(i)S((1+x2)-1)=πe-2πjxj.(ii)S(πe-2πjxj)=(1+x2)-1.Proof.(i)記f(x)=(1+x2)-1.對于x≥0,我們有記CA:={z=u+iv:-A≤u≤A,v=0}u{z=Aeiθ:0≤θ≤π}.注意到當A>1時,i是在CA界定的有界區(qū)域內(nèi)的唯一極點.由回路積分的方法并令A(yù)→∞,我們得到(Sf)(x)=πe-2πx.由于f(x)是偶函數(shù),所以(Sf)(x)也是偶函數(shù).這樣,(Sf)(x)=πe-2πjxj.(ii)記g(x)=πe-2πjxj.直接計算得=π(e2πixu+e-2πixu)e-2πuduLemma0.4.(i)對于任意的k≥0,Sfk形如(Sfk)x=e-2πjxjgk(jxj),其中g(shù)k是個k次多項式.(ii)對于任意的k≥0,S(S(fk))=fk且S(S(xfk+1(x)))=-xfk+1(x).Proof.(i)我們有遞歸公式由引理0.1,得遞歸公式:由此,由歸納法我們導(dǎo)出結(jié)論.(ii)注意到f(x)=-2(k+1)xfk+1(x)且(xfk(x))I=-(1+2k)fk(x)+2(k+1)fk+1(x).由(i)部分的結(jié)論結(jié)合引理0.1,我們知道推論0.2中的假設(shè)對函數(shù)fk(x)和xfk+1(x)(k≥0)成立.這樣,由歸納法可證S(S(fk))=fk(x)且S(S(xfk+1(x)))=-xfk+1(x)(k≥0).回到題目本身.(i)在引理0.3中已經(jīng)證明S((1+x2)-1)=πe-2πjxj.由(5)得S(-2x(1+x2)-2)=-2π2ixe-2πjxj.再由(6)得這樣,S(-2x2(1+x2)-2)=-π(1-2πjxj)e-2πjxj.(ii)首先,當k≥1時,xjfk(x)(0≤j≤2k)都是絕對可積的.這樣,由(6),y=(Sfk)(x)是2k次連續(xù)可微函數(shù).由引理0.1和引理0.4得:xyII+c1yI+c2xy=0等價于輸入fk(x)=(1+x2)-1-k,我們得到c1=-2k且c2=-4π2.8.當某公司推出一個新的社交軟件時,公司的市場部門除了會關(guān)心該軟件的活躍客戶的總?cè)藬?shù)隨時間的變化,也會對客戶群體的一些特征做具體的調(diào)研和分析。我們用n(t,x)表示客戶的數(shù)量密度(以下簡稱密度),這里t表示時間,而x表示客戶對該社交軟件的使用時長,那么在t時刻,對于0<x1<x2,使用時長介于x1和x2之間的客戶數(shù)量為,xx12n(t,x)dx。我們假設(shè),密度n(t,x)隨著時間演化受以下幾個因素的影響:假設(shè)1.當客戶持續(xù)使用該社交軟件時,他的使用時長隨時間線性增長。假設(shè)2.客戶在使用過程中,可能會停止使用,我們假設(shè)停止速率d(x)>0只跟使用時長x有關(guān)。假設(shè)3.新客戶的來源有兩個。O1公司的宣傳:單位時間內(nèi)因此增加的人數(shù)是時間的函數(shù),用c(t)表示。O2老客戶的宣傳:老客戶會主動向自己的同事、朋友等推薦使用該社交軟件,推薦成功的速率跟客戶的使用時長x有關(guān),記作b(x)。假設(shè)如果在某一時刻,記為t=0時,密度函數(shù)是已知的,n(0,x)=n0(x)?？梢酝茖?dǎo)出,n(t,x)的時間演化滿足如下的方程這里N(t)可解讀為新客戶的增加速率。我們假設(shè)b,d∈L,∞),即b(x)和d(x)正且(本質(zhì))有界。以下,我們先做一個簡化假設(shè):c(t)三0,即新客戶的增加只跟老客戶的宣傳有關(guān)。(i)問答題(10分)根據(jù)假設(shè)1和假設(shè)2,形式地推導(dǎo)出(7)中n(t,x)所滿足的偏微分方程,需要在推導(dǎo)過程中指出模型假設(shè)和數(shù)學(xué)表達式之間的對應(yīng)關(guān)系。再根據(jù)假設(shè)3,解釋(7)中N(t)的定義的含義。(ii)問答題(10分)我們想要研究新客戶的增加速率N(t)和推薦成功速率b(x)之間的關(guān)系。為此,請推導(dǎo)出一個N(t)所滿足的方程,且方程中只包含N(t),n0(x),b(x),d(x),而不包含n(t,x)。并證明,N(t)滿足如下估計∞tjn0(x)jdx,(8)∞表示L∞范數(shù)。(iii)證明題(10分)最后,我們想要研究,在充分長的時間之后,數(shù)量密度函數(shù)n(t,x)有什么漸近的趨勢。由于客戶總?cè)藬?shù)可能一直在增加,所以我們不方便直接研究數(shù)量密度函數(shù)n(t,x),而更應(yīng)該去看一個重整化的的密度函數(shù)。為此,我們首先假設(shè)如下的特征值問題有唯一解(λ0,?(x)):并且它的對偶問題也有唯一的解ψ(x):x≥0,然后,我們定義重整化密度R+→R+滿足H(0)=0,我們有并證明ψ(x)n(t,x)dx=eλ0tψ(x)n0(x)dx.為了簡化證明,我們在演算中假定在∞處的邊界項的貢獻都是可以忽略的。R8答案:(i)這個方程推導(dǎo)方式有很多。舉兩個例子。1,特征線法。由于使用時長隨時間線性增長,我們定義特征線x(t),它滿足而順著特征線,根據(jù)停止速率的含義,我們有整理即得(7)式方程。2,微元法?？紤]一個時間微元δt冬1,根據(jù)假設(shè)一和假設(shè)二,我們有n(t+δt,x+δt)=n(t,x)-δtd(x)n(x,t)+o(δt).其中右端第一項表示時間平移的貢獻,第二項表示停止的客戶數(shù)量。兩邊除以δt,再令δt→0,即得此方程。關(guān)于N(t)的定義,只需要說明老客戶推薦的貢獻。對于固定某個使用時長x的老客戶,他們單位時間內(nèi)介紹的新客戶的數(shù)量為b(x)n(t,x)。為了求單位時間內(nèi)所有老客戶介紹的新客戶數(shù)量,需要把所有使用時長的老客戶的貢獻加在一起,故表達為b(y)n(t,y)dy。(ii)根據(jù)題意和N(t)的定義,我們需要先把密度函數(shù)n(t,x)寫成N(t)和其他參數(shù)的表達式,這需要求解此方程。注意到這是一個一階雙曲方程,可以用特征線法求解。將方程改寫為d(y)dy,那么那么,當s≥max(-t,-x)時,我們有eD(∞+s)n(t+s,x+s)=eD(∞)n(t,x),8x≥0,t≥0.(10)特別的,我們可以令x=y,s=-y可得,當t≥y時n(t,y)=N(t-y)e-D(y).再令x=y,s=-t可得,當t≤y時n(t,y)=n0(y-t)eD(y-t)-D(y).為了導(dǎo)出N(t)滿足的方程,我們將它的表達式拆分成兩部分N(t)=b(y)n(t,y)dy=b(y)n(t,y)dy+b(y)n(t,y)dy.根據(jù)特征線可知,右端第一項的特征線起源于x=0,t≥0,而第二項的特征線起源于x≥0,t=0。將n(t,y)的表達式分別代入,我們得到N(t)=b(y)e-D(y)N(t-y)dy+b(y)eD(y-t)-D(y)n0(y-t)dy.(11)整理,即得到N(t)滿足的方程N(t)=b(t-x)e-D(t-x)N(x)dx+b(x+t)eD(x)-D(x+t)n0(x)dx.(12)考慮到d(x)>0所以D是遞增函數(shù),上式中的e-D(t-x),eD(x)-D(x+t)均不大于1。于是,再利用b(x)的有界性,我們可以對N(t)做如下估計∞jn0(x)jdx.最后,利用Gronwall引理,我們就可以得到待證的不等式。(iii)這是一個廣義的相對熵估計的問題。首先我們將方程(7)改寫成重整化密度函數(shù)滿足的方程然后,我們進一步地改寫,整理得到進而有將特征值問題和其對偶問題整合在一起?我們有通過直接計算?我們得到記dμ(x)=b(x)?(x)dx?將上式對x在R+上積分?可得,我們注意到?由定義知?(0)=1?b(x)n(t,x)dx?那么于是可得dx=ψ再由Jensen不等式?我們可得最后?令H(u)=u?即得待證等式"11,2.Ina?ctionalworld,eachresident(viewedasgeometricpoint)isassignetheystayatthevaccinationsiteaftertakingtheshotforobservation.Nowsupposethatdistancedm;nbetweentheResidentNo.mandtheResidentNo.nmusts(m+n)dm;n≥1.Whereweconsiderthedistanceonthecircle,itwopoints.1.Multiple-ChoiceQuestion(4points)Whichofthefollowingiscorrect?BThemaximalnumberofresidentsthatcanbeplacedsimultaneouslyisgreaterthan8,butstill?nite;2.ProofQuestion(6points)GiveaproofofyouranswertoQuestion(i).2R1Answer.TheChoiceCiscorrect.R2Answer.SolutionI.WecanplacetheResidentsNo.1,2,...accordingtothefol-lowingrule.First,putResidentNo.1arbitrarily.Forn>2,ifResidentsNo.1,2,...,n—1For1≤m≤n1,bydm;n≥,weknowthattheResidentNo.ncannotbeplacedinthearcthatiscenteredatResidentNo.m,andofthelength.Thetotal+···+=2ln<2ln2.perimeterofthecircleis·2requirement.ByinductionweconcludethatthecirclecanaccomodateanyquantityofSolutionII.WeconsidertheCartesioncoordinatesystemwhoseoriginisthecen-respectively,orinanequivalentway,wesaythat(theprinciplevaluesof)theirargu-Weprovethefollowingassertionbyinductiothattheirmutualdistancesful?lltherequirement,andnotworesidentsamongthe?rst2k-1occupyadjacentvertices.Theassertionholdsfork=2.Ifitisvalidfork,sothatthe?rst2kresidentsdistancesrelatedtoResidentsNo.2k+1,2k+2,...,WeputResidentsNo.2k+1,2k+2inpositionsnexttoResidentNo.2k-1(i.e.thecorrespondingargumentsdifertothatofResidentNo.2k-1by);putResidentsNo.nexttoResidentNo.2k-1—a+1;···putResidentsNo.2k+1—1,2k+1nexttoResidentNo.1.Asthe?rst2k-1residentsdonotoccupyanyconsecutivepositions,theaboveplace-3cethecircleisnowdividedinto2k+1arcs,erResidentsNo.m(>2k)andn,iftheyareseparatedbyatleasttwopiecesofarcs,threquirement.Thenbyinduction,weconcludethatanynumberofresidentscanbeaccomodatedinthatway.43,4.Twoyearsago,thewinnersof2018AlibabaGlobalMathematicsCompetitioncongruentnon-planarquadrilaterals.Anon-planarn-gonisanon-planar?gureobtainedfromaplanarn-gonbyfoldingitTwonon-planar?guresarecongruentifandonlyifeachcanbeobtainedfromtheotheronebyacertainisometryofR3.ApolyhedronisaboundedregioninR3whoseboundaryistheunionofa?nitecollectionofplanarpolygon3.True-FalseQuestion(4points)Weknowthat2021=43×47.Istherea4.QuestionandAnswer(6points)PleasejustifyyouranswertoQuestion(i)witharigorousargument.5R3,Answer.TheanswerisYES.R4Answer.Allweneedtodoistoconstructanexample.Let’sconsiderastandardT={θ,?:0≤θ,?<2π}.Onecanviewthez-axisastheaxisofsymmetryofthetorus:((R+rcos?)cosθ,(R+rcos?)sinθ,rsin?).Intuitively,whatwedohereistodividethetorusinto43equalparts,thencuteverypartalongthecircle{?=0},keeponesideofthecutwhileslidingtheothersidealongthecircleforcertainangle.Now,wedeformthecircle{?=0}intoaregular43-gonwhoseverticescorresptoθ=(twoofwhichareadjacentverticesofthe43-gon,whiletheothertwoaremidpointsofTakeanother“side”of?Dk,mark21points,e.g.NowwejoinCk;0Ck;1,Ck;0Ak;1,Ck;1Bk;1,Ak;iAk;i+1,Bk;iBk;i+1,Ak;iBk;i,Ak;iBk;i+1(i=1,...,21),andAk;21Dk;0,Bk;21Dk;1,Ak;21Ek,Bk;21Ek,Dk;0Ek,EkDk;1.Wegetanon-planar47-gon.Thusweget43congruent(theconstructionaboveisgons,theycanbegluetogethRemark:Atypicalmistakewouldbetothinkthatthevertices(edges)ofthesenon-planarpolygonsareallvertices(edges,notpartofeadgeductsfrom“eachedgeiscountedtwice”and“2021isadiction”.6part-timechefatAlibabaDamoAcademy.Oneday,XiaoLi,asoftwareengineerattheDAMOAcademy,complainedabouthisrecentworkwithMasterZhang.XiaoLi’sonRn.Inhislatestproject,XiaoLihastodealwithalossfunctionfthatisprovidedtheexplicitde?nitionf,butonlyofersaninterfacetoevaluatefatanygivenx∈Rn.tionoffiscostly.Fortunately,thedimensionnofthisproblemBesides,thegroupthatprovidesthefunctioninformsXiaoLithathemayassumefiswithMasterZhang,XiaoLirealizesthatminimizingfisliketuningamachinewithbytuningeachknobforwardandbackwardwhilemonitorinXiaoLiandMasterZhangproposeaniterativealgorithmforminiAutomatedForward/BackwardTuning(AFBT,Algorithm1).Atiterationk,AFBTorbackwardwithastepsizetk,setsyktotheonerenandcheckswhetherykachievesasu伍cientdecreaseinfanddoublesthestepsize;otherwise,itsetsxk+1=xkandhalvesthestepsize.Inthealgorithm,eidenotesthei-thcanonicalcoordialltheothersare0);1(·)istheindicatorfunction,sothat1[f(xk)—f(yk)≥t]equals1iff(xk)—f(yk)isatleastthesquareoftk,orelsethevalueis0.Algorithm1AutomatedForward/BackwardTuning(AFBT)1:yk:=argmin{f(y):y=xk士tkei,i=1,...,n}#Evaluatelossfunction.2:sk:=1[f(xk)—f(yk)≥t]#Sufficientdecrease?Yes:sk=1;No:sk=0.3:xk+1:=(1—sk)xk+skyk#Updateiterate.4:tk+1:=22sk-1tk#Updatestepsize.sk=1:double;sk=0:halve.7Assumption1.fisconvex.Thismeansthatf((1-Q)x+Qy)≤(1-Q)f(x)+Qf(y)Assumption2.fisdiferentiableonRnand?fisL-LipschitzonRn.Assumption3.fislevel-bounded,meaningthat{x∈Rn|f(x)≤λ}isaboundedBasedonAssumptions1and2,forallx;y∈Rn;Assumptions1and3ensurethatfhasa?niteminimumf*onRn.ProofQuestion(20points)UnderAssumptions1–3,proveforAFBTthat8R5Proof.Assumethatf(xk)。f*.Theninfk≥0[f(xk)?f*]>0since{f(xk)}isnon-increasing,Denotegk=?f(xk).Theninfk≥0ⅡgkⅡ>0(Pickanx*withf(x*)=f*.Thenf(xk)?f*≤〈gk,xk?x*〉bytheconvexityoff;meanwhile,{xk}isboundedduetothemonotonicityof{f(xk)}andthelevel-boundednessoff.Thusinfk≥0ⅡgkⅡ>0).withh=1/√n.Hence(3)wewillhavef(yk)≤f(xk)?t,whichrenderssk=1andhencetk+1=2tk.Itisthen(4)Thussk=1forin?nitelymanyk(otherwise,tk→0),andf(xk)?f(xk+1)≥t2foreachofsuchk,contradictingthelower-boundednessoff.Theproofiscomplete.9etnbeapositiveinteger.Foranypositiveintegerk,write0k=diag{rkthek×kzeromatrix.Letbea(2n+1)×(2n+1)matrix,whereA=(xi,j)1≤i≤n,1≤j≤n+1isann×(n+1)realmatrixandAtdenotesthetransposeofA,thatis,the(n+1)×nmatrixwhose(j,i)-entryisxi,j.(i)ProofQuestion(10points)Acomplexnumberλiscalledaneigenvalueofak×kmatrixXifXv=λvforsomenonzerocolumnvectorv=(x1,...,xk)t.±√λwhereλisanon-negativerealeigenvalueofAAt.(ii)ProofQuestion(15points)Letn=3anda1,a2,a3,a4befourdistinctpositiverealnumbers.Put,whereδi,j={.Showthat:Yhas7distinctR6Proof.(i)WriteIn=diag{,...,}forthen×nidentitymatrix.Byanelementarynreductionthecharacteristicpolynomialdet(λI2n+1—Y)=λdet(λ2In—AAt).Then,0isaneigenvalueofYandeveryothereigenvalueofYisoftheform±√λwhereλisanon-negativerealeigenvalueofAAt.(ii)Putu=(a4,a4,a4)andv=(aa,aa,aa).BycalculationwehaveAAt=diag{a,...,a}+utu—vtv.Letf(s)=det(sIn—AAt)bethecharacteristicpolynomialofAAt.Then,bycalculationa>b1>a>b2>a>b3>a.Then,by(i)Yhas7distinc7.Foracontinuousandabsolutelyintegrablecomplex-valuedfunctionf(x)onR,de?neafunction(Sf)(x)onRby(i)QuestionandAnswer(10points)FindexplicitformsofS()andS().(ii)QuestionandAnswer(15points)Foranyintegerk,writefk(x)=(1+x2)-1-k.Whenk≥1,?ndconstantsc1,c2suchthatthefunctiony=(Sfk)(x)solvesasecondorderdiferentialequationxyII+c1yI+c2xy=0.R7Answer.WriteVforthespaceofcomplex-valued,continuousandabsolutelyintegrablefunctionsonR.Lemma0.1.(i)Iff(x)∈V,fI(x)∈Vandlimx→∞f(x)=0,then(SfI)(x)=-2πix(Sf)(x).(5)(ii)Iff(x)∈Vandxf(x)∈V,then(Sf)I=2πiS(xf(x)).(6)Proof.(i)=-2πix(Sf)(x)=(Sf)(b)-(Sf)(a).Thus,(Sf)I=2πiS(xf(x)).Lemma0.1impliesthefollowingcorollaryimmediately.Corollary0.2.(i)Assumethatf,fI,Sf,x(Sf)(x)∈VandIf(S(Sf))(x)=f(-x),then(S(SfI))(x)=fI(-x).(ii)Assumethatf(x),xf(x),Sf,(Sf)I∈VandIf(S(Sf))(x)=f(-x),thenS(S(xf(x)))=-xf(-x).Lemma0.3.(i)S((1+x2)-1)=πe-2πjxj.(ii)S(πe-2πjxj)=(1+x2)-1.Proof.(i)Writef(x)=(1+x2)-1.Forx≥0,wehavePutCA:={z=u+iv:-A≤u≤A,v=0}u{z=Aeiθ:0≤θ≤π}.Notethat,iistheonlypoleofinsidethedomainboundedbyCAwheneverA>1.UsingthetrickofcontourintegralandlettingA→∞,weget(Sf)(x)=πe-2πx.Sincef(x)isanevenfunction,sois(Sf)(x).Then,(Sf)(x)=πe-2πjxj.(ii)Writeg(x)=πe-2πjxj.Bydirectcalculation(Sg)(x)=π(e2πixu+e-2πixu)e-2πuduLemma0.4.(i)Foranyk≥0,Sfkisoftheform(Sfk)x=e-2πjxjgk(|x|)wheregk(ii)Foranyk≥0,S(S(fk))=fkandS(S(xfk+1(x)))=-xfk+1(x).ByLemma0.1,wegetarecursiverelationforSfk:Then,oneprovestheconclusio(ii)Notethatf(x)=-2(k+1)xfk+1(x)and(xfk(x)),=-(1+2k)fk(x)+2(k+1)fk+1(x).Bytheconclusionofpart(i)andLemma0.1,weseethattheassumptionsinCorollary0.2areallsatis?edforfk(x)andxfk+1(x)(k≥0).Then,oneshowsbyinductionthatS(S(fk))=fk(x)andS(S(xfk+1(x)))=-xfk+1(x)foranyk≥0.Backtotheproblem.(i)ItisshowninLemma0.3thatS((1+x2)-1)=πe-2πjxj.Then,S(-2x(1+x2)-2)=-2π2ixe-2πjxj.S(-2x2(1+x2)-2)=-π(1-2πjxj)e-2πjxj.(ii)Firstly,xjfk(x)(0≤j≤2k)areallabsolutelyintegrablewhenk≥1.Then,by(6),y=(Sfk)(x)isa2k-thordercontinuousdiferentiablefunction.ByLemma0.1andLemma0.4,xy,,+c1y,+c2xy=0isequivalenttoInputtingfk(x)=(1+x2)-1-k,wegetc1=-2kandc2=-4π2.8.Whenanewsocialnetworkingsoftwareappearsonthemarket,theliketoinvestigatehowcertaintraitsofthecustomersevolveovertime.Wedenotethepopulationdensityofthecustomersbyn(t,x),wheretisthetimevariableandxthetimeevolutionofthedensityn(t,x)isgovernedbythefollowingfactors:lengthxincreaseslinearlyintime.Assumption2.Whenacustomerusesthesoftware,heorshemaystopusingitwithastoppingrated(x)>0.Here,Assumption3.Therearetwosourcesofnewcus1.Thesoftwarecompanypromotesthissoftwadenotedbyc(t).2.Theexistingcustomersmayrecommendthissoftwaretotheirfamilyorfriend-s.Theefectiverecommendationrateisdenotedbyb(x),whichisrelatedtoWeassumeatt=0,thepopulationdensityisgiven,n(0,x)=n0(x).Wecanderivethatthetimeevolutionofn(t,x)isgivenbyHere,N(t)isinterpretedastheincreasingrateofthenewb,d∈L(0,∞),thatis,b(x)andd(x)arepositiveand(essentially)bounded.Fromthis(i)QuestionandAnswer(10points)WithAssumption1andAssumption2,formallyderivethepartialdiferentialequationthatn(t,x)satis?esasin(7),andclearlyindicatethecorrespondencebetweenexpressionsduringthederivation.Also,explainthemeaningofN(t)asgivenin(7).(ii)QuestionandAnswer(10points)WeaimtoestablishtheconnectionbetweenN(t)andb(x).Toful?lthistask,deriveanequationthatN(t)satis?es,suchthattheequationonlycontainsN(t),n0(x),b(x)andd(x),butn(t,x)doesnotappearinthisequation.ProvethatN(t)satis?esthefollowingestimate∞tjn0(x)jdx,(8)∞denotestheL∞norm.(iii)ProofQuestion(10points)Finally,weaimtoexplorethelongtimeasymp-toticbehaviorofthepopulationdensityn(t,x).Sincethetotalnumbermi