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

Evan Chen / JMO Solution Notes

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

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

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

2025

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Да се докаже, че ако f:Z→Zf:\mathbb Z\to\mathbb Z е произволна функция, то има безкрайно много цели числа cc, за които функцията g(x)=f(x)+cxg(x)=f(x)+cx не е биекция.
РешениеДа допуснем противното. Тогава съществува крайно множество SS от лоши стойности на cc, такова че f(x)+cxf(x)+cx е биекция за всяко c∉Sc\notin S. Първото наблюдение е, че всяка последователна разлика на стойности на ff трябва да е лоша. Наистина, ако вземем c=f(t)−f(t+1),c=f(t)-f(t+1), то функцията x↦f(x)+cxx\mapsto f(x)+cx приема една и съща стойност при x=tx=t и при x=t+1x=t+1, защото f(t)+ct=f(t+1)+c(t+1).f(t)+ct=f(t+1)+c(t+1). Следователно тя не може да бъде инективна, а значи този cc принадлежи на SS. Значи всички числа f(0)−f(1), f(1)−f(2), f(2)−f(3),…f(0)-f(1),\ f(1)-f(2),\ f(2)-f(3),\ldots са в крайното множество SS. Избираме цяло число MM така, че M>∣s∣M\gt{}|s| за всяко s∈Ss\in S. Тогава M+100∉SM+100\notin S, така че по допускане функцията h(x)=f(x)+(M+100)xh(x)=f(x)+(M+100)x трябва да е биекция. Но за всяко цяло xx имаме h(x+1)−h(x)=f(x+1)−f(x)+M+100.h(x+1)-h(x)=f(x+1)-f(x)+M+100. Понеже f(x)−f(x+1)∈Sf(x)-f(x+1)\in S, получаваме f(x+1)−f(x)>−Mf(x+1)-f(x)\gt{}-M, а значи h(x+1)−h(x)>100h(x+1)-h(x)\gt{}100. Следователно hh е строго растяща и прескача цели интервали от цели числа между съседните си стойности; в частност не е сюрективна върху Z\mathbb Z. Това противоречи на предположението, че hh е биекция. Следователно лошите стойности на cc са безкрайно много.
Отвори задачатаEvan Chen VONVON JMO 2025/1Условие — източник

Задача 2

Пълен запис
Условие
Нека kk и dd са фиксирани положителни цели числа. Да се докаже, че за всяко достатъчно голямо нечетно положително цяло число nn всички цифри в записа на nkn^k в бройна система с основа 2n2n са по-големи от dd.
РешениеНека 1≤ℓ≤k1\le\ell\le k. Ще разгледаме най-десните ℓ\ell цифри на nkn^k в основа 2n2n, тоест остатъка rℓr_\ell на nkn^k при деление на (2n)ℓ(2n)^\ell. Твърдим, че съществува нечетно цяло число cℓc_\ell с 1≤cℓ≤2ℓ−11\le c_\ell\le 2^\ell-1 такова, че rℓ=cℓnℓ.r_\ell=c_\ell n^\ell. Действително остатъкът rℓr_\ell е кратен на nℓn^\ell, а след деление на nℓn^\ell трябва да изберем клас по модул 2ℓ2^\ell. Понеже nn е нечетно, китайската теорема за остатъците дава точно класа cℓ≡nk−ℓ(mod2ℓ),c_\ell\equiv n^{k-\ell}\pmod{2^\ell}, който е нечетен. Сега ще покажем, че прагът n≥(d+1)2k−1n\ge(d+1)2^{k-1} е достатъчен. При такова nn числото nkn^k има точно kk цифри в основа 2n2n, защото (2n)k−1≤nk<(2n)k.(2n)^{k-1}\le n^k\lt{}(2n)^k. За всяко ℓ=1,2,…,k\ell=1,2,\ldots,k имаме rℓ=cℓnℓ≥nℓ≥r_\ell=c_\ell n^\ell\ge n^\ell\ge(d+1)2ℓ−1nℓ−1=(d+1)(2n)ℓ−1.(d+1)2^{\ell-1}n^{\ell-1}=(d+1)(2n)^{\ell-1}. Но ℓ\ell-тата цифра отдясно е цялата част на rℓ/(2n)ℓ−1r_\ell/(2n)^{\ell-1}, следователно тя е поне d+1d+1. Това важи за всички kk цифри на nkn^k, така че всяка от тях е по-голяма от dd.
Отвори задачатаEvan Chen VONVON JMO 2025/2Условие — източник

