maths.bgmaths.bg
Всички колекции
IMO

Evan Chen / IMO Solution Notes

159 задачи от базата, подредени за бързо решаване по година или клас. Показаните източници са тези, записани към самите задачи.

29 години1 класаИма видими липси
По годинаПо клас

Избрана година

2022

Назад към папките

11-12

6 задачи

Задача 1

Пълен запис
Условие
Банката в Осло издава два вида монети: алуминиеви, означени с AA, и бронзови, означени с BB. Мариане има nn алуминиеви и nn бронзови монети, наредени в редица в произволен начален ред. Верига е всяка последователна подпоредица от монети от един и същи вид. За фиксирано положително цяло число k≤2nk\le 2n Гилберти многократно извършва следната операция: намира най-дългата верига, съдържаща kk-тата монета отляво, и премества всички монети от тази верига в левия край на редицата. Например при n=4n=4 и k=4k=4 процесът от редицата AABBBABAAABBBABA еAABBBABA→BBBAAABA→AAABBBBA→BBBBAAAA→⋯ .AABBBABA\to BBBAAABA\to AAABBBBA\to BBBBAAAA\to\cdots.Да се намерят всички двойки (n,k)(n,k) с 1≤k≤2n1\le k\le 2n, за които при всяка начална наредба в някой момент най-левите nn монети са всички от един и същи вид.
РешениеОтговорът еn≤k≤⌈3n2⌉.n\le k\le \left\lceil\frac{3n}{2}\right\rceil.Ще наричаме максимална верига блок. Нека дължините на блоковете са e1,e2,…,eme_1,e_2,\ldots,e_m отляво надясно. След една операция броят mm на блоковете никога не се увеличава. Освен това mm остава същият точно в следните два случая: или k≤e1k\le e_1, или mm е четно и em≥2n+1−ke_m\ge 2n+1-k. Това се проверява директно от действието на операцията: избраният блок или вече е най-левият, или при преместването му се залепва за блок от същия вид в левия край; във всички останали случаи поне два блока се сливат. Ако k<nk\lt{}n, вземаме начална наредба An−1BnAA^{n-1}B^nA. Тогава kk-тата монета лежи в първия блок, операцията не променя редицата и най-левите nn монети никога не са еднотипни. Ако k>⌈3n/2⌉k\gt{}\lceil3n/2\rceil, вземаме четири блока с дължини⌊n2⌋,⌊n2⌋,⌈n2⌉,⌈n2⌉,\left\lfloor\frac n2\right\rfloor,\left\lfloor\frac n2\right\rfloor,\left\lceil\frac n2\right\rceil,\left\lceil\frac n2\right\rceil,например с редуващи се видове. Тогава след всяка операция блоковете само се завъртат и m=4m=4 се запазва, така че желаното състояние не се достига. Остава да докажем, че при n≤k≤⌈3n/2⌉n\le k\le\lceil3n/2\rceil винаги успяваме. Понеже mm не се увеличава, достатъчно е да покажем, че ако m>2m\gt{}2, той не може да остане постоянен завинаги. Да допуснем обратното. След първите три операции трябва да сме във втория случай от критерия по-горе, затова m≥4m\ge4 е четно и последните три премествани блока имат дължини поне 2n+1−k2n+1-k. В частност два от тях са от един и същи вид, следователноn≥em+em−2≥2(2n+1−k).n\ge e_m+e_{m-2}\ge2(2n+1-k).Оттук k≥3n/2+1k\ge 3n/2+1, което противоречи на k≤⌈3n/2⌉k\le\lceil3n/2\rceil. Следователно mm рано или късно намалява, а повтаряйки това стигаме до m=2m=2. Тогава редицата се състои от два блока с по nn монети, така че най-левите nn монети са от един и същи вид.
Отвори задачатаEvan Chen VONVON IMO 2022/1Условие — източник

Задача 2

