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

Evan Chen / IMO Solution Notes

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

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

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

1997

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
В равнината е дадена безкрайна шахматна дъска. За всяка двойка положителни цели числа mm и nn разглеждаме правоъгълен триъгълник с върхове във възли на решетката, чиито катети са с дължини mm и nn и лежат върху страни на квадратчетата. Нека S1S_1 е общата площ на черната част на триъгълника, а S2S_2 - общата площ на бялата част. Нека f(m,n)=∣S1−S2∣.f(m,n)=|S_1-S_2|. (a) Намерете f(m,n)f(m,n) за всички положителни цели m,nm,n, които са или и двете четни, или и двете нечетни. (b) Докажете, че f(m,n)≤12max⁡{m,n}f(m,n)\le\frac12\max\{m,n\} за всички m,nm,n. (c) Докажете, че не съществува константа CC, такава че f(m,n)<Cf(m,n)\lt{}C за всички m,nm,n.
РешениеЗа област в равнината ще наричаме ориентирана разлика нейната черна площ минус нейната бяла площ. Допускаме тя да е отрицателна, така че ориентираната разлика е адитивна, а f(m,n)f(m,n) е абсолютната стойност на ориентираната разлика на съответния правоъгълен триъгълник. За (a) отговорът е0ако m,n са четни,0\quad\text{ако }m,n\text{ са четни},12ако m,n са нечетни.\qquad \frac12\quad\text{ако }m,n\text{ са нечетни}.Да разгледаме следната схема.ABCMPQТриъгълниците APMAPM и BQMBQM са еднакви. Освен това, когато m≡n(mod2)m\equiv n\pmod 2, техните шахматни оцветявания съвпадат, защото преместването от единия към другия запазва цвета на всяка съответна точка. Следователно ориентираната разлика на големия триъгълник е точно ориентираната разлика на правоъгълника CPQBCPQB. Той има цели хоризонтални дължини и височина n/2n/2; ако m,nm,n са четни, правоъгълникът се разпада на цели редове с равни черна и бяла площ и разликата е 00. Ако m,nm,n са нечетни, остава точно половин ред с едно квадратче повече от единия цвят, така че абсолютната разлика е 1/21/2. За (b) случаите от (a) вече дават f(m,n)≤1/2≤12max⁡{m,n}f(m,n)\le1/2\le\frac12\max\{m,n\}. Остава да разгледаме различни четности. Нека например mm е четно, а nn е нечетно. Триъгълникът с катети mm и nn може да се разреже на триъгълник с катети mm и n−1n-1 и тънък триъгълник с основа 11 и височина mm. Първата част има ориентирана разлика 00 по (a), а абсолютната ориентирана разлика на втората част е най-много нейната площ m/2m/2. Значи f(m,n)≤m/2≤12max⁡{m,n}f(m,n)\le m/2\le\frac12\max\{m,n\}. Случаят, в който mm е нечетно, а nn е четно, е симетричен. За (c) ще докажем, че за всяко k≥1k\ge1 е изпълненоf(2k,2k+1)=2k−16.f(2k,2k+1)=\frac{2k-1}{6}.Това веднага изключва съществуването на универсална константа CC, защото дясната страна расте неограничено с kk. За илюстрация при k=2k=2 използваме триъгълник с върхове (0,0)(0,0), (0,2k)(0,2k) и (2k+1,0)(2k+1,0).Без ограничение нека горното ляво квадратче е черно. Малките 2k2k бели триъгълника непосредствено под диагонала имат обща площ12⋅12k+1⋅12k(12+22+⋯+(2k)2)=\frac12\cdot\frac1{2k+1}\cdot\frac1{2k}\left(1^2+2^2+\cdots+(2k)^2\right)=4k+112.\frac{4k+1}{12}.От друга страна, 2k2k-те черни многоъгълника непосредствено под диагонала имат обща площ∑i=12k(1−12⋅12k+1⋅12k⋅i2)=\sum_{i=1}^{2k}\left(1-\frac12\cdot\frac1{2k+1}\cdot\frac1{2k}\cdot i^2\right)=2k−4k+112=20k−112.2k-\frac{4k+1}{12}=\frac{20k-1}{12}.В останалите цели квадратчета, които са общо 1+2+⋯+2k1+2+\cdots+2k, белите квадратчета са с kk повече от черните. Следователно ориентираната разлика по абсолютна стойност еf(2k,2k+1)=∣−k+20k−112−4k+112∣=2k−16.f(2k,2k+1)=\left|-k+\frac{20k-1}{12}-\frac{4k+1}{12}\right|=\frac{2k-1}{6}. Така f(2k,2k+1)f(2k,2k+1) е неограничена величина, което доказва (c).
Отвори задачатаEvan Chen VONVON IMO 1997/1Условие — източник