Задача 3

Пълен запис
Условие
Нека mm и nn са положителни цели числа, а RR е правоъгълна дъска 2m×2n2m\times2n от единични квадратчета. Домино е правоъгълник 1×21\times2 или 2×12\times1. Стълбичен път е път от долния ляв ъгъл на RR до горния десен ъгъл на RR, съставен от точно 2m+2n2m+2n страни на квадратчета и движещ се само нагоре и надясно. В зависимост от mm и nn да се намери броят на стълбичните пътища, които разделят RR на две подмножества от квадратчета, всяко от които може да бъде покрито с домина.
РешениеОтговорът е (m+nm)2.\binom{m+n}{m}^2. Оцветяваме дъската шахматно. За област от квадратчета, която може да се покрие с домина, е необходимо броят на черните и белите квадратчета в нея да е еднакъв. За стълбичните области, които се получават под такъв път, това условие е и достатъчно. Доказателството е индукция по броя квадратчета. Ако стълбицата не е празна и е балансирана, то поне една от следните локални операции е възможна: последните две колони имат еднаква височина и се покриват заедно; две съседни колони се различават по височина с поне две и се премахва горна лента от двойки квадратчета над по-ниската част; първите две редици имат еднаква дължина и се покриват заедно; или аналогична хоризонтална лента се премахва при две съседни редици с разлика поне две. Всяка операция покрива домино-покриваема част и оставя отново балансирана стълбица. Ако никоя операция не е възможна, височините трябва да са 1,2,…,t1,2,\ldots,t, а такава стълбица не е балансирана, освен при t=0t=0. Това доказва критерия. Следователно търсим точно пътищата, за които областта под пътя има равен брой черни и бели квадратчета; понеже цялата дъска 2m×2n2m\times2n е балансирана, тогава и другата област е балансирана. Нека височините на колоните под пътя са 0≤h1≤h2≤⋯≤h2n≤2m.0\le h_1\le h_2\le\cdots\le h_{2n}\le2m. Ако долното ляво квадратче е черно, тогава колона ii допринася излишък от един черен квадрат точно когато hih_i е нечетно и ii е нечетно, и излишък от един бял квадрат точно когато hih_i е нечетно и ii е четно. Значи стълбицата е балансирана точно когато сред индексите ii с нечетно hih_i има еднакво много четни и нечетни. Поставяме ti=hi+i.t_i=h_i+i. Тогава 1≤t1<t2<⋯<t2n≤2m+2n,1\le t_1\lt{}t_2\lt{}\cdots\lt{}t_{2n}\le2m+2n, и условието за баланс става: множеството {t1,t2,…,t2n}\{t_1,t_2,\ldots,t_{2n}\} има еднакво много четни и нечетни елементи. В интервала от 11 до 2m+2n2m+2n има m+nm+n четни и m+nm+n нечетни числа. Трябва да изберем nn от четните и nn от нечетните, затова броят е (m+nn)2=(m+nm)2.\binom{m+n}{n}^2=\binom{m+n}{m}^2.
Отвори задачатаEvan Chen VONVON JMO 2025/3Условие — източник

Задача 4

Пълен запис
Условие
Нека nn е положително цяло число и нека a0≥a1≥⋯≥an≥0a_0\ge a_1\ge\cdots\ge a_n\ge0 са цели числа. Да се докаже, че ∑i=0ni(ai2)≤12(a0+a1+⋯+an2).\sum_{i=0}^n i\binom{a_i}{2}\le\frac12\binom{a_0+a_1+\cdots+a_n}{2}.
РешениеЩе докажем твърдението с индукция по nn, като случаят n=0n=0 е празен. Нека A=a0+a1+⋯+an−1.A=a_0+a_1+\cdots+a_{n-1}. По индукционното предположение за първите nn члена имаме ∑i=0n−1i(ai2)≤12(A2).\sum_{i=0}^{n-1}i\binom{a_i}{2}\le\frac12\binom{A}{2}. Следователно е достатъчно да докажем, че добавянето на последния член не увеличава лявата страна с повече от позволеното увеличение на дясната страна, тоест n(an2)≤12((A+an2)−(A2)).n\binom{a_n}{2}\le\frac12\left(\binom{A+a_n}{2}-\binom A2\right). Умножаваме по 22 и разкриваме скобите; това е равносилно на 2n(an2−an)≤an2+an(2A−1).2n(a_n^2-a_n)\le a_n^2+a_n(2A-1). След прехвърляне на всички членове вдясно получаваме 0≤2an(A−nan)+an(an+2n−1).0\le2a_n(A-na_n)+a_n(a_n+2n-1). Последното е очевидно, защото a0,a1,…,an−1≥ana_0,a_1,\ldots,a_{n-1}\ge a_n, следователно A≥nanA\ge na_n, а освен това an≥0a_n\ge0 и an+2n−1≥0a_n+2n-1\ge0. Индукцията е завършена.
Отвори задачатаEvan Chen VONVON JMO 2025/4Условие — източник

