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

1,2.在一個虛擬的世界中,每個居民(設(shè)想為沒有大小的幾何點依次編號為12···.了抗擊某種疫情,4

的圓周。為了安全，要求第m號居民和第n民之間的距離dm,n

(m+n)dm,n≥,選擇題(4分)下列選項()A這個留觀室最多能容納8個居民B這個留觀室能容納的居民個數(shù)有大千8的上限C)R1答案.選項C符合實際情況R2答案.解法一.我們可以按下述方式安排第12號居民的位置.首先,任意安排第1號居民的位置。對n≥2,若第12n1號居民的位置已經(jīng)被安排好,我們考慮第n號居民不能在哪些位置。對千1≤m≤n1,由dm,n≥1,我們知道,從第m號居民的位置開始,逆時針方向各走,

的距離所形成的長度為

的圓弧內(nèi)部是不可以安排第n民的. +2 +···+ <2(lnn+1+lnn+2+···+ln2n?1)=2ln2n?1<2ln2.n+

n+

2n?

n+

2n? 422因此,這些圓弧的并集的總長度不超過2ln2,而整個圓周長為1·2π=π.熟知π4221.5>2ln2,故這些圓弧不能覆蓋整個圓周,因此第n號居民總可以選擇一個合適的位置使得他與第12n1號居民之間的距離均滿足題目條件.由數(shù)學歸納法可知，解法二 我們以圓周的圓心為原點建立平面直角坐標系，并將第1,2,3,4號居民分444422放在10)(10)(0,1)(01)處,即他們的輻角主值分別為0π,π,3π.444422448居民的距離不小千2·1·π=π>1故此時的4名居民滿足題目條件448我們使用數(shù)學歸納法證明下面命題:對整數(shù)k>2,可以將第122k號居民安置千圓周上一個內(nèi)接正2k邊形的各個頂點處,使得匕們互相之間(在圓周上的)距離滿足題目條件,且編號為122k?1號的居民在圓周上兩兩不相鄰.上述命題對k2成立.若其對k成立，即前2k號居民的位置都已確定.考慮他們將圓周分成的2k段弧.我們要將第2k12k22k+1號居民放置在這些弧的中點.現(xiàn)在來證明可以適當放置使得涉及第2k+12k+22k+1號居民的距離均滿足題目我們將第2k12k2號居民放置在與第2k?1號居民相鄰的位置(即與第2k?1民的輻角差為

距離的位置);將第2k32k4號居民放置在與第2k?11相鄰的位置;···將第2k2a12k2a號居民放置在與第2k?1a1位置;···將第2k+112k+1號居民放置在與第1號居民相鄰的位置由千前2k?1號居民在圓周上兩兩不相鄰,這樣的放置是可行的. π 居民的距離(只需考慮至少一位居民是“新”的情形).因為圓周被分成了2 π 長為

,對千兩位編號分別為m>2和n的居民, 弧,

2(m+ dm,n≥2k+1

2·m+n

>m+n若他們之間的距離恰為一段弧長，設(shè)n∈{2k2a12k2a},則m>2k?1a1,此

3π· (m+n)dm,n≥2k+2

+2a?1+2

?a+1)=2k+2

+a)