Пълен запис
Условие
Да се намерят всички функции f:R+→R+f:\mathbb R_+\to\mathbb R_+, за които за всяко x∈R+x\in\mathbb R_+ съществува точно едно y∈R+y\in\mathbb R_+, удовлетворяващоxf(y)+yf(x)≤2.xf(y)+yf(x)\le2.
РешениеОтговорът еf(x)=1x,f(x)=\frac1x,което очевидно работи, като единственото подходящо yy е y=xy=x. Нека сега ff е произволно решение. Ще казваме, че xx и yy са приятели, ако xf(y)+yf(x)≤2xf(y)+yf(x)\le2. Релацията е симетрична, а по условие всяко xx има точно един приятел. Първо ще докажем, че всяко число е собствен приятел. Да допуснем, че различни aa и bb са приятели. Тогава aa не е собствен приятел, следователно 2af(a)>22af(a)\gt{}2 и f(a)>1/af(a)\gt{}1/a. Аналогично f(b)>1/bf(b)\gt{}1/b. Но тогава2≥af(b)+bf(a)>ab+ba≥2,2\ge af(b)+bf(a)\gt{}\frac ab+\frac ba\ge2,противоречие. Значи единственият приятел на xx е самото xx. Следователно2xf(x)≤2,2xf(x)\le2,тоест f(x)≤1/xf(x)\le1/x за всяко x>0x\gt{}0, а за x≠yx\ne y имаме xf(y)+yf(x)>2xf(y)+yf(x)\gt{}2. Фиксираме x>0x\gt{}0 и ε>0\varepsilon\gt{}0. Тъй като xx и x+εx+\varepsilon не са приятели,2<xf(x+ε)+(x+ε)f(x)≤2\lt{}xf(x+\varepsilon)+(x+\varepsilon)f(x)\lexx+ε+(x+ε)f(x).\frac{x}{x+\varepsilon}+(x+\varepsilon)f(x).Оттукf(x)>x+2ε(x+ε)2=1x+ε2x+2ε.f(x)\gt{}\frac{x+2\varepsilon}{(x+\varepsilon)^2}=\frac1{x+\frac{\varepsilon^2}{x+2\varepsilon}}.Като пуснем ε→0+\varepsilon\to0^+, получаваме f(x)≥1/xf(x)\ge1/x. Значи f(x)=1/xf(x)=1/x за всяко x>0x\gt{}0.
Отвори задачатаEvan Chen VONVON IMO 2022/2Условие — източник

Задача 3