Задача 2

Пълен запис
Условие
Нека ABCABC е триъгълник, за който ∠A<min⁡(∠B,∠C)\angle A\lt{}\min(\angle B,\angle C). Точките BB и CC разделят описаната окръжност на триъгълника на две дъги. Нека UU е вътрешна точка на дъгата BCBC, която не съдържа AA. Симетралите на отсечките ABAB и ACAC пресичат правата AUAU съответно в точките VV и WW. Правите BVBV и CWCW се пресичат в TT. Докажете, че AU=TB+TCAU=TB+TC.
РешениеНека правата през B,T,VB,T,V пресича описаната окръжност повторно в U1U_1; тогава AU1UBAU_1UB е равнобедрен трапец. Аналогично дефинираме U2U_2 чрез правата през C,T,WC,T,W.ABCUU1U2TВ първия равнобедрен трапец равните диагонали са AUAU и BU1BU_1, следователно AU=BU1AU=BU_1. Понеже TT лежи на правата BU1BU_1, имаме BU1=BT+TU1BU_1=BT+TU_1. Аналогичният втори трапец дава последното нужно равенство TU1=TCTU_1=TC. ТакаAU=BU1=BT+TU1=BT+TC,AU=BU_1=BT+TU_1=BT+TC,както се искаше.
Отвори задачатаEvan Chen VONVON IMO 1997/2Условие — източник

Задача 3

Пълен запис
Условие
Нека x1,x2,…,xnx_1,x_2,\ldots,x_n са реални числа, за които ∣x1+x2+⋯+xn∣=1,|x_1+x_2+\cdots+x_n|=1,∣xi∣≤n+12(i=1,2,…,n).\qquad |x_i|\le\frac{n+1}{2}\quad(i=1,2,\ldots,n). Докажете, че съществува пермутация y1,y2,…,yny_1,y_2,\ldots,y_n на x1,x2,…,xnx_1,x_2,\ldots,x_n, такава че ∣y1+2y2+⋯+nyn∣≤n+12.|y_1+2y_2+\cdots+ny_n|\le\frac{n+1}{2}.
РешениеБез ограничение можем да приемем, че x1+x2+⋯+xn=1x_1+x_2+\cdots+x_n=1, като при нужда сменим знаците на всички числа. Също така ги преномерираме така, че x1≤x2≤⋯≤xnx_1\le x_2\le\cdots\le x_n. По неравенството за пренареждане най-голямата възможна стойност на ∑i=1niyi\sum_{i=1}^n i y_i е A=∑i=1nixi,A=\sum_{i=1}^n i x_i, а най-малката е B=∑i=1n(n+1−i)xi.B=\sum_{i=1}^n (n+1-i)x_i. Средната стойност на тази сума по всички пермутации е 1+2+⋯+nn(x1+x2+⋯+xn)=n+12,\frac{1+2+\cdots+n}{n}(x_1+x_2+\cdots+x_n)=\frac{n+1}{2}, затова B≤(n+1)/2≤AB\le (n+1)/2\le A. Сега преминаваме от реда, който дава AA, към обратния ред, който дава BB, чрез последователни размени на съседни елементи. Ако на позиции ii и i+1i+1 разменим u≤vu\le v, стойността намалява с v−uv-u, а от условието v−u≤n+1v-u\le n+1. Интервалът [−(n+1)/2,(n+1)/2][-(n+1)/2,(n+1)/2] има дължина n+1n+1. Понеже започваме не по-малко от (n+1)/2(n+1)/2 и завършваме не по-голямо от (n+1)/2(n+1)/2, а всяка стъпка е с дължина най-много n+1n+1, някоя междинна пермутация дава стойност в този интервал. Това е точно исканото.
Отвори задачатаEvan Chen VONVON IMO 1997/3Условие — източник

Задача 4

