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

Evan Chen / JMO Solution Notes

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

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

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

2019

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
В редица са подредени a+ba+b купи, номерирани от 11 до a+ba+b, където aa и bb са дадени положителни цели числа. Първоначално във всяка от първите aa купи има по една ябълка, а във всяка от последните bb купи има по една круша. Един допустим ход се състои в това да преместим ябълка от купа ii в купа i+1i+1 и круша от купа jj в купа j−1j-1, при условие че i−ji-j е четно. Позволено е в една и съща купа едновременно да има няколко плода. Целта е накрая във всяка от първите bb купи да има по една круша, а във всяка от последните aa купи да има по една ябълка. Докажете, че това е възможно тогава и само тогава, когато произведението abab е четно.
РешениеПърво ще докажем, че ако abab е четно, целта е постижима. Доказваме това с индукция по a+ba+b, като допускаме междинно и случаите с някой от параметрите равен на 00. Ако min⁡(a,b)=0\min(a,b)=0, няма какво да се доказва. Ако min⁡(a,b)=1\min(a,b)=1, например a=1a=1, тогава bb е четно. Можем да разменим единствената най-лява ябълка с най-дясната круша, като работим само с тези два плода: във всеки момент разликата между текущите им позиции има правилната четност. Нека сега min⁡(a,b)≥2\min(a,b)\ge2. Ако a+ba+b е нечетно, разменяме най-лявата ябълка с най-дясната круша, като пак използваме само тези два плода. Това свежда задачата до параметрите (a−1,b−1)(a-1,b-1), а поне един от тях е четен, така че прилагаме индукцията. Ако пък a+ba+b е четно, то понеже abab е четно, числата aa и bb са четни. Тогава разменяме ябълката в купа 11 с крушата в купа a+b−1a+b-1, а ябълката в купа 22 с крушата в купа a+ba+b. След тези размени оставаме със задачата за (a−2,b−2)(a-2,b-2), която също е възможна по индукция. Остава да докажем невъзможността, когато abab е нечетно. НекаX=броят на ябълките в купи с нечетни номера,X=\text{броят на ябълките в купи с нечетни номера},Y=броят на крушите в купи с нечетни номера.Y=\text{броят на крушите в купи с нечетни номера}.При всеки допустим ход двете преместени купи имат еднаква четност преди хода и еднаква четност след него, така че разликата X−YX-Y не се променя. Ако aa и bb са нечетни, първоначалноX=a+12,Y=b−12,X=\frac{a+1}{2},\qquad Y=\frac{b-1}{2},а в желаната крайна конфигурацияX=a−12,Y=b+12.X=\frac{a-1}{2},\qquad Y=\frac{b+1}{2}.Следователно X−YX-Y би се променило с 22, което е невъзможно. Значи целта е постижима точно когато abab е четно.
Отвори задачатаEvan Chen VONVON JMO 2019/1Условие — източник

Задача 2

Пълен запис
Условие
За кои двойки цели числа (a,b)(a,b) съществуват функции f ⁣:Z→Zf\colon\mathbb Z\to\mathbb Z и g ⁣:Z→Zg\colon\mathbb Z\to\mathbb Z, за коитоf(g(x))=x+aиg(f(x))=x+bf(g(x))=x+a\qquad\text{и}\qquad g(f(x))=x+bза всяко цяло число xx?
РешениеОтговорът е: точно когато a=ba=b или a=−ba=-b. Ако a=ba=b, можем да вземем f(x)=x+af(x)=x+a и g(x)=xg(x)=x. Ако a=−ba=-b, можем да вземем f(x)=−x+af(x)=-x+a и g(x)=−xg(x)=-x. И в двата случая проверката е непосредствена. Сега ще докажем, че други възможности няма. Първо, ff и gg са биекции. Сюрективността следва веднага от равенствата f(g(x))=x+af(g(x))=x+a и g(f(x))=x+bg(f(x))=x+b. За инективността, ако f(u)=f(v)f(u)=f(v), тогаваu+b=g(f(u))=g(f(v))=v+b,u+b=g(f(u))=g(f(v))=v+b,тоест u=vu=v; аналогично gg е инективна. Освен това за всяко цяло xx имамеf(x+b)=f(g(f(x)))=f(x)+af(x+b)=f(g(f(x)))=f(x)+aиg(x+a)=g(f(g(x)))=g(x)+b.(1)g(x+a)=g(f(g(x)))=g(x)+b.\tag{1}Ако a=0a=0 или b=0b=0, от (1) и инективността веднага следва, че и другото число е 00, и сме в случая a=ba=b. Нека вече ab≠0ab\ne0. Ще покажем, че ∣a∣=∣b∣|a|=|b|. Ако ∣b∣>∣a∣|b|\gt{}|a|, разглеждаме числатаf(0),f(1),…,f(∣b∣−1)f(0),f(1),\dots,f(|b|-1)по модул ∣a∣|a|. По принципа на Дирихле две от тях, да кажем f(r)f(r) и f(s)f(s) с 0≤r<s<∣b∣0\le r\lt{}s\lt{}|b|, са сравними по модул ∣a∣|a|. Значи f(s)=f(r)+taf(s)=f(r)+ta за някое цяло tt. От първото равенство в (1), приложено многократно и в двете посоки, получавамеf(r+tb)=f(r)+ta=f(s).f(r+tb)=f(r)+ta=f(s).Понеже ff е инективна, следва s=r+tbs=r+tb, което е невъзможно при 0<s−r<∣b∣0\lt{}s-r\lt{}|b|, освен ако t=0t=0, но тогава пак получаваме s=rs=r. Противоречие. Същият аргумент с разменени роли на f,gf,g и a,ba,b изключва случая ∣a∣>∣b∣|a|\gt{}|b|. Следователно ∣a∣=∣b∣|a|=|b|, тоест a=ba=b или a=−ba=-b, както трябваше.
Отвори задачатаEvan Chen VONVON JMO 2019/2Условие — източник