>8所以，第122k+1號居民兩兩之間的距離均滿足題目條件.由數(shù)學歸納法知,3,4.2019年第一屆阿里巴巴數(shù)學競賽的優(yōu)勝者們在參加集訓(xùn)營的時候集體送給主辦方負責人的禮物,是一個有60個全等的三角形面的多面體。從圖中我們可以看到,這個多面體的表面是60個全等的空間四邊形拼接而成的。一個空間n邊形是指由一個平面n邊形沿若干條對角線做適當翻折(即在選定的對角線處形成適當?shù)亩娼?后得到的空間圖形。兩個空間圖形全等指的是匕們可以通過R3中的一個等距變換完全重合。一個多面體指的是一個空間有界區(qū)域,其邊界可以判斷題(4分)我們知道2021=4347.那么是否存在一個多面體,由43個全等的空間47邊形拼接而成)R3答案.可以R4答案.我們只需要舉一個例子即可.考慮一個標準的環(huán)面T,T={θ,?:0≤θ,?<我們可以認為這個環(huán)面以z-軸為對稱軸:(θ?)對應(yīng)千空間中的((Rrcos?cosθ(R+rcos?sinθrsin?).對千1≤k≤43,kD={θ,?:2(k?1)π+3k

≤θ π+ 直觀地說,把環(huán)面分成全等的43份之后,每一份沿{?=0}切開,不動另一側(cè)扭轉(zhuǎn)一定角度現(xiàn)在,把{?0這個圓變形成一個正43邊形,各個頂點分別對應(yīng)千θ=2kπ.這樣Dk有四條“邊”(其中兩條位千{?0上四個頂點(兩個位千正43邊形的頂點處,兩個位千邊的中點處,我們還要標記出這兩個中點之間的正43邊形的頂點).記為

=(2(k?1)π,0),2k+

=( 2k+Dk,0=

π,2π),Dk,1=

π,Ek=

2k+π,在?Dk的另一條邊上取21個點, =(2(k?1)π+3?π,

π),i=1,...,

然后繞z-軸旋轉(zhuǎn)2π后得到另21個點,記為Bk,ii=1連結(jié)線段Ck,0Ck,1Ck,0Ak,1Ck,1Bk,1Ak,iAk,i+1Bk,iBk,i+1Ak,iBk,iAk,iBk,i+1(i=121),以及Ak,21Dk,0Bk,21Dk,1Ak,21EkBk,21EkDk,0Ek和EkDk,1.我們得到一個空間47邊形.這樣我們就得到了43個全等的(上述構(gòu)造與k無關(guān)空間47邊形匕們說明:一個典型的錯誤是誤認為這些空間多邊形的頂點(邊)都是多面體的頂點(邊),而根據(jù)“每條邊都算兩次”和“2021是奇數(shù)”得到“矛盾”,由此認為本題的解答是否定的去年，張師傅因為多旋圈面爆紅，今年他來到了達摩院給掃地僧做面。某天，軟件工程師小李跟張師傅吐槽工作。小李主要研究和設(shè)計算法用千調(diào)節(jié)各種產(chǎn)品的參數(shù)。這樣的參數(shù)一般可以通過極小化Rn上的某個損失函數(shù)f求得。在小李最近的一個項目中，這個損失函數(shù)是另外一個課題組提供的；出千安全考慮和技術(shù)原因，該課題組數(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)整算法”(Automatedorard/BakardTuning，AFBT，算法1)。在第k次迭代中，AFBT通過前后調(diào)整xk的單個分量得到2n個點{xk±tkei:i=1n},其中tk為步長；然后，令yk為這些點中函數(shù)值最小的一個，并檢查yk是否使f充分減??；若是，取xk+1=ykk則，令xk+1xk并將步長減半。在算法1中，ei表示Rn中的第i個坐標向量，匕的第i個分量為1,其余皆為0；山(·為指示函數(shù)若f(xkf(yk至少為tk之平方，則山[f(xkf(ykt2]取值為1，否則為0。k1自動前后調(diào)整算法輸入x0Rn,t0>0。對k012,1:ykargmin{f(yyxktkei,i1 k2:sk:=山[f(xk)?f(yk)≥ #是否充分下降?是:sk=1；否:sk=0k?3:xk+1 sk)xk ?4:tk+1:=22sk 更新步長。sk=1步長增倍；sk=0現(xiàn)在，我們對損失函數(shù)f:Rn→R假設(shè)1.f為凸函數(shù)，即對任何xyRn與α[01]f((1?α)x+αy)≤(1?α)f(x)+αf假設(shè)2.f在Rn上可微且?f在Rn上L-Lipschitz假設(shè)3.f的水平集有界，即對任意λR，集合{xRnf(xλ基千假設(shè)1與假設(shè)2 ?f(x),yx〉≤f(yf(x)≤?f(x),yx+2lx對任何xy∈Rn成立；假設(shè)1與假設(shè)3則保證f在Rn上取到有限的最小值f?證明題(20分)在假設(shè)1–3下，對千AFBTlimf(xk)=fR5證明.假設(shè)f(xk)-Af?。因{f(xk)}不增,故fk0k)??]>0。記gk=?f(xk),則infk≥0k0取x使f(x?f?則f之凸性保證gkxkx?f(xkf?；同時，{f(xk)}之單調(diào)性與f之水平集有界性保證{xk?x?}有界。故infk≥0k>0)。換言之，存在ε0使kε對所有k0成立。任給k0,可取ik{1其中κ=1/√n

|gk,eik〉|≥k≥ k±kik} k?k| ik〉 f(y minf te f(x g, 2

t2k≤f(xk)?κεtk+2.k

tk

L+k我們就有f(yk)≤f(xk)?t2,從而sk=1,進而有tk+1=2tkkk0L+ ≥t≡min夕t,κε1>k0L+對所有k≥0成立。故存在無窮個k使得sk=1(否則tk→0);對每一個這樣的k,fk)?(xk+1≥t2。這與f { } 令n為正整數(shù)。對任一正整數(shù)k,記0=diag0,..., { } （ Y （ 為一個(2n1)(2n1)矩陣,其中A=(xi,j)1≤i≤n,1≤j≤n+1是一個n(n1)且At記A的轉(zhuǎn)置矩陣，即(n+1)n的矩陣，(ji)處元素為證明題(10分)稱復(fù)數(shù)λ為kk矩陣X的一個特征值,v=(x1,...,使得Xvλv.證明:0是Y的特征值且Y的其他特征值形如±√λ,實數(shù)λ是AAt證明題(15分)令n=3且a1a2a3a4是4a jaijaii =ai

+a

ji4j (a+aji4j(1≤i≤3,1≤j≤4),其中

1ifi=ff

證明:Y有7 { } R6證明:(i)記I=diag1,...,1 { } ,,det(λI2n+1?Y)=λdet(λ2In?所以,0是Y的特征值且Y的其他特征值形如±√λ,其中λ是AAt的非負實數(shù)特征a2+a2a2+a2(ii)記u=(a4,a4,a4),v=( 4, 4, 4).計算 13AAt=diag{a2,...,a2}+utu?13設(shè)f(sdet(sInAAt為AAt的特征多項式.a2af(a2)

r(a2?

1234i(?i∈{1234}).令alalalal為a1a2a3a4經(jīng)重排后得到的遞減序列.由f(x2)1234i表達式得:AAt有三個互不相等的特征值b2b2b3,其中b1b2b3 a21l>b1>a21

>b2>

>b3>34的正實數(shù).因此,由(i)得Y有7個互不相等的特征值34對千R上的連續(xù)且絕對可積的復(fù)數(shù)值函數(shù)f(x),定義R上的函數(shù)(Sf(Sf)(x(Sf)(x)e2πiuxf問答題(10分)求S(1)和S( )的顯式表達式 問答題(15分)對任意整數(shù) 記fk(x)=(1+ 假設(shè)k≥ 找到數(shù)c1c2使得函數(shù)y=(Sfk)(x)xyll+c1yl+c2xy=R7答案且

1S(1+

)=S( )=π(1+2π|x|)e?2π|x|.(1+ (ii)c1?2k且c2解答記V為R上的復(fù)數(shù)值、連續(xù)、絕對可積的函數(shù)組成的線性空間Lemma (i)若f(x)∈V,fl(x)∈V且limxf(x)=0,(Sfl)(x)=πS (ii)若f(xV且xf(xV,(Sf)l=2πiS(xf .(Sf e2πiuxf=e2πiuxf(u)|+∞e2πie2πiuxf==

(e2πiux)lf=πS(ii)對任意的abR(aa2πiS(xfa +∞= =e2πiuxufaa e2πie2πibuf(u)du==

2πiue2πiuxfaaee2πiauf=(Sf)(b)?(Sf這樣,(Sf)l2πiS(xfCorollary (i)假設(shè)fflSfx(Sf)(xVlimf(x)=若(S(Sf))(x)=f(?x),則(S(Sfl))(x)=f(ii)假設(shè)f(x)xf(x)Sf(Sf)lVlim(Sf)(x)=若(S(Sf))(x)=f(?x),則S(S(xf(x)))=?xfLemma (i)S((1+x2)?1)=(ii)S(πe?2π|x|)=(1+Proof.(i)記f(x(1x2)?1.對千x0,(Sf)(x)

A

?A1+記CA:={z=u+iv:?A≤u≤A,v=0}u{z=Aeiθ:0≤θ≤注意到當A>1時,i是1在CA界定的有界區(qū)域內(nèi)的唯一極點并令A(yù),我們得到(Sf)(xπe?2πx.由千f(x)是偶函數(shù),所以(Sf)(x)函數(shù).這樣,(Sf)(x)=(ii)記g(x)=πe?2π|x|.∞ ==(e2πixu+001

e?2π(1?ix)u=?21

1+

1? 1+x2Lemma (i)對千任意的k≥0,Sfk形如(Sfk)x= 其中g(shù)k個k次多項式(ii)對千任意的k≥0,S(S(fk))=fk且S(S(xfk+1(x)))=?xfk+1(x).Proof.(i)我們有遞歸公式

=

+2(k+

xflk由引理0.1,得遞歸公式k

=

?2(k+

由此由歸納法我們導(dǎo)出結(jié)論k(ii)注意到fl(x?2(k1)xfk+1(x)且(xfk(x))l=?(12k)fk(x2(k1)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)(kk回到題目本身.(i)在引理0.3中已經(jīng)證明S((1x2)?1)=πe?2π|x|.由(5)S(?2x(1+x2)?2)=

S(?2x2(1+x2)?2)=?π(1?2S((1+x2)?2)=π(1+2(ii)首先,當k≥1時 xjfk(x)(0≤j≤ 都是絕對可積的 這樣,由ySfk)(x)是2k次連續(xù)可微函數(shù).由引理0.1和引理0.4得:xyllc1ylc2xy0kk(x2fl+kk

c2kk f=kk1輸入fk(x(1x2)?1?k,我們得到c1?2k且c21當某公司推出一個新的社交軟件時，公司的市場部門除了會關(guān)心該軟件的活躍客戶的總?cè)藬?shù)隨時間的變化，也會對客戶群體的一些特征做具體的調(diào)研和分析。我們用n(t,)表示客戶的數(shù)量密度（以下簡稱密度），這里t表示時間，而x表示客戶對該社交軟件的使用時長，那么在t時刻，對千0<x1<x2，使用時長介千x1和x2之間的客戶數(shù)量為Jx2n(t,x)dx。我們假設(shè)，密度n(t,x)假設(shè)1.假設(shè)2.客戶在使用過程中，可能會停止使用，我們假設(shè)停止速率d(x)>0時長x假設(shè)3.公司的宣傳：單位時間內(nèi)因此增加的人數(shù)是時間的函數(shù)，用c(t)推薦成功的速率跟客戶的使用時長x有關(guān)，記作b(x)假設(shè)如果在某一時刻,記為t=0時，密度函數(shù)是已知的，n(0x)=n0(x)導(dǎo)出，n(t,x)0f?n(t,x)+?n(t,x)+d(x)n(t,x)= t≥00f?n(t,x)+?n(t,x)+d(x)n(t,x)= t≥0,x≥+這里N(t)可解讀為新客戶的增加速率。我們假設(shè)b,d∈L∞(0∞)，即b(x)和d(x)正且(本質(zhì))有界。以下，我們先做一個簡化假設(shè)：c(t)≡0，即新客戶的增加只跟老客戶+問答題(10分根據(jù)假設(shè)1和假設(shè)2，形式地推導(dǎo)出(7)中n(t,x所滿足的?微分設(shè)3，解釋(7)中N(t)的定義的含義。問答題(10分)我們想要研究新客戶的增加速率N(t)和推薦成功速率b(x)之間的關(guān)系。為此，請推導(dǎo)出一個N(t)所滿足的方程，且方程中只包含N(t),n0(x),b(x),d(x)，而不包含n(t,x)。并證明，N(t)滿足如下估計|N(t)|≤∞這里l·l∞表示L∞

∞

|n0(x)| 證明題(10分)最后，我們想要研究，在充分長的時間之后，數(shù)量密度函數(shù)n(t,x)數(shù)量密度函數(shù)n(t,x)，而更應(yīng)該去看一個重整化的的密度函數(shù)。 為此，我們首先假設(shè)如下的特征值問題有唯一解(λ0 ?l(x)+(λ+d(x))?(x)= 0?(x)> ?(0)=J∞b(x)?(x)dx=0f f 0ψl(x)+(λ+d(x))ψ(x)=ψ(0)b(x), ψ(x)≥0, J∞ψ(x)?(x)dx=1.0然后，我們定義重整化密度?(t,x)n(t,x)e?λ0t。證明，對千任意凸函數(shù)H RR+滿足H(0)0 dt

?(t,

dx≤ ?t≥

∞ψ(x)n(t,x)dx=0

∞0∞R8答案:(i)1，特征線法。由千使用時長隨時間線性增長，我們定義特征線x(t)

=

dtn(t,x(t))=?d(x(t))n(t,2,微元法?？紤]一個時間微元δt?1n(t+δt,x+δt)=n(t,x)?δtd(x)n(x,t)+其中右端第一項表示時間平移的貢獻，第二項表示停止的客戶數(shù)量。兩邊除以δt令δt0Jb(y)n(t,關(guān)千N(t)的定義，只需要說明老客戶推薦的貢獻。對千固定某個使用時長x的老客戶，他們單位時間內(nèi)介紹的新客戶的數(shù)量為Jb(y)n(t,為 0根據(jù)題意和N(t)的定義，我們需要先把密度函數(shù)n(t,x)寫成N(t)dn(t+s,x+s)+d(x+s)n(t+s,x+s)=0則如果定義D(x)=Jxd(y)dy0 eD(x+s)n(t+s,x+s)= 那么，當smax(?t,?x)eD(x+s)n(t+s,x+s)=eD(x)n(t, ?x≥0,t≥ 特別的，我們可以令x=y，s=?y可得，當t≥yn(t,y)=N(t?再令xy，s?t可得，當tyn(t,y)=n0(y?為了導(dǎo)出N(t)N(t)

b(y)n(t,y)dy0

b(y)n(t,y)dy0

b(y)n(t,t根據(jù)特征線可知，右端第一項的特征線起源千x=0,t≥0千x≥0t=0。將n(t,y)N(t)

?b(y)e?D(y)N y)dy?0

? ?t整理，即得到N(t)N(t)0b(N(t)0b(t?x)e?D(t?x)N(x)dxb(x+ 0考慮到d(x)>0所以D是遞增函數(shù)，上式中的e?D(t?x),eD(x)?D(x+t)均不大千1千是,再利用b(x)的有界性，我們可以對N(t)|N(t)|≤

0|N(x)|dx+0

0|n0(x)|0 ?(t,?(t,?t

?(t,+?x

=

?H?(t,x)\+

H?(t,x)\=ψ(x)≥ J∞ψ(x)?(x)dx=f?[?(xψ(x)≥ J∞ψ(x)?(x)dx=00?『ψ(x)?(x)H?(t,x)\l

『ψ(x)?(x)H?(t,x)\l?ψ(0)b(x)?(x)H?(t,x) 記dμ(x)=b(x)?(x)dx，將上式對x dt

?(t,

?dx ?0

?(t,

dμ(x)+

?(t, 0我們注意到，由定義知?(0)=1，且n(t,0)=J∞b(x)n(t,x)dx0?(t,

?(t,

∞b(x)?(t,

?(t,

dt

?(t,

∞ 『?dx= 『?0

?(t,

dμ(x)+

?(t, 再由Jensen dt

?(t,

dx≤最后，令H(u)=uAlibabaGlobalMathematicsCompetition-1,2,···.Inordertofightagainstsomeepidemic,theresidentstakesomevaccineandtheystayatthevaccinationsiteaftertakingtheshotforobservation.Nowsuppose4theshapeoftheObservationRoomisacircleofradius1,andonerequiresthatthedistancedm,nbetweentheResidentNo.mandtheResidentNo.nmustsatisfy4(m+n)dm,n≥Whereweconsiderthedistanceonthecircle,i.e.,thelengthoftheminorarcbetweentwopoints.ANomorethan8residentscanbeplacedinsidetheobservationthan8,butstillfinite;R1Answer.TheChoiceCisR2Answer.SolutionI.WecanplacetheResidentsNo.1,2,...accordingtothefol-lowingrule.First,putResidentNo.1arbitrarily.Forn>2,ifResidentsNo.1,2,...,havealreadybeenplaced,weconsiderthepositionswhereResidentNo.ncannotbeFor1≤m≤n?1,bydm,n≥1,weknowthattheResidentNo.ncannotplacedinthearcthatiscenteredatResidentNo.m,andofthelength2.Thelengthofthesearcs2+2+···+ <2(lnn+1+lnn+2+···+ln2n?1)=2ln2n?1<2ln2.n+

n+

2n?

n+

2n? Therefore,thetotallengthoftheunionofthesearcsdoesnotexceed2ln2,while422perimeterofthecircleis1·2π=π.Itiseasytoobservethatπ>1.5>2ln2,422thesearcswouldnotcoverthewholecircle,henceitisalwayspossibletofindaplaceforResidentNo.nsuchthatitsdistancestoResidentsNo.1,2,...,n?1satisfytherequirement.Byinductionweconcludethatthecirclecanaccomodateanyquantity4444SolutionII.WeconsidertheCartesioncoordinatesystemwhoseoriginisthecen-terofthecircle,andplaceResidentsNo.1,2,3and4at(1,0),(?1,0),(0,1),(0,?14444respectively,orinanequivalentway,wesaythat(theprinciplevaluesof)their22mentsare0,π,πand3π.Nowthedistancebetweenanytworesidentsisnoless224482·1·π=π>1,sotheplacementofthese4residentssatisfiesthe448Weprovethefollowingassertionbyinduction:foranyintegerk>2,wecanResidentsNo.1,2,...,2kattheverticesofaregular2k-goninscribedtothecircle,suchthattheirmutualdistancesfulfilltherequirement,andnotworesidentsamongthefirst2k?1occupyadjacentvertices.Theassertionholdsfork=2.Ifitisvalidfork,sothatthefirst2kresidentsareplaced.Theydividethecircleinto2kequalarcs.WeneedtoputResidentsNo.2k+1,2k+2,...,2k+1atthemidpointsofthesearcs.SowejustneedtoprovethedistancesrelatedtoResidentsNo.2k+1,2k+2,...,2k+1satisfytherequirement.WeputResidentsNo.2k+1,2k+2inpositionsnexttoResidentNo.2k?1(i.e.correspondingargumentsdiffertothatofResidentNo.2k?1by

2k+3,2k+4nexttoResidentNo.2k?1?1;···putResidentsNo.2k+2a?1,2k+2anexttoResidentNo.2k?1?a+1;···putResidentsNo.2k+1?1,2k+1nexttoAsthefirst2k?1residentsdonotoccupyanyconsecutivepositions,theaboveplace-mentwouldnotcauseanyproblem.Nowweconsiderdistancebetweentworesidents(onlythecaseswhereatleastoneresidentinthepairis“new”needtobe14Sincethecircleisnowdividedinto2k+1arcs,eachhaslength2π =π14ResidentsNo.m(>2k)andn,iftheyareseparatedbyatleasttwopiecesofarcs, 2(m+ dm,n≥2k+1>2·m+n

>m+nIftheyarejustseparatedbyonepieceofarc,thenforn∈{2k+2a?1,2k+2a},wehavem>2k?1?a+1,hence

3π· (m+n)dm,n≥2k+2

?a+1)=2k+2

+a)

>8Therefore,thedistancesbetweeneachpairofResidentsNo.1,2,...,2k+1satisfiestherequirement.Thenbyinduction,weconcludethatanynumberofresidentscanbeaccomodatedinthatway.3,4.Twoyearsago,thewinnersof2018AlibabaGlobalMathematicsCompetitionmadeapaperpolyhedronasapresenttotheorganizers.Asshowninthephotoes,thepolyhedronhas60equaltriangularfaces,anditssurfacecanalsobedividedinto60congruentnon-planarquadrilaterals.Anon-planarn-gonisanon-planarfigureobtainedfromaplanarn-gonbyfoldingitTwonon-planarfiguresarecongruentifandonlyifeachcanbeobtainedfromtheotheristheunionofafinitecollectionofplanarpolygonsalongcommonedges.True-FalseQuestion(4points)Weknowthat2021=43×47.IsthereQuestionandAnswer(6points)PleasejustifyyouranswertoQuestion(i)witharigorousargument.R4Answer.Allweneedtodoistoconstructanexample.Let’sconsiderastandardtorusT,whosepointscanberepresentedbytwoparameters:T={θ,?:0≤θ,?<Onecanviewthez-axisastheaxisofsymmetryofthe((R+rcos?)cosθ,(R+rcos?)sinθ,rsinFor1≤k≤43,weconsiderthefollowingregiononthekD={θ,?:2(k?1)π+3k

≤θ π+ Intuitively,whatwedohereistodividethetorusinto43equalparts,thencuteverypartalongthecircle{?=,keeponesideofthecutwhileslidingtheothersidealongthecircleforcertainangle.Now,wedeformthecircle{?=0}intoaregular43-gonwhoseverticescorrespondtoθ=2kπ.ThenDkhasfour“sides”of(twoofwhichlieon{?=0),four(twoofwhichareadjacentverticesofthe43-gon,whiletheothertwoaremidpointsoftwosides,weneedthenmarkthevertexofthe43-gonbetweenthesetwomidpoints).Wedenote

=(2(k?1)π,0),2k+

=( 2k+Dk,0=

π,2π),Dk,1=

π,Ek=

2k+π,Takeanother“side”of?Dk,mark21points, =(2(k?1)π+3?π,iπ),i=1,...,

Thenrotatearoundz-axisby2πtogetanother21points,denotethembyBk,i,i=1,...,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,...,andAk,21Dk,0,Bk,21Dk,1,Ak,21Ek,Bk,21Ek,Dk,0Ek,EkDk,1.Wegetanon-planar47-gon.Thusweget43congruent(theconstructionaboveisindependentofk)non-planar47-gons,theycanbegluetogethertoformapolyhedron.Remark:Atypicalmistakewouldbetothinkthatthevertices(edges)ofthesenon-planarpolygonsareallvertices(edges,notpartofeadges)ofthepolyhedron,thend-eductsfrom“eachedgeiscountedtwice”and“2021isanoddnumber”afake“condtra-Lastyear,MasterZhanggotfamouswithhistopologynoodle,andheisnowapart-timechefatAlibabaDamoAcademy.Oneday,XiaoLi,asoftwareengineerattheDAMOAcademy,complainedabouthisrecentworkwithMasterZhang.XiaoLi’susuallybeformulatedasfindingavectorx∈RnthatminimizesacertainlossonRn.Inhislatestproject,XiaoLihastodealwithalossfunctionfthatisbyanothergroup.Forsecurityandtechnicalreasons,theothergroupcannotrevealtheexplicitdefinitionf,butonlyoffersaninterfacetoevaluatefatanygivenx∈Rn.tionoffiscostly.Fortunately,thedimensionnofthisproblemisnothigh(around10).Besides,thegroupthatprovidesthefunctioninformsXiaoLithathemayassumefisXiaoLi’sproblemremindsMasterZhangaboutanantiqueradiothatheowns.Tolistentoaprogramonthisradio,youneedtocarefullytunethefrequencyknobforwardandbackwardwhilemonitoringthequalityofthesounduntilfindingthebestfrequencyforreceivingthesignal.Inthisprocess,nobodyknowsthepreciserelationbetweentheangleoftheknobandthequalityofthesound.AfteracarefuldiscussionwithMasterZhang,XiaoLirealizesthatminimizingfisliketuningamachinewithmultipleknobs:justimaginethateachcomponentofxiscontrolledbyaknob,andf(x)representscertainperformanceofthemachine;oneshouldbeabletofindthebestxbytuningeachknobforwardandbackwardwhilemonitoringthevalueoff.Therefore,XiaoLiandMasterZhangproposeaniterativealgorithmforminimizingf,namedAutomatedForward/BackwardTuning(AFBT,Algorithm1).Atiterationk,considers2npoints{xk±tkei:i=1,...,n}byvaryingeachcomponentofxkorbackwardwithastepsizetk,setsyktotheonerenderingthesmallestvalueoff,andcheckswhetherykachievesasufficientdecreaseinf;ifyes,ittakesxk+1=ykanddoublesthestepsize;otherwise,itsetsxk+1=xkandhalvesthestepsize.Inkalgorithm,eidenotesthei-thcanonicalcoordinatevectorinRn(thei-thentryis1whilealltheothersare0);]_(·)istheindicatorfunction,sothat]_[f(xk)?f(yk)≥t2]equalskiff(xk)?f(yk)isatleastthesquareoftk,orelsethevalueisAlgorithm1AutomatedForward/BackwardTuning(AFBT)Inputx0∈Rnandt0>0.Fork=0,1,2,...,dothe k± 1:y:=argminf(y):y= tei,i=1,... k± k2:sk:=]_f(xk)?f(yk)≥ #Sufficientdecrease?Yes:sk=1;No:sk=k3:xk+1:=(1?sk)xk+ #Update4:tk+1:=22sk #Updatestepsize.sk=1:double;sk=:Nowwemakethefollowingassumptionsonthelossfunctionf:Rn→Assumption1.fisconvex.Thismeansf((1?α)x+αy)≤(1?α)f(x)+αf(y)forallx,y∈Rnandα∈[0,1].Assumption2.fisdifferentiableonRnand?fisL-LipschitzonAssumption3.fislevel-bounded,meaningthat{x∈Rn|f(x)≤λ}isaboundedsetforanygivenλ∈R.BasedonAssumptions1and2,wecanprove ?f(x),y?x)≤f(y)?f(x)≤?f(x),y?x)+2lx?forallx,y∈Rn;Assumptions1and3ensurethatfhasafiniteminimumf?onRn.Formorepropertiesofconvexfunctions,seeanytextbookonconvexanalysis.

f(xk)=fR5Proof.Assumethatf(xk)--f-f?.Thenfk0(xk)?f?]>0since{f(xk)}isnon-increasing,Denotegk=?f(xk).Theninfk≥0k>0(Pickanx?withf(x?)=f?.Thenf(xk)?f?≤gk,xk?x?)bytheconvexityoff;meanwhile,{xk}isboundedduetothemonotonicityof{f(xk)}andthelevel-boundednessoff.Thusinfk≥0k>0).Inotherwords,thereexistsanε>0suchthatk≥εforallk≥0.Givenanyk≥0,wecanpickanik∈{1,...,n}satisfying|gk,eik)|≥k≥ withκ=/√n.i

2f(yk)≤min{f(xk±tkek)}≤f(xk)?tk|gk,ek)|+2

≤f(xk)?κεtk+2.

tk

L+kwewillhavef(yk)≤f(xk)?t2,whichrenderssk=1andhencetk+1=2tk.Itistheneasytoseethat{tk}hasapositivelowerbound,namelykk0L+ ≥t≡min｛t,κε｝> for k≥k0L+Thussk=1forinfinitelymanyk(otherwise,tk→0),andfk)?(xk+1)≥t2foreachofsuchk,contradictingthelower-boundednessoff.Theproofiscomplete.Letnbeapositiveinteger.Foranypositiveintegerk,write0k=g...,0}thek×kzeromatrix.

( Y (

bea(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)-entryxi,jProofQuestion(10points)Acomplexnumberλiscalledaneigenvalueofak×kmatrixXifXv=λvforsomenonzerocolumnvectorv=(x1,...,xk)t.Showthat:0isaneigenvalueofYandeveryothereigenvalueofYisoftheform±√λwhereλisanon-negativerealeigenvalueofIProofQuestion(15points)Letn=3anda1,a2,a3,a4befourdistinctpositiverealnumbers.Iaia aijji =ai

+a

i4j (a+ai4j(1≤i≤3,1≤j≤4),where

1ifi=f0ifi/=f

.Showthat:Yhas7.、'R6Proof.(i)WriteIn=diag{1,...,1}forthen×nidentitymatrix..、'det(λI2n+1?Y)=λdet(λ2In?Then,0isaneigenvalueofYandeveryothereigenvalueofYisoftheform±√λλisanon-negativerealeigenvalueof

(ii)Putu=(a4,a4,a4)andv=

1a4

2a4

3a4).Bycalculationwe13AAt=diag{a2,...,a2}+utu?13Letf(s)=det(sIn?AAt)bethecharacteristicpolynomialofAAt.Then,byf(ai)i(f(ai)i(ai?ajforeachi∈{1,2,3,4}.Letal,al,al,albethedescendingre-orderingofa1,a2,a3,1234Then,weget:AAthasthreedistincteigenvaluesb2,b2,b3whereb1,b2,b3are1234

a21l>b1>a21

>b2>

>b3>al34Then,by(i)Yhas7distinctreal34afunction(Sf)(x)onRby(Sf)(x)

rr

fQuestionandAnswer(10points)FindexplicitformsofS(12)and 122 (1+xQuestionandAnswer(15points)Foranyintegerk,writefk(x)=(1+x2)?1?k.Whenk≥1,findconstantsc1,c2suchthatthefunctiony=(Sfk)(x)solvesasecondorderdifferentialequationxyll+c1yl+c2xy=R7Answer. WriteVforthespaceofcomplex-valued,continuousandabsolutelyintegrablefunctionsonR.Lemma (i)Iff(x)∈V,fl(x)∈Vandlimx→∞f(x)=0,(Sfl)(x)=πS (ii)Iff(x)∈Vandxf(x)∈V,(Sf)l=2πiS(xf Proof.

r(Sfr

f=

f(u)|+∞

r(e2πiux)lfrr=r

f=πS(ii)Foranya,b∈Rwitha<r22πiS(xfaarrbrr a

ufr+∞r(nóng)= (=(

fr r

f(u)du

rr

f=(Sf)(b)?(SfThus,(Sf)l=2πiS(xfCorollary (i)Assumethatf,fl,Sf,x(Sf)(x)∈V

f(x)=If(S(Sf))(x)=f(?x),then(S(Sfl))(x)=f(ii)Assumethatf(x),xf(x),Sf,(Sf)l∈Vlim(Sf)(x)=If(S(Sf))(x)=f(?x),thenS(S(xf(x)))=?xfLemma (i)S((1+x2)?1)=(ii)S(πe?2π|x|)=(1+rr(Sf)(x)

A

?A1+uCA:={z=u+iv:?A≤u≤A,v= {z=Aeiθ:0≤θ≤uNotethat,iistheonlypoleof12insidethedomainboundedbyCAwheneverA>1.UsingthetrickofcontourintegralandlettingA→∞,weget(Sf)(x)=πe?2πx.Sincef(x)isanevenfunction,sois(Sf)(x).Then,(Sf)(x)=πe?2π|x|.(ii)Writeg(x)=πe?2π|x|.Bydirectrr∞ rr

∞= 0

+

1

e?2π(1?ix)u=?21

1+

1? 1+x2Lemma (i)Foranyk≥0,Sfkisoftheform(Sfk)x=e?2π|x|gk(|x|)whereisapolynomialofdegree(ii)Foranyk≥0,S(S(fk))=fkandS(S(xfk+1(x)))=?xfk+1(x).Proof.(i)Wehavearecursiverelation

=

+2(k+

xflkByLemma0.1,wegetarecursiverelationfork

=

?2(k+

k(ii)Notethatfl(x)=?2(k+1)xfk+1(x)and(xfk(x))l=kkkk1Bytheconclusionofpart(i)andLemma0.1,weseethattheassumptionsinCorollaryk0.2areallsatisfiedforfk(x)andxfk+1(x)(k≥0).Then,oneshowsbyinductionS(S(fk))=fk(x)andS(S(xfk+1(x)))=?xfk+1(x)foranyk≥Backtotheproblem.(i)ItisshowninLemma0.3thatS((1+x2)?1)=By(5),weBy(6),weget

S(?2x(1+x2)?2)=π2π|S(?2x2(1+x2)?2)=?π(1?2S((1+x2)?2)=π(1+2(ii)Firstly,xjfk(x)(0≤j≤2k)areallabsolutelyintegrablewhenk≥1.Then,(6),y=(Sfk)(x)isa2k-thordercontinuousdifferentiablefunction.ByLemma0.1andLemma0.4,xyll+c1yl+c2xy=0isequivalenttokk(x2fl+kk

c2kk f=kk1Inputtingfk(x)=(1+x2)?1?k,wegetc1=?2kandc2=1caresabouthowthenumberoftheactivecustomersincreasesintime,andalsowouldliketoinvestigatehowcertaintraitsofthecustomersevolveovertime.Wedenotethepopulationdensityofthecustomersbyn(t,x),wheretisthetimevariableandxrepresentshowlonganactivecustomerhasbeenusingthissoftware.WeassumethatAssumption1.Whenacustomerkeepsusingthesoftware,hisorherusagetimelengthxincreaseslinearlyintime.Assumption2.Whenacustomerusesthesoftware,heorshemaystopusingitwithastoppingrated(x)>0.Here,weassumethestoppingrateonlydependsonx.Therateofchangeinthenumberofcustomersduetotheadvertisementsisdenotedbyc(t).s.Theeffectiverecommendationrateisdenotedbyb(x),whichisrelatedtothecustomer’susagetimelength.Weassumeatt=0,thepopulationdensityisgiven,n(0,x)=n0(x).Wecanderivethatthetimeevolutionofn(t,x)isgivenby0Jf?n(t,x)+?n(t,x)+d(x)n(t,x)= t≥0,x≥N(t):=n(0Jf?n(t,x)+?n(t,x)+d(x)n(t,x)= t≥0,x≥+b,d∈L∞(0,∞),thatis,b(x)andd(x)arepositiveand(essentially)bounded.Fromthispointon,wealsoassumec(t)≡0forsimplicityofanalysis.+formallyderivethepartialdifferentialequationthatn(t,x)satisfiesasin(7),andexpressionsduringthederivation.Also,explainthemeaningofN(t)asgiveninN(t)andb(x).Tofulfilthistask,deriveanequationthatN(t)satisfies,suchthattheequationonlycontainsN(t),n0(x),b(x)andd(x),butn(t,x)doesnotappearinthisequation.ProvethatN(t)satisfiesthefollowingestimate|N(t)|≤∞

r∞r(nóng)0

|n0(x)| wherel·l∞denotestheL∞ProofQuestion(10points)Finally,weaimtoexplorethelongtimeasymp-toticbehaviorofthepopulationdensityn(t,x).Sincethetotalnumbermightbeincreasing,itismoreconvenienttoworkwithanormalizeddensityfunction. ?l(x)+(λ+d(x))?(x)= 0?(x)> ?(0)=J∞b(x)?(x)dx=0ψ(x)≥∞ψ(x)?(x)dx=ψ(x)≥∞ψ(x)?(x)dx=00Wedefinethenormalizeddensity?(t,x):=n(t,x)e?λ0t.Provethatforanyr H:R+→R+withH(0)=0,wer rλtrλt

dt