Задача 6

Пълен запис
Условие
Нека SS е множество от цели числа със следните свойства: {1,2,…,2025}⊆S\{1,2,\ldots,2025\}\subseteq S; ако a,b∈Sa,b\in S и gcd⁡(a,b)=1\gcd(a,b)=1, то ab∈Sab\in S; ако s+1s+1 е съставно за някое s∈Ss\in S, тогава всички положителни делители на s+1s+1 са в SS. Да се докаже, че SS съдържа всички положителни цели числа.
РешениеЩе докажем с индукция по NN, че {1,2,…,N}⊆S\{1,2,\ldots,N\}\subseteq S. Началото N≤2025N\le2025 е дадено. Нека вече всички положителни цели числа до NN са в SS и искаме да докажем, че N+1∈SN+1\in S. Ако N+1N+1 е съставно, тогава N∈SN\in S и третото условие, приложено към s=Ns=N, директно дава N+1∈SN+1\in S. Остава случаят N+1=pN+1=p, където p>2025p\gt{}2025 е просто число. Ще наричаме едно число добро, ако всяка проста степен в каноничното му разлагане е по-малка от pp. По индукционното предположение всички тези прости степени са в SS, а понеже са две по две взаимно прости, второто условие показва, че всяко добро число е в SS. Разглеждаме три случая. Първо, нека нито p−1p-1, нито p+1p+1 е степен на 22. Тогава s=p2−1=(p−1)(p+1)s=p^2-1=(p-1)(p+1) е добро: всяка нечетна проста степен в разлагането му дели точно едно от p−1p-1 и p+1p+1, а най-голямата степен на 22, която го дели, също е по-малка от pp, защото единият от двата съседни четни множителя има само един множител 22, а другият не е чиста степен на 22. Следователно s∈Ss\in S, а понеже s+1=p2s+1=p^2 е съставно, третото условие дава p∈Sp\in S. Второ, нека p+1p+1 е степен на 22, тоест p=2q−1p=2^q-1. За p>2025p\gt{}2025 можем да приемем, че q≥11q\ge11 е нечетно. Числото s0=2q+1−1=(2(q+1)/2−1)(2(q+1)/2+1)s_0=2^{q+1}-1=\left(2^{(q+1)/2}-1\right)\left(2^{(q+1)/2}+1\right) е добро, защото двата му множителя са взаимно прости и по-малки от pp. Значи s0∈Ss_0\in S, а от s0+1=2q+1s_0+1=2^{q+1} получаваме 2q+1∈S2^{q+1}\in S. Сега в p2−1=(p−1)(p+1)p^2-1=(p-1)(p+1) най-голямата степен на 22 е точно 2q+12^{q+1}, а всички останали прости степени са по-малки от pp; чрез второто условие заключаваме, че p2−1∈Sp^2-1\in S. Отново (p2−1)+1=p2(p^2-1)+1=p^2 е съставно, следователно p∈Sp\in S. Трето, нека p−1p-1 е степен на 22. Тогава pp е просто число на Ферма, така че p≡2(mod3)p\equiv2\pmod3. Поставяме s=2p−1.s=2p-1. Имаме s≡0(mod3)s\equiv0\pmod3. Освен това ss не е степен на 33: иначе от p=22e+1p=2^{2^e}+1 бихме получили 22e+1+1=3r,2^{2^e+1}+1=3^r, което за p>2025p\gt{}2025 е изключено от теоремата на Михайлеску, известна и като теоремата на Каталан. Понеже s<2ps\lt{}2p, всяка проста степен в разлагането на ss е по-малка от pp, освен ако самото ss не е проста степен; последното току-що изключихме. Значи ss е добро и s∈Ss\in S. Но s+1=2ps+1=2p е съставно, така че третото условие дава p∈Sp\in S. Във всички случаи N+1=pN+1=p принадлежи на SS, което завършва индукцията и доказва, че SS съдържа всички положителни цели числа.
Отвори задачатаEvan Chen VONVON JMO 2025/6Условие — източник