Пълен запис
Условие
Нека kk е положително цяло число и нека SS е крайно множество от нечетни прости числа. Да се докаже, че има най-много един начин, с точност до завъртане и отражение, елементите на SS да се поставят по окръжност така, че произведението на всеки две съседни числа да е от вида x2+x+kx^2+x+k за някое положително цяло число xx.
РешениеЩе наричаме добро всяко число от вида x2+x+kx^2+x+k, като за удобство допускаме x≥0x\ge0. Това не променя същността, защото замяната x↦−1−xx\mapsto -1-x дава същите стойности. Първо доказваме ключово твърдение. Ако pp е нечетно просто число, то има най-много две нечетни прости числа q,r<pq,r\lt{}p, за които pqpq и prpr са добри. Нещо повече, акоpq=x2+x+k,pr=y2+y+kpq=x^2+x+k,\qquad pr=y^2+y+kс x,y≥0x,y\ge0, тогаваx+y+1=p,xy≡k(modp).x+y+1=p,\qquad xy\equiv k\pmod p.Наистина, уравнението T2+T+k≡0(modp)T^2+T+k\equiv0\pmod p има най-много две решения по модул pp. Понеже q,r<pq,r\lt{}p и k>0k\gt{}0, съответните xx и yy лежат в интервала [0,p−1][0,p-1]. Формулите за сумата и произведението на корените дават x+y≡−1(modp)x+y\equiv-1\pmod p и xy≡k(modp)xy\equiv k\pmod p, а от 0<x+y<2p0\lt{}x+y\lt{}2p следва x+y+1=px+y+1=p. Сега ще покажем, че ако такива две числа qq и rr съществуват, то и qrqr е добро. Нека α\alpha е корен на α2+α+k=0\alpha^2+\alpha+k=0. Тогаваt2+t+k=N(t−α)t^2+t+k=N(t-\alpha)в квадратичното разширение, където NN означава нормата. Следователноpq⋅pr=N((x−α)(y−α))=pq\cdot pr=N((x-\alpha)(y-\alpha))=N((xy−k)−(x+y+1)α).N((xy-k)-(x+y+1)\alpha).Понеже x+y+1=px+y+1=p и xy≡k(modp)xy\equiv k\pmod p, можем да разделим вътрешния израз на pp и получавамеqr=N(xy−kp−α),qr=N\left(\frac{xy-k}{p}-\alpha\right),тоест qrqr също е добро. Вече завършваме с индукция по ∣S∣|S|. Нека pp е най-големият елемент на SS. В допустима наредба двете му съседни числа трябва да са сред най-много двете възможности от първото твърдение. Ако са две, второто твърдение показва, че те могат да станат съседни след изтриване на pp, защото произведението им също е добро. По индукция наредбата на останалите елементи е единствена с точност до завъртане и отражение, а мястото на pp е принудено между тези две съседни числа. Това доказва единствеността.
Отвори задачатаEvan Chen VONVON IMO 2022/3Условие — източник

Задача 4

Пълен запис
Условие
Нека ABCDEABCDE е изпъкнал петоъгълник, за който BC=DEBC=DE. Да предположим, че вътре в ABCDEABCDE има точка TT такава, че TB=TDTB=TD, TC=TETC=TE и ∠ABT=∠TEA\angle ABT=\angle TEA. Правата ABAB пресича правите CDCD и CTCT съответно в точки PP и QQ, като точките P,B,A,QP,B,A,Q лежат на тази права в този ред. Правата AEAE пресича правите CDCD и DTDT съответно в точки RR и SS, като точките R,E,A,SR,E,A,S лежат на тази права в този ред. Да се докаже, че точките P,S,Q,RP,S,Q,R лежат на една окръжност.
РешениеОт условията TB=TDTB=TD, TC=TETC=TE и BC=DEBC=DE следва, че триъгълниците BTCBTC и DTEDTE са еднакви. В частност съответните ъгли при TT и при основите съвпадат. ПоставямеK=CT∩AE,L=DT∩AB,K=CT\cap AE,\qquad L=DT\cap AB,X=BT∩AE,Y=ET∩AB.\qquad X=BT\cap AE,\qquad Y=ET\cap AB.От равенството ∠ABT=∠TEA\angle ABT=\angle TEA и еднаквостта по-горе получаваме подобието△BTY∼△ETX.\triangle BTY\sim\triangle ETX.Основното твърдение е△BTQ∼△ETS\triangle BTQ\sim\triangle ETSи едновременноBY:YL:LQ=EX:XK:KS.BY:YL:LQ=EX:XK:KS.То следва от преследване на ъгли: имаме ∠BTL=∠BTD=∠CTE=∠KTE\angle BTL=\angle BTD=\angle CTE=\angle KTE и ∠BTQ=∠BTC=∠DTE=∠STE\angle BTQ=\angle BTC=\angle DTE=\angle STE, а вече установеното подобие BTY∼ETXBTY\sim ETX фиксира мащаба по двете секущи. Затова двете начупени линии TBYLQTBYLQ и TEXKSTEXKS са подобни. Оттук следват две последствия. Първо,TLTQ=TKTS,\frac{TL}{TQ}=\frac{TK}{TS},следователно TL⋅TS=TK⋅TQTL\cdot TS=TK\cdot TQ, което означава, че K,L,S,QK,L,S,Q са вписани. Второ, съответните отношения дават KL∥CDKL\parallel CD, а понеже PP и RR също лежат на CDCD, имаме KL∥PRKL\parallel PR. Накрая прилагаме теоремата на Райм към вписания четириъгълник KLSQKLSQ и правата, успоредна на KLKL, която пресича правите LQLQ и KSKS съответно в PP и RR. Получаваме, че P,S,Q,RP,S,Q,R са вписани, както трябваше.ABCDETPQRSKLXY
Отвори задачатаEvan Chen VONVON IMO 2022/4Условие — източник