Пълен запис
Условие
Матрица n×nn\times n с елементи от множеството S={1,2,…,2n−1}S=\{1,2,\ldots,2n-1\} се нарича сребърна, ако за всяко i=1,2,…,ni=1,2,\ldots,n ii-тият ред и ii-тият стълб заедно съдържат всички елементи на SS. Докажете, че: (a) не съществува сребърна матрица за n=1997n=1997; (b) сребърни матрици съществуват за безбройно много стойности на nn.
РешениеЗа (a) наричаме кръст обединението на един ред и съответния му стълб. Всяка клетка извън главния диагонал участва в точно два кръста, а всяка диагонална клетка участва в точно един. Ако имаше сребърна матрица за n=1997n=1997, всеки символ s∈Ss\in S щеше да се среща във всеки от 19971997-те кръста, тоест общият му брой участия в кръстове щеше да е нечетен. Извън диагонала всяко срещане се брои два пъти, затова броят на срещанията на ss върху диагонала трябва да е нечетен, в частност поне едно. Но ∣S∣=3993|S|=3993, а диагоналът има само 19971997 клетки, противоречие. За (b) ще построим сребърна матрица MeM_e за всяко n=2en=2^e, e≥1e\ge1, като поддържаме и свойството, че всички единици са точно по главния диагонал. За e=1e=1 вземаме матрицата с редове (1,2)(1,2) и (3,1)(3,1). Нека вече имаме Me−1M_{e-1} с размер m=2e−1m=2^{e-1} и положим c=2e−1=2m−1c=2^e-1=2m-1. Първо образуваме блокова матрица с блокове Me−1M_{e-1} горе вляво и долу вдясно, а Me−1+cM_{e-1}+c горе вдясно и долу вляво. Тя съдържа числата от 11 до 2e+1−22^{e+1}-2; липсва само 2e+1−12^{e+1}-1. Във всеки нов кръст ниските числа идват от стар кръст на Me−1M_{e-1}, а високите числа идват от съответните ред и стълб на изместените блокове. Единствената повторена висока стойност е 2e2^e, защото тя идва от диагоналните единици на стария блок. Заменяме в горния десен блок тези стойности 2e2^e с четен локален диагонален индекс с 2e+1−12^{e+1}-1, а в долния ляв блок - тези с нечетен локален диагонален индекс. Тогава всеки кръст вижда точно едно от двете си копия на 2e2^e заменено с липсващото число 2e+1−12^{e+1}-1, а всички останали числа остават налични. Следователно получаваме сребърна матрица от размер 2e2^e. Понеже това работи за всяко e≥1e\ge1, такива размери има безбройно много.
Отвори задачатаEvan Chen VONVON IMO 1997/4Условие — източник

Задача 5

Пълен запис
Условие
Намерете всички двойки положителни цели числа (a,b)(a,b), за които ab2=ba.a^{b^2}=b^a.
РешениеОтговорът е (1,1),(16,2),(27,3).(1,1),\quad(16,2),\quad(27,3). Ако едно от числата a,ba,b е равно на 11, веднага получаваме (a,b)=(1,1)(a,b)=(1,1). Нека занапред a,b>1a,b\gt{}1. Всяко цяло число, по-голямо от 11, се представя еднозначно във вида tmt^m, където m∈Nm\in\mathbb N, а tt не е точна степен. Да запишем a=sma=s^m и b=tnb=t^n в този вид. От (sm)t2n=(tn)sm\left(s^m\right)^{t^{2n}}=\left(t^n\right)^{s^m} и еднозначността следва s=ts=t, а после mt2n=ntm,тоестt2n−m=nm.m t^{2n}=n t^m,\qquad\text{тоест}\qquad t^{2n-m}=\frac nm. Нека e=2n−me=2n-m. Тогава n=temn=t^e m и след заместване получаваме e+m=2tem.e+m=2t^e m. Разглеждаме възможностите за цялото число ee. Ако e>0e\gt{}0, дясната страна е по-голяма от e+me+m, невъзможно. Ако e=0e=0, получаваме m=2mm=2m, пак невъзможно. Ако e=−1e=-1, то m−1=2mt,m=tt−2,m-1=\frac{2m}{t},\qquad m=\frac{t}{t-2}, откъдето единствената допустима възможност е t=3t=3, m=3m=3, n=1n=1, даваща (a,b)=(27,3)(a,b)=(27,3). Ако e=−2e=-2, то m−2=2mt2,m=2t2t2−2,m-2=\frac{2m}{t^2},\qquad m=\frac{2t^2}{t^2-2}, откъдето получаваме t=2t=2, m=4m=4, n=1n=1, тоест (a,b)=(16,2)(a,b)=(16,2). Накрая, ако e=−k≤−3e=-k\le-3, тогава m=k+2ktk−2.m=k+\frac{2k}{t^k-2}. За k≥3k\ge3 и t≥2t\ge2 имаме tk−2≥2kt^k-2\ge2k, като равенство е възможно само при (t,k)=(2,3)(t,k)=(2,3); тогава обаче n=m/tkn=m/t^k не е цяло число. Други случаи няма. Проверка показва, че трите намерени двойки наистина удовлетворяват уравнението.
Отвори задачатаEvan Chen VONVON IMO 1997/5Условие — източник

