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

Evan Chen / JMO Solution Notes

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

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

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

2016

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

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

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

11-12

4 задачи

Задача 2

Пълен запис
Условие
Да се докаже, че съществува положително цяло число n<106n\lt{}10^6, за което десетичният запис на 5n5^n съдържа шест последователни нули.
РешениеЩе построим такова nn, като контролираме последните 2020 цифри на 5n5^n. Некаn=20+219.n=20+2^{19}.Тогава n<106n\lt{}10^6. Ще покажем, че 5n5^n има същите последни 2020 цифри като 5205^{20}. По модул 5205^{20} и двете числа са 00. По модул 2202^{20}, от теоремата на Ойлер имаме 5219≡1(mod220)5^{2^{19}}\equiv1\pmod{2^{20}}, защото φ(220)=219\varphi(2^{20})=2^{19} и gcd⁡(5,220)=1\gcd(5,2^{20})=1. Следователно5n=520⋅5219≡520(mod220).5^n=5^{20}\cdot5^{2^{19}}\equiv5^{20}\pmod{2^{20}}.С китайската теорема за остатъците получаваме5n≡520(mod1020).5^n\equiv5^{20}\pmod{10^{20}}.Но520=953674316406255^{20}=95367431640625има 1414 цифри. Значи последните 2020 цифри на 5n5^n са00000095367431640625,00000095367431640625,което съдържа шест последователни нули. Това доказва твърдението.
Отвори задачатаEvan Chen VONVON JMO 2016/2Условие — източник

Задача 3

Пълен запис
Условие
Нека X1X_1, X2X_2, …\ldots, X100X_{100} са редица от две по две различни непразни подмножества на множество SS. За всеки две съседни множества XiX_i и Xi+1X_{i+1} е изпълнено, че те са несечащи се и обединението им не е цялото множество SS, тоестXi∩Xi+1=∅иXi∪Xi+1≠SX_i\cap X_{i+1}=\varnothing\qquad\text{и}\qquad X_i\cup X_{i+1}\ne Sза всички i=1,2,…,99i=1,2,\ldots,99. Да се намери най-малкият възможен брой елементи на SS.
РешениеОтговорът е 88. Първо ще докажем, че ∣S∣≥8|S|\ge8 е необходимо. Очевидно трябва да има поне 100100 различни непразни подмножества, така че ∣S∣≥7|S|\ge7. Ще покажем, че ∣S∣=7|S|=7 все още не стига. Нека S={1,2,…,7}S=\{1,2,\ldots,7\} и да имаме редица с исканите свойства. Всяко подмножество с поне 44 елемента може да стои до множество с най-много 22 елемента: ако съседното множество има 33 или повече елемента и е несечащо се с него, тогава обединението би било цялото SS. Подмножества с най-много 22 елемента има(71)+(72)=28.\binom71+\binom72=28.Следователно в редицата може да има най-много 2929 множества с поне 44 елемента. Освен това множествата с точно 33 елемента са само (73)=35\binom73=35. Значи общият брой членове на такава редица е най-много29+28+35=92<100,29+28+35=92\lt{}100,противоречие. Значи ∣S∣≥8|S|\ge8. Остава да построим пример при ∣S∣=8|S|=8. Ще дадем по-обща индуктивна конструкция. За всяко n≥4n\ge4 ще построим редица от 2n−1+12^{n-1}+1 подмножества на {1,2,…,n}\{1,2,\ldots,n\} със същите свойства. За n=4n=4 работи редицата34, 1, 23, 4, 12, 3, 14, 2, 13,34,\ 1,\ 23,\ 4,\ 12,\ 3,\ 14,\ 2,\ 13,където например 3434 означава множеството {3,4}\{3,4\}. Нека вече имаме такава редица за {1,2,…,n}\{1,2,\ldots,n\}. Премахваме крайния й член, така че дължината да стане четна, правим две копия на останалата редица и ги слепваме с ∅\varnothing между тях. После добавяме новия елемент n+1n+1 към множествата на редуващи се позиции, започвайки от първата позиция. Лесно се проверява, че съседните множества в новата редица пак са несечащи се и обединението им не е цялото множество: в старите съседства това следва от индукционното предположение, а при слепването празното множество не създава проблем; добавянето на n+1n+1 в редуващи се позиции запазва несечението на всяка съседна двойка и оставя във всяка двойка поне един липсващ елемент. Дължината става2⋅2n−1+1=2n+1.2\cdot2^{n-1}+1=2^n+1.При n=8n=8 получаваме редица с 27+1=1292^7+1=129 различни непразни подмножества. Вземайки първите 100100 от тях, получаваме търсената редица. Следователно най-малкият възможен размер на SS е 88.
Отвори задачатаEvan Chen VONVON JMO 2016/3Условие — източник

Задача 4