Задача 5

Пълен запис
Условие
Намерете всички тройки (a,b,p)(a,b,p) от положителни цели числа, за които pp е просто число иap=b!+p.a^p=b!+p.
РешениеОтговорът е (2,2,2)(2,2,2) и (3,4,3)(3,4,3); директно се проверява, че 22=2!+22^2=2!+2 и 33=4!+33^3=4!+3. По-нататък нека a≥2a\ge2. Първо ще докажем, че b≤2p−2b\le2p-2. Ако b≥2pb\ge2p, то b!b! се дели на p2p^2, следователноb!+p≡p(modp2),b!+p\equiv p\pmod {p^2},тоест νp(b!+p)=1\nu_p(b!+p)=1. Това е невъзможно за pp-та степен apa^p, защото νp(ap)\nu_p(a^p) е кратно на pp. Остава да изключим b=2p−1b=2p-1. Тогава(2p−1)!+p=(2p-1)!+p=p((p−1)!(p+1)(p+2)⋯(2p−1)+1).p\left((p-1)!(p+1)(p+2)\cdots(2p-1)+1\right).За p>2p\gt{}2 изразът в скобите е сравним с ((p−1)!)2+1≡(−1)2+1≡2(modp)((p-1)!)^2+1\equiv (-1)^2+1\equiv2\pmod p по теоремата на Уилсън, така че отново pp-адичната валуация е 11, невъзможно. За p=2p=2 случаят b=3b=3 дава 3!+2=83!+2=8, което не е квадрат. Следователно b≤2p−2b\le2p-2. Оттукap=b!+p≤(2p−2)!+p<p2p,a^p=b!+p\le(2p-2)!+p\lt{}p^{2p},например като групираме (2p−2)≠∏k=1p−1k(2p−1−k)<(p(p−1))p−1(2p-2)\neq{}\prod_{k=1}^{p-1}k(2p-1-k)\lt{}(p(p-1))^{p-1}. Значи a<p2a\lt{}p^2. Следва, че a≥pa\ge p. Ако, напротив, a<pa\lt{}p, то p≥a+1p\ge a+1. За a=2a=2 имаме ap−p≥23−3>2!a^p-p\ge2^3-3\gt{}2!, а за a≥3a\ge3 имаме ap−p≥aa+1−(a+1)>a!a^p-p\ge a^{a+1}-(a+1)\gt{}a!. Значи във всички случаи b≠ap−p>a!b\neq{}a^p-p\gt{}a!, откъдето b>ab\gt{}a. Тогава a∣b!a\mid b!, а от уравнението по модул aa получаваме p≡0(moda)p\equiv0\pmod a, невъзможно при 1<a<p1\lt{}a\lt{}p. Така a≥pa\ge p. Освен товаb≠ap−p≥pp−p>(p−1)!,b\neq{}a^p-p\ge p^p-p\gt{}(p-1)!,следователно b≥pb\ge p. Сега ще покажем, че всъщност a=pa=p. Понеже p≤bp\le b, имаме p∣b!p\mid b!, а от уравнението следва p∣ap\mid a. Нека a=pka=pk. От a<p2a\lt{}p^2 получаваме k<pk\lt{}p, значи k<p≤bk\lt{}p\le b и следователно k∣b!k\mid b!. Вземайки уравнението по модул kk, получаваме 0≡p(modk)0\equiv p\pmod k, тоест k∣pk\mid p. Понеже 0<k<p0\lt{}k\lt{}p и pp е просто, имаме k=1k=1, значи a=pa=p. Остават малките стойности и случаят p≥5p\ge5. При p=2p=2 проверката на 2≤b≤32\le b\le3 дава единствено (a,b)=(2,2)(a,b)=(2,2). При p=3p=3 проверката на 3≤b≤43\le b\le4 дава единствено (a,b)=(3,4)(a,b)=(3,4). Накрая нека p≥5p\ge5. Тогава a=pa=p иb≠pp−p=p(pp−1−1).b\neq{}p^p-p=p(p^{p-1}-1).По теоремата на Зигмонди числото pp−1−1p^{p-1}-1 има прост делител qq, за който редът на pp по модул qq е точно p−1p-1. Следователно q≡1(modp−1)q\equiv1\pmod {p-1} и q≠pq\ne p. Понеже q∣b!q\mid b!, трябва да е q≤b≤2p−2q\le b\le2p-2. Но най-малкото число, което е сравнимо с 11 по модул p−1p-1 и е по-голямо от pp, е 2p−12p-1, противоречие. Така няма други решения.
Отвори задачатаEvan Chen VONVON IMO 2022/5Условие — източник