Задача 6

Пълен запис
Условие
За всяко положително цяло число nn нека f(n)f(n) е броят на представянията на nn като сума от степени на 22 с неотрицателни цели показатели. Представяния, които се различават само по реда на събираемите, се смятат за еднакви. Например f(4)=4f(4)=4, защото 4,2+2,2+1+1,1+1+1+14,\qquad 2+2,\qquad 2+1+1,\qquad 1+1+1+1 са четирите такива представяния. Докажете, че за всяко цяло число n≥3n\ge3 е изпълнено 2n2/4<f(2n)<2n2/2.2^{n^2/4}\lt{}f(2^n)\lt{}2^{n^2/2}.
РешениеПолагаме f(0)=1f(0)=1. Ако сортираме представянията на NN според броя на използваните единици, след премахване на тези единици и деление на останалите събираеми на 22 получаваме рекурсията f(N)=∑j=0⌊N/2⌋f(j).f(N)=\sum_{j=0}^{\lfloor N/2\rfloor} f(j). Оттук веднага следва, че ff е монотонна и че f(2r+1)=f(2r)f(2r+1)=f(2r). Горната оценка доказваме с индукция. За n=3n=3 имаме f(8)=10<29/2f(8)=10\lt{}2^{9/2}. За n≥4n\ge4 от рекурсията и монотонността получаваме f(2n)≤(2n−1+1)f(2n−1)<2n−1/2f(2n−1),f(2^n)\le (2^{n-1}+1)f(2^{n-1})\lt{}2^{n-1/2}f(2^{n-1}), защото 2n−1+1<2n−1/22^{n-1}+1\lt{}2^{n-1/2}. Индукционното предположение дава f(2n)<2n−1/2⋅2(n−1)2/2<2n2/2.f(2^n)\lt{}2^{n-1/2}\cdot2^{(n-1)^2/2}\lt{}2^{n^2/2}.За долната оценка ни трябва лека изпъкналост. Ако a+ba+b е четно, то f(2a)+f(2b)≥2f(a+b).f(2a)+f(2b)\ge2f(a+b). Наистина, при a≥ba\ge b и m=(a+b)/2m=(a+b)/2 рекурсията свежда това до ∑j=m+1af(j)≥∑j=b+1mf(j),\sum_{j=m+1}^{a} f(j)\ge\sum_{j=b+1}^{m} f(j), което следва от монотонността, понеже двете суми имат еднакъв брой събираеми. Следователно за 1≤k<2n−11\le k\lt{}2^{n-1} имаме f(2n−1−k)+f(k+1)≥2f(2n−2),f(2^{n-1}-k)+f(k+1)\ge2f(2^{n-2}), като при нужда използваме f(2r+1)=f(2r)f(2r+1)=f(2r), за да направим двата аргумента четни. В рекурсията за f(2n)f(2^n) сдвояваме членовете f(r)f(r) за 1≤r≤2n−11\le r\le2^{n-1} като f(k+1)f(k+1) с f(2n−1−k)f(2^{n-1}-k). Първата двойка f(1)+f(2n−1)f(1)+f(2^{n-1}) също е поне 2f(2n−2)2f(2^{n-2}), защото f(2n−1)≥2f(2n−2)f(2^{n-1})\ge2f(2^{n-2}). Така f(2n)>2n−1f(2n−2).f(2^n)\gt{}2^{n-1}f(2^{n-2}). По индукционното предположение за n−2n-2 получаваме f(2n)>2n−1⋅2(n−2)2/4=2n2/4,f(2^n)\gt{}2^{n-1}\cdot2^{(n-2)^2/4}=2^{n^2/4}, а началото n=3,4n=3,4 се проверява директно от f(8)=10f(8)=10 и f(16)=36f(16)=36.
Отвори задачатаEvan Chen VONVON IMO 1997/6Условие — източник