Пълен запис
Условие
Да се намери най-малкото положително цяло число NN със следното свойство: ако от множеството {1,2,…,N}\{1,2,\ldots,N\} премахнем произволни 20162016 числа, тогава сред останалите числа винаги могат да се изберат 20162016 различни числа със сбор NN.
РешениеОтговорът еN=2017+2018+⋯+4032=N=2017+2018+\cdots+4032=1008⋅6049=6097392.1008\cdot6049=6097392.Първо ще докажем, че по-малко NN не стига. Ако премахнем числата 1,2,…,20161,2,\ldots,2016, тогава най-малкият възможен сбор на 20162016 различни останали числа е2017+2018+⋯+4032.2017+2018+\cdots+4032.Следователно всяко работещо NN трябва да е поне тази стойност. Остава да докажем, че това NN наистина работи. Разглеждаме двойките(1,6048),(2,6047),…,(3024,3025).(1,6048),(2,6047),\ldots,(3024,3025).Всяка от тях има сбор 60496049, а всички използвани числа са не по-големи от 6048<N6048\lt{}N. Премахването на 20162016 числа може да развали най-много 20162016 от тези 30243024 двойки, защото едно премахнато число принадлежи на най-много една двойка. Значи остават поне 3024−2016=10083024-2016=1008 непокътнати двойки. Избираме числата от тези 10081008 двойки. Получаваме точно 20162016 различни останали числа, а сборът им е1008⋅6049=N.1008\cdot6049=N.Така посоченото NN има исканото свойство и по долната граница е минимално.
Отвори задачатаEvan Chen VONVON JMO 2016/4Условие — източник

Задача 6

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb R\to\mathbb R такива, че за всички реални числа xx и yy е изпълнено(f(x)+xy)f(x−3y)+(f(y)+xy)f(3x−y)=(f(x)+xy)f(x-3y)+(f(y)+xy)f(3x-y)=f(x+y)2.f(x+y)^2.
РешениеДвете решения саf(x)≡0иf(x)=x2.f(x)\equiv0\qquad\text{и}\qquad f(x)=x^2.Лесна проверка показва, че и двете функции удовлетворяват уравнението. Ще докажем, че други няма. Поставяме x=y=0x=y=0 и получаваме f(0)=0f(0)=0. После при x=0x=0 имамеf(y)f(−y)=f(y)2.f(y)f(-y)=f(y)^2.След замяна на yy с −y-y следва и f(−y)f(y)=f(−y)2f(-y)f(y)=f(-y)^2. От тези две равенства получаваме f(y)=f(−y)f(y)=f(-y) за всяко yy, тоест ff е четна. Сега поставяме y=−xy=-x. Тъй като ff е четна и f(0)=0f(0)=0, получаваме2(f(x)−x2)f(4x)=0.2(f(x)-x^2)f(4x)=0.Следователно за всяко реално xx е вярно, чеf(x)=x2илиf(4x)=0.(1)f(x)=x^2\quad\text{или}\quad f(4x)=0.\tag{1}Ще използваме още едно свойство на нулите. Поставяме (x,y)=(3t,t)(x,y)=(3t,t). Понеже f(0)=0f(0)=0, уравнението става(f(t)+3t2)f(8t)=f(4t)2.(2)(f(t)+3t^2)f(8t)=f(4t)^2.\tag{2}Оттук f(4t)≠0f(4t)\ne0 влече f(8t)≠0f(8t)\ne0, тоест f(z)≠0f(z)\ne0 влече f(2z)≠0f(2z)\ne0. Еквивалентно, ако f(2z)=0f(2z)=0, то f(z)=0f(z)=0. За обратната посока допускаме f(8t)≠0f(8t)\ne0. От (1), приложено за 2t2t, следва f(2t)=4t2f(2t)=4t^2; при t≠0t\ne0 това е ненулево, а вече доказаната посока дава f(4t)≠0f(4t)\ne0. Следователно f(4t)=0f(4t)=0 влече f(8t)=0f(8t)=0. Значи за всяко реално zzf(z)=0⟺f(2z)=0.(3)f(z)=0\quad\Longleftrightarrow\quad f(2z)=0.\tag{3}От (1) и (3) следва, че за всяко xx имаме само две възможности:f(x)=x2илиf(x)=0.f(x)=x^2\quad\text{или}\quad f(x)=0.Ако няма ненулево aa с f(a)=0f(a)=0, то веднага f(x)=x2f(x)=x^2 за всички x≠0x\ne0, а и f(0)=0f(0)=0; значи f(x)=x2f(x)=x^2. Остава случаят, когато съществува a≠0a\ne0 с f(a)=0f(a)=0. От (3) получаваме f(2na)=0f(2^n a)=0 за всяко n≥0n\ge0. Нека b>0b\gt{}0 е произволно. По четност можем да приемем a>0a\gt{}0. Избираме nn така, че c=2na>bc=2^n a\gt{}b, и поставямеx=3c+b4,y=c−b4.x=\frac{3c+b}{4},\qquad y=\frac{c-b}{4}.Тогава x,y>0x,y\gt{}0, x−3y=bx-3y=b, x+y=cx+y=c и 3x−y=2c+b3x-y=2c+b. В уравнението дясната страна е f(c)2=0f(c)^2=0. От предишния абзац всички стойности на ff са неотрицателни, а f(x)+xy>0f(x)+xy\gt{}0 и f(y)+xy>0f(y)+xy\gt{}0. Следователно(f(x)+xy)f(b)+(f(y)+xy)f(2c+b)=0(f(x)+xy)f(b)+(f(y)+xy)f(2c+b)=0е възможно само ако f(b)=0f(b)=0. Значи ff занулява всяко положително bb, а по четност и всяко реално bb. Тогава f≡0f\equiv0. Получихме точно двете посочени функции.
Отвори задачатаEvan Chen VONVON JMO 2016/6Условие — източник