Задача 6

Пълен запис
Условие
Нека nn е положително цяло число. Нордически квадрат е дъска n×nn\times n, съдържаща всички цели числа от 11 до n2n^2, така че във всяка клетка стои точно едно число. Възходящ път е редица от една или повече клетки, за която: (a) първата клетка е долина, тоест записаното в нея число е по-малко от числата във всички нейни ортогонални съседи; (b) всяка следваща клетка е ортогонално съседна на предишната; (c) числата в клетките на редицата са в нарастващ ред. Да се намери, като функция на nn, най-малкият възможен общ брой възходящи пътища в нордически квадрат.
РешениеОтговорът е2n2−2n+1.2n^2-2n+1.Първо даваме долна граница. Вземаме произволни две съседни клетки с числа a>ba\gt{}b. От клетката с bb можем да вървим надолу, докато стигнем долина; понеже числата строго намаляват, това винаги спира. Обръщайки получения път, получаваме възходящ път с дължина поне 22, който завършва с реброто между тези две клетки. Различните съседни двойки дават различни такива пътища. В дъска n×nn\times n има 2n(n−1)2n(n-1) съседни двойки клетки, следователно има поне 2n(n−1)2n(n-1) възходящи пътища с дължина поне 22. Освен това има поне една долина, значи поне един път с дължина 11. Получаваме долна граница2n(n−1)+1=2n2−2n+1.2n(n-1)+1=2n^2-2n+1.За конструкцията е достатъчно да построим дърво TT върху клетки на дъската така, че никои две клетки извън TT да не са ортогонално съседни. Такова дърво може да се построи например чрез повтарящ се зигзагообразен скелет през три реда; за произволно nn се взема същият модел и се отрязват излишните последни редове и крайни колони. Поставяме числото 11 в някоя клетка на TT, после поставяме числата 2,3,…,∣T∣2,3,\ldots,|T| по дървото така, че всяко следващо число да е в клетка, съседна на вече поставена клетка. Останалите числа поставяме произволно в клетките извън TT. Тъй като всяка клетка извън TT има съсед в TT с по-малко число, а по дървото числата растат от корена 11 навън, единствената долина е клетката с 11. Освен това никои две клетки извън TT не са съседни, така че всеки възходящ път е точно един от пътищата, получени при обръщане на низходящ път по някое ребро, плюс единичният път, състоящ се само от клетката с 11. Следователно броят им е точно 2n(n−1)+12n(n-1)+1, което постига долната граница.скелет Tизолирани клеткинямат обща страна
Отвори задачатаEvan Chen VONVON IMO 2022/6Условие — източник