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

1球狀閃電作為一名秘密任務(wù)的長官,你和首席科學(xué)家大寶有如下的談話?？茖W(xué)家:“長官,我們已經(jīng)掌握了球狀閃電的控制規(guī)律,我們發(fā)現(xiàn)實驗室中的球狀閃電半徑的變化率v(t)滿足如下的方程。v=ar+r3-r5.這里r(t)表示球狀閃電的半徑,而t是時間變量。初始時刻,沒有球狀閃電,即r(0)=0。相應(yīng)地,我們也有v(0)=0。而a∈R可以被人為控制,您可以通過拉動一個控制桿來迅速的改變a的值。我們給它的預(yù)設(shè)值是a=-1?！蹦?“做的漂亮,博士!a是我們的唯一控制方式嗎?這似乎并不能把球狀閃電啟動起來?！笨茖W(xué)家:“您說的對,長官。我們的確有另一個控制方式,就是踢一下儀器。”你:“博士,您沒開玩笑吧?踢一下?”科學(xué)家:“沒錯,如果踢一下的話,r(t)的值就會瞬間提高ε(ε遠(yuǎn)小于1)。”你:“明白了,這的確有幫助。我們今天的測試目標(biāo)是啟動球狀閃電,讓它的半徑嚴(yán)格超過√2,再讓它逐漸完全消失?！笨茖W(xué)家:“是的,長官。我們?yōu)榇嗽O(shè)計了四個控制方案。請問長官您覺得這些方案如何?”你看了一下這些選項,發(fā)現(xiàn)其中可行的方案有()。A設(shè)置a=2,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置a=-B設(shè)置a=3,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置a=-C設(shè)置a=4,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置a=-D設(shè)置a=5,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置2設(shè)兩個凸八面體O1;O2的每個面都是三角形,且O1在O2的內(nèi)部.記O1(O2)的棱長之和為l1(l2).當(dāng)我們計算l1/l2時,可能得到以下哪個(些)值?(多選題)143A與B二人進(jìn)行“抽鬼牌”游戲。游戲開始時,A手中有n張兩兩不同的牌。B手上有n+1張牌,其中n張牌與A手中的牌相同,另一張為“鬼牌”,與其他所有牌都不同。游戲規(guī)則為:i)雙方交替從對方手中抽取一張牌,A先從B手中抽取。ii)若某位玩家抽到對方的牌與自己手中的某張牌一致,則將兩張牌丟棄。iii)最后剩一張牌(鬼牌)時,持有鬼牌的玩家為輸家。假設(shè)每一次抽牌從對方手上抽到任一張牌的概率都相同,請問下列n中哪個n使A的勝率最大?n=31n=32n=999對所有的n,A的勝率都一樣4某個城市有10條東西向的公路和10條南北向的公路?共交于100個路口.小明從某個路口駕車出發(fā)?經(jīng)過每個路口恰一次?最后回到出發(fā)點.在經(jīng)過每個路口時?向右轉(zhuǎn)不需要等待?直行需要等待1分鐘?向左轉(zhuǎn)需要等待2分鐘.設(shè)小明在路口等待總時間的最小可能值是S分鐘?則S<50;50≤S<90;90≤S<100;100≤S<150;5設(shè)n≥2是給定正整數(shù).考慮n×n矩陣X=(ai;j)1≤i;j≤n(ai;j=0或者1)的集合.(1)證明:存在這樣的X滿足detX=n—1.(3)若n≥2023,證明存在X.6對實數(shù)r,用||r||表示r和最近的整數(shù)的距離:||r||=min{|r-n|:n∈Z}.1.試問是否存在非零實數(shù)s,滿足limn→∞||ns||=0?2.試問是否存在非零實數(shù)s,滿足limn→∞||ns||=0?7某公司要招聘一名員工,有N人報名面試。假設(shè)N位報名者所具有該職位相關(guān)的能力值兩兩不同,且招聘委員會能觀察到的能力值排名與其真實能力值排名吻合。委員會決定采取如下招聘程序:1.招聘委員會按隨機(jī)順序逐個面試候選人,且他們能觀察到當(dāng)時所見候選人的相對排名。比如委員會面試到第m位候選人時,他們擁有的信息是前m位面試者的相對排名,但不知后N-m位候選人的能力情況。2.每面試完一位候選人,委員會需當(dāng)即決定是否給他/她發(fā)工作ofer。3.如果委員會決定給某位候選者發(fā)ofer,那么這位候選者以概率p接受,以概率1-p拒絕,且獨立于(之前)所有其他面試者的決定。如果該候選人接受ofer,那么委員會將不再繼續(xù)面試接下去的候選人。如果該候選人拒絕ofer,那么委員會將繼續(xù)面試下一4.如果委員會決定不給某位面試者發(fā)ofer,那么他們將繼續(xù)面試下一位候選人,且不能再回頭去找前面已經(jīng)面試過的人。5.反復(fù)該面試程序,直到有候選者接受ofer。如果沒有候選者接收該工作,那么委員會面試完所有的N位候選者。由于N位面試者的順序是完全隨機(jī)的,因此他們能力的排名在N!的可能性中是均勻分布。且委員會所具有的全部信息是當(dāng)前面試過的候選人的相對排名。委員會的任務(wù)是,在遵守如上程序的前提下,找到一個策略,使得招到N位候選者中能力最優(yōu)者的概率最大化。問題如下:(a)考慮如下策略。委員會先面試前m-1位候選者,不管其能力排名如何,都不發(fā)工作ofer。從第m位開始,一旦看到能力在所面試過候選人中的最優(yōu)者,即發(fā)工作ofer。如對方拒絕,則繼續(xù)面試直到下一位當(dāng)前最優(yōu)者1出現(xiàn)。試證明:對于任意的N,都存在一個m=mN,使得依靠上述策略找到(所有N位候選人中)最優(yōu)者的概率值,在所有可能的策略所給出的概率值中是最大的。(b)假設(shè)p=1。當(dāng)N→+∞,求的極限。(c)對一般的p∈(0,1),當(dāng)N→+∞,求的極限。1“當(dāng)前最優(yōu)者”指當(dāng)前被面試者在所有被面試過的人(包括被發(fā)ofer并婉拒的人)中的最優(yōu)者。1第1題球狀閃電作為一名秘密任務(wù)的長官,你和首席科學(xué)家大寶有如下的談話?？茖W(xué)家:“長官,我們已經(jīng)掌握了球狀閃電的控制規(guī)律,我們發(fā)現(xiàn)實驗室中的球狀閃電半徑的變化率v(t)滿足如下的方程。v=ar+r3-r5.這里r(t)表示球狀閃電的半徑,而t是時間變量。初始時刻,沒有球狀閃電,即r(0)=0。相應(yīng)地,我們也有v(0)=0。而a∈R可以被人為控制,您可以通過拉動一個控制桿來迅速的改變a的值。我們給它的預(yù)設(shè)值是a=-1?！蹦?“做的漂亮,博士!a是我們的唯一控制方式嗎?這似乎并不能把球狀閃電啟動起來?！笨茖W(xué)家:“您說的對,長官。我們的確有另一個控制方式,就是踢一下儀器。”你:“博士,您沒開玩笑吧?踢一下?”科學(xué)家:“沒錯,如果踢一下的話,r(t)的值就會瞬間提高ε(ε遠(yuǎn)小于1)?！蹦?“明白了,這的確有幫助。我們今天的測試目標(biāo)是啟動球狀閃電,讓它的半徑嚴(yán)格超過√2,再讓它逐漸完全消失。”科學(xué)家:“是的,長官。我們?yōu)榇嗽O(shè)計了四個控制方案。請問長官您覺得這些方案如何?”你看了一下這些選項,發(fā)現(xiàn)其中可行的方案有()。(A).設(shè)置a=2,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置(B).設(shè)置a=3,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置a=-(C).設(shè)置a=4,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置a=-(D).設(shè)置a=5,踢一下儀器,等球狀閃電半徑嚴(yán)格超過√2,再設(shè)置1答案選(B)。我們記變化率方程為v=f(r;a).如果v>0則r隨時間增長;如果v<0則r隨時間下降;如果v=0則r保持不變。2我們首先注意到f(0,a)=0,即r=0永遠(yuǎn)是一個根。但是變化率函數(shù)的非負(fù)實根數(shù)量受a的取值影響。事實上,我們可以算出來f(r,a)=0的所有的根:r1=0,r2=-,r3=下面我們分類討論,當(dāng)a>0的時候,我們有兩個非負(fù)實根r1=0和r5>0。我們?nèi)菀昨炞C,當(dāng)r∈(0,r5)時v>0,但r∈(r5,+∞)時v<0。于是當(dāng)a>0的時候,如果我們踢一下機(jī)器,就能啟動球狀閃電,閃電的半徑逐漸增大到r5,但不會超過r5。為了使得半徑嚴(yán)格超過√2,我們需要令r5>√所以啟動時,我們需要令a>2。這樣排除了選項(A)。當(dāng)-0的時候,我們有三個非負(fù)實根,從小到大依次是r1=0,r3>0和r5>0。特別地,r5<1且當(dāng)r∈(r5,+∞)時,v<0半徑縮小。如果此刻r=√2,半徑會逐步縮小直到r=r5,但不會小于r5。所以此時,球狀閃電不能完全消失。這樣,排除了選項(D)。當(dāng)a=-時,我們有兩個非負(fù)實根r1=0和r5=類似上述情況,如果此刻半徑會逐步縮小直到r=r5,但不會小于r5。所以此時,球狀閃電不能完全消失。這樣,排除了選項(C)。當(dāng)a<-時,我們只有一個非負(fù)實根r1=0,且當(dāng)r>0時,v<0。所以球狀閃電會逐漸完全消失。選項(B)的確是合理的選項。3第2題設(shè)兩個凸八面體O1,O2的每個面都是三角形,且O1在O2的內(nèi)部.記O1(O2)的棱長之和為l1(l2).當(dāng)我們計算l1/l2時,可能得到以下哪個(些)值?(多選題)(A).0.64(B).1(E).42答案選(A)(B)(C)(D)。說明:在60-70年代全蘇中學(xué)生數(shù)學(xué)奧林匹克中,有過這樣一個題:“四面體V1位于四面體V2內(nèi)部,證明V1的棱長之和小于V2的棱長之和的倍”.這里反直覺的地方在于,如果是二維平面上一個三角形位于另一個三角形內(nèi)部,那么小三角形不僅面積是嚴(yán)格小于大三角形的,周長也是如此.而在三維情形,雖然體積和表面積的大小關(guān)系是保持的,但棱長之和的大小關(guān)系會被破壞.這道題的“出處”應(yīng)該是兩個波蘭數(shù)學(xué)家于1962年發(fā)表的:atyczne6(1962),14-16.這文章用波蘭語寫的,自然沒有什么人知道,然后1977年他們出了一個英文版Holszty/nski,W.andKuperberg,W.,OnaPropertyofTetrahedra,AlabamaJ.Math到了1986年,Alabama大學(xué)的CarlLinderholm把這個結(jié)果推廣到了高維歐氏空間中的單形:定理:對于Rn中的兩個m維單形S和T(前者完全位于后者的內(nèi)部),和任意正整數(shù)1≤r≤m.存在常數(shù)Bm,r,使得S的所有r維面的面積之和不超過T的所有r維面的面積之和的Bm,r倍.這里Bm,r的具體數(shù)值計算如下:設(shè)m+1=(r+1)q+s(帶余除法),則(CARLLINDERHOLM,ANINEQUALITYFORSIMPLICES,GeometriaeDedicata(1986)回到本題,這里的選項(A)是平凡的,關(guān)鍵是要說明:?為什么(B)、(C)和(D)可以實現(xiàn)??為什么(E)不能實現(xiàn)?這里需要的數(shù)學(xué)知識大致有:4(A)一些幾何拓?fù)?每個面都是三角形的凸八面體,共有3×8/2=12條棱,于是由Euler公式,頂點數(shù)為6.(B)一點點圖論:如果有一個頂點引出5條棱,那么簡單討論可知必有另一個頂點也引出5條棱,這個八面體的各頂點度數(shù)為(5,5,4,4,3,3).除此之外,唯一可能的情形就是每個頂點都引出4條棱(如正八面體).(C)一點點凸幾何知識:因為我們考慮的都是凸八面體,所以八面體的任意兩點之間距離的最大值必定在某兩個頂點之間實現(xiàn).?如果大八面體的每個頂點都引出4條棱,且最大距離l在兩個不相鄰頂點A和B之間實現(xiàn),那么因為另四個頂點與這兩個頂點均相鄰,所以大八面體的棱長之和至少是4l(且在另四個頂點到直線AB的距離充分小的時候可以充分接近),而對于小八面體來說,假設(shè)也是每個頂點引出4條棱,讓三個頂點趨近于A,另三個趨近于B,其棱長之和會趨近于6l.這樣所有小于1.5的比例均可實現(xiàn).(所以有選手會選(A),(B),(C))?如果大八面體的兩點間最大距離是在兩個度數(shù)為3的頂點之間實現(xiàn)的,那么大八面體的棱長之和至少是3l(且在另四個頂點到直線AB的距離充分小的時候可以充分接近),而對于小八面體來說,仍假設(shè)每個頂點引出4條棱,讓三個頂點趨近于A,另三個趨近于B,其棱長之和會趨近于6l.這樣所有小于2的比例均可實現(xiàn).而如果此時小八面體與大八面體的拓?fù)浣Y(jié)構(gòu)相同,且兩個度數(shù)為5的頂點非常接近,與此同時另4個頂點非常接近,那么比例上限可提高到8/3.?作簡單的分類討論可知,如果大八面體的兩頂點間最大距離l2是在一個度數(shù)為a的頂點和一個度數(shù)為b的頂點之間實現(xiàn)的(不管它們是否相鄰),那么大八面體的各棱長度之和大于min(a,b)l,而小八面體的棱長之和顯然不超過12l,所以(E)是不可能實現(xiàn)的.5第3題A與B二人進(jìn)行“抽鬼牌”游戲。游戲開始時,A手中有n張兩兩不同的牌。B手上有n+1張牌,其中n張牌與A手中的牌相同,另一張為“鬼牌”,與其他所有牌都不同。游戲規(guī)則為:i)雙方交替從對方手中抽取一張牌,A先從B手中抽取。ii)若某位玩家抽到對方的牌與自己手中的某張牌一致,則將兩張牌丟棄。iii)最后剩一張牌(鬼牌)時,持有鬼牌的玩家為輸家。假設(shè)每一次抽牌從對方手上抽到任一張牌的概率都相同,請問下列n中哪個n使A的勝率最大?(A).n=31(B).n=32(C).n=999(D).n=1000(E).對所有的n,A的勝率都一樣3答案選(B)。記初始A手上n張牌時A的勝率為an,則(1)故有而(2)故有我們可以得到遞推公式其中右端第一項為A未抽中鬼牌的情況,這時B無論抽中什么都能成功配對(鬼牌在B手上),這時A手上有n-2張牌,B手上有n-1張牌且A先手。右端第二項為A,B均抽中對方手上的鬼牌的情況,右端第三項為A抽中B手上的鬼牌而B沒抽中A手上的鬼牌的情況,而pn,n-1為A先手,手上有包含鬼牌的n張牌,B手上有不包含鬼牌的n-1張牌時A的勝率。我們有pn,n-1=1-an-2;(4)這是因為A無論抽到哪一張均能配對,此時變?yōu)锳手上有包含鬼牌的n-1張牌,B手上有不包含鬼牌的n-2張牌且為B先手,故此時B的勝率為an-2而A的勝率為1-an-2。6進(jìn)而可得=...若n為奇數(shù)?由遞推可得(7)若n為偶數(shù)?由遞推可得(8)?a31=?a32=答案為(B)?即A初始手上有32張牌時A的勝率最大"7第4題某個城市有10條東西向的公路和10條南北向的公路,共交于100個路口.小明從某個路口駕車出發(fā),經(jīng)過每個路口恰一次,最后回到出發(fā)點.在經(jīng)過每個路口時,向右轉(zhuǎn)不需要等待,直行需要等待1分鐘,向左轉(zhuǎn)需要等待2分鐘.設(shè)小明在路口等待總時間的最小可能值是S分鐘,則(A).S<50;(B).50≤S<90;(C).90≤S<100;(D).100≤S<150;4答案選(C)。由題意知小明行駛的路線是一條不自交的閉折線.將每個路口看作一個頂點,那么他行駛的路線可以看成是一個100邊形(有的內(nèi)角可能是平角,也有大于平角的內(nèi)角).由多邊形內(nèi)角和公式知這個100邊形的所有內(nèi)角之和為98×180。.注意內(nèi)角只能是90。,180。和270。,果小明在這條路上是順時針行駛的,那么90。內(nèi)角對應(yīng)右轉(zhuǎn),180。內(nèi)角對應(yīng)直行,270。內(nèi)角對應(yīng)左轉(zhuǎn),他在路口等待的總時間是(100—a—b)+2b=100—(a—b)=96(min);如果小明在這條路上是逆時針行駛的,那么90。內(nèi)角對應(yīng)左轉(zhuǎn),180。內(nèi)角對應(yīng)直行,270。內(nèi)角對應(yīng)右轉(zhuǎn),他在路口等待的總時間是(100—a—b)+2a=100+(a—b)=104(min).因此,S=96,選項(C)正確.注:如果小明的起點/終點處的轉(zhuǎn)彎時間不計,那么等待的總時間還可以減少2分鐘(選擇一個左轉(zhuǎn)的位置作為起點),這樣S=94,但不影響選擇的選項.8第5題設(shè)n≥2是給定正整數(shù).考慮n×n矩陣X=(ai,j)1≤i,j≤n(ai,j=0或者1)的集合.(1)證明:存在這樣的X滿足detX=n?1.(2)若2≤n≤4,證明detX≤n?1.(3)若n≥2023,證明存在X.5答案(1)若X有一行全為0或者有兩行相等,則detX=0;若X有一行只有一個1,則可約化到(n?1)階矩陣的情形;若X有一行全為1,還有一行有n?1個1,則可約化到有一行只有一個1的情形,進(jìn)一步約化到(n?1)階矩陣的情形.若以上都不發(fā)生,則X的各行有很少的可能性,我們可以逐個討論.(2)取XI=(ai,j)1≤i,j≤n,其中ai,j=1?δi,j,1≤i,j≤n.則detXI=(?1)n—1(n?1).若n是奇數(shù),令X=XI.若n是偶數(shù),令X為調(diào)換XI的最后兩行所得矩陣.則detX=n?1.(3)當(dāng)n=2k?1時,令則Y是元素為±1的(n+1)×(n+1)矩陣,且注意Y的最后一行為αn+1=(,...,).記ti=±1為Y的第i行的最后一個元素(1≤i≤n).令n+1去掉β的最后一個元素(其等于0),得到一個n行向量βi.令XI=(β1,...,βn)t.記則XI是元素為0,1的n×n矩陣,且detXI=t2(k—2)2k-1+1.9若有必要,則調(diào)換X/的最后兩行,可以得到一個元素為0,1的n×n矩陣,滿足detX=2(k—2)2k-1+1.不妨設(shè)2k?1≤n<2k+1?1.當(dāng)2k?1≤n<3·2k—1且n≥21的n×n矩陣X,滿足detX≥2(k—2)2k-1+1>2(k—2)2k-1.另一方面,<(2k+1)3·2k-3=23(k+1)·2k-3.X>n4.這樣X>n4.當(dāng)3·2k—1≤n<2k+1?1且n≥2023時,則k≥10.存在元素為0,1的n×n矩陣X,滿足detX≥2(k—2)2k-1+12(k—3)·2k-2+1>2(3k—7)2k-2.另一方面,<(2k+1)2k-1=2(k+1)·2k-1..第6題對實數(shù)r,用||r||表示r和最近的整數(shù)的距離:||r||=min{|r-n|:n∈Z}.1.試問是否存在非零實數(shù)s,滿足limn→∞||ns||=0?2.試問是否存在非零實數(shù)s,滿足limn→∞||ns||=0?6答案1.存在,取s=1即可。設(shè)n=xn+√yn,則n=xn-√從而n.由此|xn+√yn-2xn|=|√yn-xn|=2.不存在。反證法,假設(shè)s滿足ns=mn+∈n,其中l(wèi)imn→∞∈n=0.記α=√考慮冪級數(shù)(1-αx)(1-αx)=1-6x+7x2,上式兩邊乘以1-6x+7x2可得設(shè)(1-6x+7x2n=,(1-6x+7x2n=n,則pn∈Z,limn→∞ηn=0.因為(9)左邊是一次式,從而右邊滿足pn+ηn=0,n≥2.n充分大時ηn很小,所以必有pn=ηn=0,即(9)右邊兩項均為多項式。因此右邊寫成部分分式形如.因為limn→∞∈n=0,所以左邊的收斂半徑至少為1,而α,α均大于1,所以必須A=B=0.這樣當(dāng)n充分大時,∈n=0,從而mn∈Z,矛盾!第7題某公司要招聘一名員工,有N人報名面試。假設(shè)N位報名者所具有該職位相關(guān)的能力值兩兩不同,且招聘委員會能觀察到的能力值排名與其真實能力值排名吻合。委員會決定采取如下招聘程序:1.招聘委員會按隨機(jī)順序逐個面試候選人,且他們能觀察到當(dāng)時所見候選人的相對排名。比如委員會面試到第m位候選人時,他們擁有的信息是前m位面試者的相對排名,但不知后N—m位候選人的能力情況。2.每面試完一位候選人,委員會需當(dāng)即決定是否給他/她發(fā)工作ofer。3.如果委員會決定給某位候選者發(fā)ofer,那么這位候選者以概率p接受,以概率1—p拒絕,且獨立于(之前)所有其他面試者的決定。如果該候選人接受ofer,那么委員會將不再繼續(xù)面試接下去的候選人。如果該候選人拒絕ofer,那么委員會將繼續(xù)面試下一4.如果委員會決定不給某位面試者發(fā)ofer,那么他們將繼續(xù)面試下一位候選人,且不能再回頭去找前面已經(jīng)面試過的人。5.反復(fù)該面試程序,直到有候選者接受ofer。如果沒有候選者接收該工作,那么委員會面試完所有的N位候選者。由于N位面試者的順序是完全隨機(jī)的,因此他們能力的排名在N!的可能性中是均勻分布。且委員會所具有的全部信息是當(dāng)前面試過的候選人的相對排名。委員會的任務(wù)是,在遵守如上程序的前提下,找到一個策略,使得招到N位候選者中能力最優(yōu)者的概率最大化。問題如下:(a)考慮如下策略。委員會先面試前m—1位候選者,不管其能力排名如何,都不發(fā)工作ofer。從第m位開始,一旦看到能力在所面試過候選人中的最優(yōu)者,即發(fā)工作ofer。如對方拒絕,則繼續(xù)面試直到下一位當(dāng)前最優(yōu)者1出現(xiàn)。試證明:對于任意的N,都存在一個m=mN,使得依靠上述策略找到(所有N位候選人中)最優(yōu)者的概率值,在所有可能的策略所給出的概率值中是最大的。(b)假設(shè)p=1。當(dāng)N→+∞,求的極限。(c)對一般的p∈(0,1),當(dāng)N→+∞,求的極限。7答案對于任意的1≤k≤N,我們令Zk為委員會完全略過前k—1位面試者,而從第k位開始采取最優(yōu)策略的最終所得,即N位候選者中能力最高者接受該工作的概率。則我們有Zk≥Zk+1.(a)如果委員會面試了第k位候選人,且其能力在前k位被面試者中居首,那么委員會發(fā)出ofer。在這個事件下,委員會最終找到能力值最高者的條件概率為1“當(dāng)前最優(yōu)者”指當(dāng)前被面試者在所有被面試過的人(包括被發(fā)ofer并婉拒的人)中的最優(yōu)者。由此可知,委員會向第k位面試者發(fā)出ofer,當(dāng)且僅當(dāng)其在前k位中的能力值最高,且Zk+1≥Zk+1,(10)即≥Zk+12.遞增,而{Zk}k遞減,且Zk≤,易見不等式(10)必定對某一個k≥N—1成立。由此可知,最優(yōu)策略可以通過選擇某個m來達(dá)到,也即滿足不等式(10)的k中的最小值。此外,如果k=m滿足不等式(10),則任意的k≥m也滿足。因此,對于第m位之后的“當(dāng)前最優(yōu)者”,也應(yīng)當(dāng)發(fā)放ofer。(b)令pm為委員會采取(a)中的策略,且找到能力最高者的概率。當(dāng)p=1時,被發(fā)ofer的候選者一定會接受,所以這時選中能力最高者對應(yīng)的是事件的不相交并集,其中Ak對應(yīng)的事件為第k位候選人是N位中的能力最高者,且被面試了。這樣的話,事件Ak的概率為其中對應(yīng)的是這位候選者是能力最高者的概率,是他/她被面試到的概率,即前k1位中的相對能力最高者在前m1位中。這樣,我們就有易見pm先曾后減,因此其最優(yōu)值m*=mN應(yīng)為滿足pm≥pm+1的最小的m,即滿足的最小m。當(dāng)N很大時,由左端的近似逼近為可知,→(c)對一般的于p∈(0,1),同樣的,pm的值為下列不相交事件并的概率:其中Ak對應(yīng)的事件為第k位候選人是N人中的能力最高者、被面試了、并且接受了ofer.我們有2如果這個不等式不滿足,則略過第k個人,且從第k+1位開始采取最優(yōu)策略,則得到最佳求職者的概率將更大。其中qk為假定第k位候選人為N人中能力最高者后,他/她被面試的條件概率。則我們有其中Γ為經(jīng)典的Γ函數(shù)。據(jù)此,我們得到如果從第m位開始,委員會找到(所有N位候選人中)能力值最高者的概率為pm對于m先增后減。由Γ函數(shù)的近似及積分對求和的逼近,我們計算得,當(dāng)N非常大時,讓pm最大化的mN的值滿足當(dāng)p=1時,極限為1/e.1Balllighteningscientist.Scientist:”Chief,wv=ar+r3-r5.Herer(t)representstheradiusofballlightning,andtisthetimevariable.Attheinitialmoment,thereisnoballlightning,thatis,r(0)=0.Accordingly,wealsohavev(0)=0.controllever.Wesetitspresetvaluetoa=-1.”You:”Welldone,Doctor!Isaouronlywaytheballlightning.”Scientist:”You’reright,Chief.Wedohaveanotherwayofcontrol,whichistokicktheinstrument.”You:”Doctor,areyoukiddingme?Kickit?”Scientist:”Yes,ifyoukickit,thevalueofr(t)willinstantlyincreasebyε(εismuchsmallerthan1).”You:”Isee.That’shelpfulindeed.Ourtestgoaltodayistostarttheballlightning,makeitsradiusstrictlyexceed√2,andthenletitgraduallydisappearcompletely.”Scientist:”Yes,Chief.WWhatdoyouthinkoftheseschemes,Chief?”Seta=2,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,Seta=3,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,Seta=4,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,thenseta=-Seta=5,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,thenseta=-.2thesumofedgekengthsofO1(resp.O2)bel1(resp.l2).Whenwecalculatel1/l2,whichvalue(s)amongthefollowingcanbeobtained?(MultipleChoice)143Twoplayers,AandB,playagamecalled“drawthejokercard”.Inthebeginning,PlayerAhasndiferentcardsPlayerBhasn+1cards,nofwhicharethesamewiththencardsinPlayerA’shand,andtherestoneisaJoker(diferentfromallotherncards).Therulesarei)PlayerA?rstdrawsacardfromPlayerB,andthenPlayerBdrawsacardfromPlayerA,andthenthetwoplayerstaketurnstodrawacardfromtheotherplayer.ii)ifthecardthatoneplayerdrewfromtheotheronecoincideswithoneofthecardsonhis/herownhand,thenthisplayerwillneedtotakeoutthesetwoidenticalcardsanddiscardthem.iii)whenthereisonlyonecardleft(necessarilytheJoker),theplayerwhoholdsthatcardAssumeforeachdraw,theprobabilityofdrawinganyofthecardsfromtheotherplayeristhesame.WhichninthefollowingmaximisesPlayerA’schanceofwinningthn=31n=32n=9994theoriginalcrossing.Ateverycrossing,thereisnowaittoturnright,1minutewaittogostraight,and2minuteswaittoturnleft.LetSbetheminimumnumberoftotalminutesonwaitingatthecrossings,then5Letn≥2beagivenpositiveinteger.Considerthesetofn×nmatricesX=(ai;j)1≤i;j≤nwithentries0and1.(1)showthat:thereexistssuchanXwithdetX=n—1.n(3)Whenn≥2023,showthatthereexistsanXwithdetX>n4.n6f1.Isthereanonzerorealnumbers,suchthatlimn→∞||ns||=0?2.Isthereanonzerorealnumbers,suchthatlimn→∞||ns||=0?7Acompanyhasoneopenpositionavailable,andNcandidatesapplied(Nisknown).AssumetheNcandidates’abilitiesforthispositionarealldiferentfromeachother(inotherwords,thereisanon-ambiguousrankingamongtheNcandidates),andthehiringcommitteecanobservethefullrelativerankingofallthecandidatestheyhaveinterviewed,andtheirobservedrankingsarefaithfulwithrespecttothecandidates’trueabilities.Thehiringcommitteedecidesthefollowingruletoselectoneca1.ThecommitteeinterviewsthecandidatesTheyobserveinformationoncandidates’relativerankingregardingtheirabilitiesfortheposition.Theonlyinformationavailabletothemafterinterviewingmcandidates2.Aftereachinterview,thecommitteedecideswhethertooferthecandidatethepositionornot.3.Iftheydecidetooferthepositiontothecandidatejustinterviewed,thenthecandi-datewillacceptthejobwithprobabilityp,anddeclinetheoferwithprobability1-p,independentlywithallothercandidates.Iftheselectedcandidateacceptstheofer,thenhe/shegetsthejob,andthecommitteestopsinterviewingtheremainingcandi-dates.Ifhe/shedeclinestheofer,thenthecommitteeproceedtointerviewingthenextcandidate.4.Iftheydecidenottooferthepositiontothecandidatejustinterviewed,thentheyproceedtointerviewingthenextcandidate,andtheycannotturnbacktopreviouslyoruntilthey?nishinterviewingallNcandidatesifthepositionhasnotbeen?lledprobabilityamongtheN!possibilities.Thecommittee’smissionistomaximisetheproba-bilityofgettingthecandidatewiththehighestranking(amongNcandidates)forthejob(a)Fix1≤m≤N,andconsiderthefollowingstrategy.Thecommitteeinterviewsthe?rstm-1candidates,anddonotgiveofertoanyofthemregardlessoftheirrel-ativerankings.Startingfromthem-thcandidate,thecommitteeofershim/herthepositionwheneverthecandidate’srelativerankingisthehighestamongallpreviouslyinterviewedcandidates.Ifhe/shedeclinestheofer,thenthecommitteecontinuestheinterviewuntilthenextrelativelybestcandidate1,andthenrepeattheprocesswhenapplicable.ShowthatforeveryN,thereexistsm=mNsuchthattheabovestrategymaximisestheprobabilityofgettingthebestcandidateamongallpossiblestrategies.1“Relativelybestcandidate”referstothecandidatewiththehighestabilityamongallcandidateswhohavebeeninterviewed(includingthosewhoareoferedthepositionanddeclined).8(b)Supposep=1.Whatisthelimitof11Balllighteningscientist.Scientist:”Chief,wv=ar+r3-r5.Herer(t)representstheradiusofballlightning,andtisthetimevariable.Attheinitialmoment,thereisnoballlightning,thatis,r(0)=0.Accordingly,wealsohavev(0)=0.controllever.Wesetitspresetvaluetoa=-1.”You:”Welldone,Doctor!Isaouronlywaytheballlightning.”Scientist:”You’reright,Chief.Wedohaveanotherwayofcontrol,whichistokicktheinstrument.”You:”Doctor,areyoukiddingme?Kickit?”Scientist:”Yes,ifyoukickit,thevalueofr(t)willinstantlyincreasebyε(εismuchsmallerthan1).”You:”Isee.That’shelpfulindeed.Ourtestgoaltodayistostarttheballlightning,makeitsradiusstrictlyexceed√2,andthenletitgraduallydisappearcompletely.”Scientist:”Yes,Chief.WWhatdoyouthinkoftheseschemes,Chief?”(A).Seta=2,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,(B).Seta=3,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,(C).Seta=4,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,(D).Seta=5,kicktheinstrument,waitfortheballlightningradiustostrictlyexceed√2,21AnswerTheansweris(B).Weintroducethefollowingnotationfortheratefunctionv=f(r;a).Whenv>0,risincreasingintime.Whenv<0,risdecreasingintime.Whenv=0,rWecan?ndalltherootsoff(r,a)=0,whichwelistinthefollowing:r1=0,r2=-,r3=Whena>0,wehavetwononnegativeroots:r1=0andr5>0.Clearly,whenr∈(0,r5),v>0;andwhenr∈(r5,+∞),v<0.Thus,whena>0andifwekicktheinstrument,wecanstarttheballlightening,anditsradiuswillgrowtor5(butitwillnotexceedr5).When-particular,wehaver5<1andwhenr∈(r5,+∞),v<0.Thismeans,ifwestartwith,theradiusisgettingsmaller,butitwillnotbecomesmallerthanr5.Therefore,theballlighteningwillnotvanishcompletely.Hence,Scheme(D)fails.Whena=-,similartothepreviouscase,theradiuswillnotbesmallerthanr5=,andtheballlighteningwillnotvanishcompletely.Hence,Scheme(C)fails.Whena<-v<0,andthustheballlighteningwillvanishcompletely.ThismeansScheme(B)works.3LetthesumofedgekengthsofO1(resp.O2)bel1(resp.l2).Whenwecalculatel1/l2,whichvalue(s)amongthefollowingcanbeobtained?(MultipleChoice)(A).0.64(B).1(E).42AnswerTheansweris(A)(B)(C)(D).CommentsInthe60’s-70’s,thefollowingquestionappearedinAll-UnionMathOlympiadofUSSR:AtetradehronV1sitsinsideanothertetrahedronV2,provethatthesumofedgelengthsofV1doesnotexceedtimesthatofV2.Whatisanti-intuitiveisthat,onaplane,ifatrianglesitsinsideanothertriangle,thennotonlytheareaofthe?rsttriangleisstrictlysmallerthanthatofthesecondone,buttheperimeteralsois.Nowinathreedimensionalsituation,thoughthe“order”ofvolumeandsurfaceisstillkept,itisnotthecasefortheThe“origine”oftheproblemislikelythefollowingpaperinPolish:Holszty/nski,W.andKuperberg,W.,OnaPropertyofTetrahedra,AlabamaJ.MathThenin1986,CarlLinderholmoftheUniversityofAlabamageneralizedtheaboveresulttodimensionalfacesofSdoesnotexceedBm,rtimesthatofT.HereBm,riscalculatedasfollows:Letm+1=(r+1)q+s(Euclideandivision),then(CARLLINDERHOLM,ANINEQUALITYFORSIMPLICES,GeometriaeDedicata(1986)Nowbacktothecurrentproblem,theChoice(A)istrivial,sowefocuson:4?why(B),(C)and(D)canberealized??why(E)cannot?(A)alittlegeometrictopology:anoctahedronwithallfacesbeingtriangleshas3×8/2=12Theonlyotherpossibilityisthateveryvertexhasdegree4(likethatofaregularocrahedron).(C)alittlebitofconvexgeometry:asweconsidercondistanceoftwopointsonitmustbeattainedbetweentwovertices.?Ifeveryvertexofthebigoctahedronisofdegree4,andthemaximumdistancelisrealizedbetweentwoverticesAandBthatareNOTadjacent,thenastheotherfourverticesarealladjacenttothem,sol2isatleast4l2(andcanbearbitrarilyclosetothatvalurwhentheotherfourverticesarecloseenoughtolineAB),andforthesmallwhiletheotherthreeveryclosetoB,sol1wouldbeverycloseto6l2.Henceanyratio?Ifthemaximumdistancelisrealizedbetweentwoverticesofdegree3inoctahedron,thenl2isatleast3l2(andcanbearbitrarilyclosetothatvalurwhentheotherfourverticesarecloseenoughtolineAB),whileforthesmalloctahedron,wecanstilltakeeachvertextobeofdegree4,anotherthreeveryclosetoB,sol1woulActually,ifthesmalloctahedronhasthesometopologicalcon?gurationasthatofthefourverticesareveryclosetogether,thentheratiocanactuallyapproach8/3.adjacentornot),onehasalwaysl2isatlastmin(a,b)l,whileobviouslyl1cannotexceed53Twoplayers,AandB,playagamecalled“drawthejokercard”.Inthebeginning,PlayerAhasndiferentcards.PlayerBhasn+1cards,nofwhicharethesamewiththencardsinPlayerA’shand,andtherestoneisaJoker(diferentfromallotherncards).Therulesi)PlayerA?rstdrawsacardfromPlayerB,andthenPlayerBdrawsacardfromPlayerA,andthenthetwoplayerstaketurnstodrawacardfromtheotherplayer.ii)ifthecardthatoneplayerdrewfromtheotheronecoincideswithoneofthecardsonhis/herownhand,thenthisplayerwillneedtotakeoutthesetwoidenticalcardsanddiscardthem.iii)whenthereisonlyonecardleft(necessarilytheJoker),theplayerwhoholdsthatcardAssumeforeachdraw,theprobabilityofdrawinganyofthecardsfromtheotherplayeristhesame.WhichninthefollowingmaximisesPlayerA’schanceofwinningth(A).n=31(B).n=32(C).n=999(D).n=10003AnswerTheansweris(B).WedenoteantobetheprobabilitythatAwinsthegamewhenAhasncardsinthebeginning.(1)Therefore,a1=.Inaddition,wehave(2)Actually,wecanobtainthefollowinginductionformulawherethe?rsttermontheRHSisthescenariowhenAdoesnotdrawthejokercardfromB.Inthiscase,nomatterwhichcardBdrawsfromA,thiscardwouldmatchoneofthecardsthatBhasinhishand(becauseBholdsthejokercard).ThenAwillhaven-2cardsandBhasn-1cards,withAdrawingfromB?rstandBholdingthejokercard.Thesecond6termontheRHSisthescenariowhenA?rstdrawsthejokercardfromB,andthenBdrawsthejokercardfromA.ThethirdtermontheRHSisthescenariowhenAdrawsthejokercardfromBbutBdoesnotdrawthejokercardfromA,andpn;n-1istheprobabilityforAtowinthegamewhenAdraws?rstwithncardsincludingajokercard,Bdrawsnextwithn-1cardsthatdonotincludethejokercard.Wehavepn;n-1=1-an-2,(4)becausenomatterwhichcardAdrawsfromB,AwouldhaveonecardinhandthatmatchthisdrawncardfromB(becausethejokercardisinA’shand).Therefore,afterA’sdrawing,Awillhaven-1cardsincludingthejokercard,Bwillhaven-2cardswithoutthejokercard,andBdraws?rst.Inthiscase,theprobabilityforBtowinwillbean-2,sowehavepn;n-1=1-an-2.=...Byinduction,ifnisanoddnumber,then(7)Ontheotherhand,ifnisanevennumber,thenbyinductionwehave(8)?a31=?a32=?a1000=.rectansweris(B),andn=32initialcardswillgiveAthebiggestchancfwinning.7theoriginalcrossing.Ateverycrossing,thereisnowaittoturnright,1minutewaittogostraight,and2minuteswaittoturnleft.LetSbetheminimumnumberoftotalminutesonwaitingatthecrossings,then(A).S<50(B).50≤S<904AnswerTheansweris(C).Obviously,therouteofdrivingisanon-self-intersectingclosedpolyline.Regardeachorequaltoastraightangle..Bytheformulaofthesumoftheanglesofthepolygon,theright,gostraightandturnleft,respectively.Thetotaltimeonwaitingatthecrossingsiscorrspondstoturnleft,gostraightandturnright,respectively.ThetotaltimeonwaitingatNote:Ifweignorethewaitingtimeonthebeginning/endingcrossing,thetotaltimeonwehavethatS=94,butdonotafectthecorrectchoice.85Letn≥2beagivenpositiveinteger.Considerthesetofn×nmatricesX=(ai,j)1≤i,j≤nwithentries0and1.(1)showthat:thereexistssuchanXwithdetX=n?1.(2)when2≤n≤4,showthatdetX≤n?1.n(3)Whenn≥2023,showthatthereexistsanXwithdetX>n4.n5Answer(1)IfXhasazerorowortwoequalrows,thendetX=0;ifXhasarowwithonlyonenonzeroentry,itreducesto(n?1)matrixcase;ifXhasarowwithnnonzeroentriesandarowwith(n?1)nonzeroentries,itreducestothecasethatXhasarowwithonlyonenonzeroentryandfurtherreducesto(n?1)matrixcase.Whentheaboveallnothappen,(2)takeXI=(ai,j)1≤i,j≤nwhereai,j=1?δi,j,1≤i,j≤n.Then,detXI=(?1)n—1(n?1).Ifnisodd,letX=XI.Ifniseven,getXbyswitchingthe?rsttworowsofXI.Then,detX=n?1.Then,Yisan(n+1)×(n+1)matrixwithentries±1andhavingThelastrowofYisequaltoαn+1=(,...,).Writeti=±1forthelastentryofthei-thn+1rowαiofY(1≤i≤n).PutRemovingthelastentryofβ(whichis0),wegetannrowvectorβi.PutXI=(β1,...,βn)tandwriteThen,XIisann×nmatrixwithentries0and1andwehavedetXI=t2(k—2)2k-1+1.9Switchingthe?rsttworowsofX/ifnecessary,wegetann×nmatrixXwithentries