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

Evan Chen / JMO Solution Notes

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

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

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

2020

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

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

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

11-12

3 задачи

Задача 1

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число. Карл има nn книги, подредени на лавица. Всяка книга има височина и ширина. Няма две книги с еднаква височина и няма две книги с еднаква ширина. Първоначално книгите са подредени отляво надясно по нарастваща височина. Един ход се състои в това Карл да избере две съседни книги, при които лявата книга е по-широка и по-ниска от дясната, и да разменя местата им. Карл повтаря това, докато повече не може да направи ход. Докажете, че независимо как Карл избира ходовете си, процесът спира след краен брой ходове и тогава книгите са подредени отляво надясно по нарастваща ширина.
РешениеЩе казваме, че двойка книги (A,B)(A,B) е инвертирана по височина, ако AA е вляво от BB и AA е по-висока от BB. Аналогично дефинираме двойки, инвертирани по ширина. Всеки ход намалява броя на двойките, инвертирани по ширина: при размяна на две съседни книги се променя само техният взаимен ред, а избраната двойка вече не е инвертирана по ширина. Следователно процесът завършва, понеже първоначално има най-много (n2)\binom n2 такива двойки. Сега разглеждаме момент, в който повече ходове не са възможни. Да допуснем противното: има две съседни книги (A,B)(A,B), които все още са инвертирани по ширина, тоест AA е вляво от BB и е по-широка от нея. Понеже ход вече не е възможен, тази двойка трябва да е инвертирана и по височина, тоест AA е по-висока от BB. Първоначално обаче книгите са били подредени по нарастваща височина, така че BB е била вляво от AA. За да се окажат в реда A,BA,B, двете книги някога трябва да са били разменени една с друга. Но когато са били в реда B,AB,A, лявата книга BB е била по-ниска и по-тясна от AA, така че ходът за размяна на тази двойка не е бил разрешен. Противоречие. Значи в крайното положение няма инверсии по ширина, т.е. книгите са подредени по нарастваща ширина.
Отвори задачатаEvan Chen VONVON JMO 2020/1Условие — източник

Задача 5

Пълен запис
Условие
Нека (a1,b1),(a2,b2),…,(a100,b100)(a_1,b_1),(a_2,b_2),\dots,(a_{100},b_{100}) са различни наредени двойки от неотрицателни цели числа. Нека NN е броят на двойките цели числа (i,j)(i,j), за които 1≤i<j≤1001\le i\lt{}j\le100 и∣aibj−ajbi∣=1.\left\lvert a_ib_j-a_jb_i\right\rvert=1.Да се намери най-голямата възможна стойност на NN при всички избори на тези 100100 наредени двойки.
РешениеОтговорът е 197197. По-общо, ако числото 100100 се замени с произволно n≥2n\ge2, отговорът е 2n−32n-3. Нека Pi=(ai,bi)P_i=(a_i,b_i) е точка в координатната равнина, а O=(0,0)O=(0,0). Условието ∣aibj−ajbi∣=1|a_ib_j-a_jb_i|=1 означава, че триъгълникът OPiPjOP_iP_j има лице 12\frac12. Ще наричаме такъв триъгълник добър. Първо даваме конструкция за 197197 добри триъгълника. Вземаме точките(1,0),(1,1),(2,1),(3,1),…,(99,1).(1,0),(1,1),(2,1),(3,1),\dots,(99,1).O(1,0)(1,1)(2,1)(3,1)(4,1)...Има 9898 добри триъгълника с върхове (0,0)(0,0), (k,1)(k,1) и (k+1,1)(k+1,1) за k=1,2,…,98k=1,2,\dots,98, както и 9999 добри триъгълника с върхове (0,0)(0,0), (1,0)(1,0) и (k,1)(k,1) за k=1,2,…,99k=1,2,\dots,99. Общо получаваме 98+99=19798+99=197. Остава да докажем, че повече не може. Ще докажем по индукция по nn, че за nn точки броят на добрите триъгълници е най-много 2n−32n-3. Базата n=2n=2 е очевидна. Нека P=Pn=(a,b)P=P_n=(a,b) е точка, която е най-далеч от OO измежду всички избрани точки. Твърдим, че PP участва в най-много два добри триъгълника. Ако gcd⁡(a,b)>1\gcd(a,b)\gt{}1, тогава PP не участва в нито един добър триъгълник, защото всеки общ делител на aa и bb дели и детерминантата ay−bxay-bx за всяка целочислена точка Q=(x,y)Q=(x,y). Нека сега gcd⁡(a,b)=1\gcd(a,b)=1. Множеството от точките Q=(x,y)Q=(x,y), за които [OPQ]=12[OPQ]=\frac12, е обединението на двете правиay−bx=1иay−bx=−1.ay-bx=1\qquad\text{и}\qquad ay-bx=-1.Те са успоредни на OPOP. Върху всяка от тези прави целочислените точки се получават една от друга чрез прибавяне или изваждане на вектора (a,b)(a,b).OP=(a,b)(u,v)(u',v')ay-bx=1ay-bx=-1Понеже всички избрани точки са в първи квадрант и PP е най-далеч от OO, върху всяка от двете прави може да има най-много една избрана точка: ако две неотрицателни целочислени точки на една и съща такава права се различават с (a,b)(a,b), то по-далечната е строго по-далеч от OO от самата точка P=(a,b)P=(a,b), което противоречи на избора на PP. Следователно PP участва в най-много два добри триъгълника. Изтриваме точката PP. По индукционната хипотеза останалите n−1n-1 точки дават най-много2(n−1)−32(n-1)-3добри триъгълника, а изтритата точка е участвала в най-много още два. Затова общият брой е най-много2(n−1)−3+2=2n−3.2(n-1)-3+2=2n-3.За n=100n=100 това дава горна граница 197197, а конструкцията по-горе я достига.
Отвори задачатаEvan Chen VONVON JMO 2020/5Условие — източник

