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

Evan Chen / JMO Solution Notes

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

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

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

2013

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

Открити липси за попълване от източника

  • 2013 · 11-12: липсва задача 3, 5

11-12

4 задачи

Задача 1

Пълен запис
Условие
Съществуват ли цели числа aa и bb, такива че a5b+3a^5b+3 и ab5+3ab^5+3 да са точни кубове на цели числа?
РешениеНе, такива цели числа aa и bb не съществуват. Ще разгледаме два случая. Първо да допуснем, че 3∣ab3\mid ab. Без ограничение нека 3∣a3\mid a. Тогаваa5b+3≡3(mod9),a^5b+3\equiv3\pmod 9,което е невъзможно за точен куб, защото кубовете по модул 99 са само 0,10,1 и 88. Остава случаят 3∤ab3\nmid ab. Тогава a5b+3a^5b+3 е куб, който не се дели на 33, следователно е равен на ±1\pm1 по модул 99. Получавамеa5b∈{5,7}(mod9).a^5b\in\{5,7\}\pmod 9.Аналогичноab5∈{5,7}(mod9).ab^5\in\{5,7\}\pmod 9.Но тези две сравнения не могат да са едновременно верни. Наистина, понеже 3∤ab3\nmid ab, от теоремата на Ойлер имаме(ab)6≡1(mod9).(ab)^6\equiv1\pmod 9.От друга страна произведението на двете числа a5ba^5b и ab5ab^5 трябва да е произведение на две числа от множеството {5,7}\{5,7\}, а5⋅5≡7,5⋅7≡8,7⋅7≡4(mod9).5\cdot5\equiv7,\qquad 5\cdot7\equiv8,\qquad 7\cdot7\equiv4\pmod 9.Нито един от тези остатъци не е 11. Противоречието доказва, че търсените цели числа не съществуват.
Отвори задачатаEvan Chen VONVON JMO 2013/1Условие — източник

Задача 2

Пълен запис
Условие
Всяка клетка на дъска m×nm\times n е запълнена с някакво неотрицателно цяло число. Две числа в запълването се наричат съседни, ако клетките им имат обща страна. Запълването се нарича градина, ако удовлетворява следните две условия: 1. Разликата между всеки две съседни числа е 00 или 11. 2. Ако едно число е по-малко или равно на всички свои съседни числа, то е равно на 00. Да се намери броят на различните градини в зависимост от mm и nn.
РешениеОтговорът е 2mn−12^{mn}-1. Ще докажем нещо по-силно, като опишем всички градини. Нека SS е произволно непразно множество от клетки на дъската. За всяка клетка θ\theta записваме минималното таксиметрово разстояние от θ\theta до някоя клетка от SS; в частност в клетките от SS записваме 00. Тогава получаваме градина, и всяка градина се получава по този начин. Понеже има точно 2mn−12^{mn}-1 непразни множества SS, това ще даде искания брой. Например, ако SS има три клетки, може да се получи градина от вида[212101101212112323012334].\begin{bmatrix} 2 & 1 & 2 & 1 & \mathbf{0} & 1 \\ 1 & \mathbf{0} & 1 & 2 & 1 & 2 \\ 1 & 1 & 2 & 3 & 2 & 3 \\ \mathbf{0} & 1 & 2 & 3 & 3 & 4 \end{bmatrix}.Лесно се вижда, че описаната процедура винаги дава градина: при движение към съседна клетка таксиметровото разстояние до SS се променя с най-много 11, а всяка клетка извън SS има съседна клетка, която е с една стъпка по-близо до SS. Остава да докажем, че всяка градина е от този вид. Да е дадена произволна градина. Първо отбелязваме, че в нея има поне една клетка с число 00: вземаме клетка с минимално записано число; то е не по-голямо от числата във всички съседни клетки, следователно по условие е 00. Нека SS е множеството от всички клетки, в които е записана нула. Твърдим, че ако в клетка θ\theta е записано числото dd, то минималното разстояние от θ\theta до клетка от SS е точно dd. Доказателството е с индукция по dd. За d=0d=0 твърдението е вярно по дефиниция на SS. Нека сега d≥1d\ge1 и в клетката θ\theta е записано dd. Всеки съсед на θ\theta има число поне d−1d-1, така че при всяка стъпка по път към клетка с нула стойността може да намалява с най-много 11; следователно всеки такъв път има дължина поне dd. От друга страна, по второто условие не може всички съседи на θ\theta да имат числа поне dd, защото тогава dd би трябвало да е 00. Значи има съседна клетка с число d−1d-1. По индукционната хипотеза от тази съседна клетка има път с дължина d−1d-1 до SS, а като добавим първата стъпка от θ\theta, получаваме път с дължина точно dd. Следователно числото във всяка клетка е точно минималното таксиметрово разстояние до SS, както искахме.
Отвори задачатаEvan Chen VONVON JMO 2013/2Условие — източник

Задача 4