Задача 5

Пълен запис
Условие
Нека nn е неотрицателно цяло число. Да се намери броят на начините да се изберат множества Sij⊆{1,2,…,2n}S_{ij}\subseteq\{1,2,\ldots,2n\} за всички 0≤i≤n0\le i\le n и 0≤j≤n0\le j\le n (не непременно различни), така че - ∣Sij∣=i+j|S_{ij}|=i+j; - Sij⊆SklS_{ij}\subseteq S_{kl} винаги когато 0≤i≤k≤n0\le i\le k\le n и 0≤j≤l≤n0\le j\le l\le n.
РешениеОтговорът е(2n)!⋅2n2.(2n)!\cdot2^{n^2}.Първо отбелязваме, че∅=S00⊊S01⊊⋯⊊S0n⊊S1n⊊⋯⊊Snn=\varnothing=S_{00}\subsetneq S_{01}\subsetneq\cdots\subsetneq S_{0n}\subsetneq S_{1n}\subsetneq\cdots\subsetneq S_{nn}={1,2,…,2n}.\{1,2,\ldots,2n\}.По тази гранична верига елементите се добавят един по един, което дава множител (2n)!(2n)!. След преименуване на елементите можем да приемем, чеS0i={1,2,…,i}иSin={1,2,…,n+i}.S_{0i}=\{1,2,\ldots,i\}\qquad\text{и}\qquad S_{in}=\{1,2,\ldots,n+i\}.Остава да преброим начините за запълване на останалата решетка. Ще докажем по-силно твърдение. Нека TT е избор от клетки, които искаме да запълним, със свойството, че ако една клетка е в TT, то всички клетки над нея и вляво от нея също са в TT; с други думи, TT е диаграма на Юнг. Тогава броят на допустимите запълвания на клетките в TT е точно 2∣T∣2^{|T|}. Доказателството е с индукция по ∣T∣|T|. При ∣T∣=0|T|=0 няма какво да се доказва. Нека добавяме нова ъглова клетка и нека локалната картина е[BCAS],\begin{bmatrix} B & C \\ A & S \end{bmatrix},където AA, BB и CC вече са фиксирани, а SS трябва да се избере. Понеже размерите на множествата се увеличават с по 11 при всяка стъпка нагоре или надясно, можем да запишемB=A∪{x},C=A∪{x,y}B=A\cup\{x\},\qquad C=A\cup\{x,y\}за някои x,y∉Ax,y\notin A. Тогава за SS има точно две възможности:A∪{x}иA∪{y},A\cup\{x\}\qquad\text{и}\qquad A\cup\{y\},и двете удовлетворяват всички нужни включвания и имат правилната големина. Следователно всяка добавена клетка дава независим фактор 22. За пълния квадрат има n2n^2 такива клетки, така че след фиксираната граница получаваме 2n22^{n^2} запълвания. Общият брой е(2n)!⋅2n2.(2n)!\cdot2^{n^2}.
Отвори задачатаEvan Chen VONVON JMO 2019/5Условие — източник

Задача 6

Пълен запис
Условие
Нека mm и nn са взаимно прости положителни цели числа. На дъската са написани числата mn\frac mn и nm\frac nm. Във всеки момент Евън може да избере две от написаните числа xx и yy и да запише или тяхното средно аритметично x+y2\frac{x+y}{2}, или тяхното хармонично средно 2xyx+y\frac{2xy}{x+y}. За кои двойки (m,n)(m,n) Евън може да запише числото 11 след краен брой стъпки?
РешениеТова е възможно тогава и само тогава, когато m+nm+n е степен на 22. Нека q=m/nq=m/n, така че началните числа на дъската са qq и q−1q^{-1}. Първо ще докажем невъзможността. Нека pp е нечетен прост делител на m+nm+n. Тогава p∤mnp\nmid mn, понеже mm и nn са взаимно прости, иq≡q−1≡−1(modp).q\equiv q^{-1}\equiv -1\pmod p.Ако a≡b≡−1(modp)a\equiv b\equiv -1\pmod p, то 2≢0(modp)2\not\equiv0\pmod p и a+b≡−2≢0(modp)a+b\equiv -2\not\equiv0\pmod p, така че и двете средни са определени по модул pp иa+b2≡−1(modp),2aba+b≡−1(modp).\frac{a+b}{2}\equiv -1\pmod p, \qquad \frac{2ab}{a+b}\equiv -1\pmod p.Следователно всички числа, които някога се появят на дъската, остават сравними с −1-1 по модул pp. Числото 11 не може да се появи. Значи m+nm+n не може да има нечетен прост делител. Обратно, нека m+n=2rm+n=2^r. Всъщност ще използваме само средноаритметични операции. Чрез последователно вземане на средни аритметични можем да получим всяка двоична изпъкнала комбинацияaq+bq−12r\frac{a q+b q^{-1}}{2^r}с a+b=2ra+b=2^r: това е просто построяване чрез повтарящо се делене наполовина. Избираме a=na=n и b=mb=m. Тогаваnq+mq−1m+n=n⋅m/n+m⋅n/mm+n=1.\frac{nq+mq^{-1}}{m+n}=\frac{n\cdot m/n+m\cdot n/m}{m+n}=1.Понеже m+n=2rm+n=2^r, това число може да бъде построено с крайно много средноаритметични операции. Следователно търсените двойки са точно тези, за които m+nm+n е степен на 22.
Отвори задачатаEvan Chen VONVON JMO 2019/6Условие — източник