Задача 6

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число. Нека P(x1,x2,…,xn)P(x_1,x_2,\ldots,x_n) е неконстантен полином на nn променливи с реални коефициенти. Да се предположи, че PP се занулява винаги когато две от променливите му са равни. Докажете, че PP има поне n!n! едночлена.
РешениеЩе докажем твърдението с индукция по nn. Първо отбелязваме следния факт. Твърдение. За никои 1≤i<j≤n1\le i\lt{}j\le n полиномът PP няма едночлен, в който не участват едновременно и xix_i, и xjx_j. Наистина, ако положим xi=xj=0x_i=x_j=0, полиномът трябва да стане тъждествено нула като полином в останалите n−2n-2 променливи, защото се занулява за всички реални стойности на тези променливи. Следователно след събирането на подобните членове не може да остане едночлен, който не съдържа нито xix_i, нито xjx_j. Базата n=2n=2 е ясна: неконстантен полином, който се занулява при x1=x2x_1=x_2, има поне два едночлена. Нека n≥3n\ge3 и твърдението вече е доказано за n−1n-1 променливи. Можем да приемем, че PP не се дели на никоя от променливите x1,x2,…,xnx_1,x_2,\ldots,x_n; ако всички едночлени съдържат някоя променлива, можем да разделим на нея, без да променим броя на едночлените и без да загубим свойството за зануляване върху равенствата xi=xjx_i=x_j. Сега за всяко r=1,2,…,nr=1,2,\ldots,n разглеждаме полинома, получен от PP след полагане xr=0x_r=0. Той не е тъждествено нула, защото xrx_r не дели PP, и пак се занулява винаги когато две от останалите му променливи са равни. По индукционното предположение той има поне (n−1)!(n-1)! едночлена. Остава да забележим, че едночлените, които се виждат при различни избори на rr, идват от различни едночлени на първоначалния полином. Ако един и същ едночлен на PP оцеляваше едновременно при xi=0x_i=0 и при xj=0x_j=0, той нямаше да съдържа нито xix_i, нито xjx_j, което противоречи на твърдението. Следователно PP има понеn⋅(n−1)≠n!n\cdot(n-1)\neq{}n!едночлена. Границата е точна, например за полинома на Вандермонд∏1≤i<j≤n(xi−xj),\prod_{1\le i\lt{}j\le n}(x_i-x_j),който има точно n!n! едночлена.
Отвори задачатаEvan Chen VONVON JMO 2020/6Условие — източник