Пълен запис
Условие
Нека f(n)f(n) е броят на начините да се представи nn като сбор от степени на 22, като редът на събираемите се отчита. Например f(4)=6f(4)=6, защото 44 може да се представи като 44, 2+22+2, 2+1+12+1+1, 1+2+11+2+1, 1+1+21+1+2 и 1+1+1+11+1+1+1. Намерете най-малкото n>2013n\gt{}2013, за което f(n)f(n) е нечетно.
РешениеОтговорът е 20472047. За удобство полагаме f(0)=1f(0)=1. Ако разгледаме първото събираемо в представянето на nn, получаваме рекурентната формулаf(n)=∑k=0⌊log⁡2n⌋f(n−2k).(1)f(n)=\sum_{k=0}^{\lfloor\log_2 n\rfloor} f(n-2^k).\tag{1}Първите стойности саf(0)=1,f(1)=1,f(2)=2,f(3)=3,f(4)=6,f(5)=10,f(6)=18,f(7)=31.\begin{aligned} f(0)&=1, & f(1)&=1, & f(2)&=2, & f(3)&=3,\\ f(4)&=6, & f(5)&=10, & f(6)&=18, & f(7)&=31. \end{aligned}Те подсказват следното твърдение. Ще докажем, че f(n)f(n) е нечетно тогава и само тогава, когато n+1n+1 е степен на 22. Еквивалентно, f(n)f(n) е нечетно точно за числата n=0,1,3,7,15,…n=0,1,3,7,15,\ldots, тоест за нула и за числата, чийто двоичен запис се състои само от единици. Доказваме това с индукция по nn. Да наречем такова число специално. По индукционната хипотеза в дясната страна на (1) нечетни са точно онези събираеми, за които n−2kn-2^k е специално. Това е еквивалентно наn+1=2k+2rn+1=2^k+2^rза някое r≥0r\ge0. Ако n+1n+1 е степен на 22, има точно един такъв избор: двете степени трябва да са равни, тоест 2k=2r=(n+1)/22^k=2^r=(n+1)/2. Следователно в (1) има точно едно нечетно събираемо и f(n)f(n) е нечетно. Ако n+1n+1 е сбор на две различни степени на 22, тогава има точно два избора за kk, съответстващи на тези две степени, и броят на нечетните събираеми в (1) е четен. Ако пък двоичният запис на n+1n+1 има поне три единици, няма такъв избор изобщо. И в двата случая f(n)f(n) е четно. Така твърдението е доказано. Най-малката степен на 22, по-голяма от 20142014, е 20482048, следователно най-малкото търсено nn е2048−1=2047.2048-1=2047.
Отвори задачатаEvan Chen VONVON JMO 2013/4Условие — източник

Задача 6

Пълен запис
Условие
Намерете всички реални числа x,y,z≥1x,y,z\ge1, за коитоmin⁡(x2x+xyz,x2y+xyz,x2z+xyz)=\min\left(\sqrt{\vphantom{x^2}x+xyz},\sqrt{\vphantom{x^2}y+xyz},\sqrt{\vphantom{x^2}z+xyz}\right)=x2x−1+x2y−1+x2z−1.\sqrt{\vphantom{x^2}x-1}+\sqrt{\vphantom{x^2}y-1}+\sqrt{\vphantom{x^2}z-1}.
РешениеПоставямеx=1+a,y=1+b,z=1+c,x=1+a,\qquad y=1+b,\qquad z=1+c,където a,b,c≥0a,b,c\ge0. Без ограничение нека a≤b≤ca\le b\le c. Тогава минималният член в лявата страна еx2x+xyz=x2(1+a)(1+(1+b)(1+c)).\sqrt{\vphantom{x^2}x+xyz}=\sqrt{\vphantom{x^2}(1+a)\left(1+(1+b)(1+c)\right)}.Ще докажем, че тази величина винаги е понеa+b+c,\sqrt a+\sqrt b+\sqrt c,и после ще разгледаме случаите на равенство. Имаме(1+a)(1+(1+b)(1+c))≥(1+a)(1+(b+c)2)≥(a+b+c)2.\begin{aligned} (1+a)\left(1+(1+b)(1+c)\right) &\ge (1+a)\left(1+(\sqrt b+\sqrt c)^2\right)\\ &\ge \left(\sqrt a+\sqrt b+\sqrt c\right)^2. \end{aligned}Първото неравенство е еквивалентно на (x2bc−1)2≥0(\sqrt{\vphantom{x^2}bc}-1)^2\ge0, а второто - на(a(b+c)−1)2≥0.\left(\sqrt a(\sqrt b+\sqrt c)-1\right)^2\ge0.Следователно даденото равенство е възможно точно когато едновременноbc=1bc=1иa=1(b+c)2.a=\frac{1}{(\sqrt b+\sqrt c)^2}.Нека c=t2c=t^2 за t>0t\gt{}0. Тогава b=t−2b=t^{-2} иa=1(t+t−1)2=(tt2+1)2.a=\frac{1}{(t+t^{-1})^2}=\left(\frac{t}{t^2+1}\right)^2.Значи всички решения са пермутациите на тройките(x,y,z)=(1+(tt2+1)2,1+1t2,1+t2),t>0.(x,y,z)=\left(1+\left(\frac{t}{t^2+1}\right)^2, 1+\frac{1}{t^2}, 1+t^2\right),\qquad t\gt{}0.Лесно се проверява, че за всяка такава тройка и всяка нейна пермутация равенството в задачата наистина е изпълнено.
Отвори задачатаEvan Chen VONVON JMO 2013/6Условие — източник