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

Evan Chen / USAMO Solution Notes

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

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

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

2019

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Функция f:N→Nf:\mathbb N\to\mathbb N удовлетворява ff(n)(n)=n2f(f(n))f^{f(n)}(n)=\frac{n^2}{f(f(n))} за всяко положително цяло число nn, където frf^r означава rr-кратно прилагане на ff. Какви са всички възможни стойности на f(1000)f(1000)?
РешениеОтговорът е: всяко четно положително цяло число. По-точно всички решения са функциите, които фиксират всяко нечетно число и върху четните числа действат като произволна инволюция. Така f(1000)f(1000) може да бъде произволно четно число, и всяка такава стойност се реализира. Първо доказваме инективност. Ако f(a)=f(b)f(a)=f(b), то от условието следва a2=ff(a)(a)f(f(a))=ff(b)(b)f(f(b))=b2,a^2=f^{f(a)}(a)f(f(a))=f^{f(b)}(b)f(f(b))=b^2, значи a=ba=b. Сега показваме по индукция, че всяко нечетно nn е неподвижна точка. Ако вече са фиксирани по-малките нечетни числа, в равенството ff(n)(n)f(f(n))=n2f^{f(n)}(n)f(f(n))=n^2 двата множителя не могат да бъдат сред тях поради инективността; следователно и двата са nn. Така f(f(n))=nf(f(n))=n, а ако y=f(n)y=f(n), прилагане на условието към yy дава y2=nyy^2=ny, откъдето y=ny=n. Следователно ff праща четните числа в четни числа. Нека g=f∘fg=f\circ f. Тогава за четно nn имаме gf(n)/2(n)g(n)=n2g^{f(n)/2}(n)g(n)=n^2. Функцията gg вече фиксира нечетните числа и е инективна; същата индукция върху четните nn показва, че g(n)=ng(n)=n. Значи f(f(n))=nf(f(n))=n за всяко nn: върху четните числа ff е инволюция, а върху нечетните е тъждествена. Обратно, всяка такава функция очевидно удовлетворява условието.
Отвори задачатаEvan Chen VONVON USAMO 2019/1Условие — източник

Задача 3

Пълен запис
Условие
Нека KK е множеството от положителните цели числа, чието десетично представяне не съдържа цифрата 77. Да се определят всички многочлени f(x)f(x) с неотрицателни коефициенти, за които f(x)∈Kf(x)\in K за всяко x∈Kx\in K.
РешениеОтговорът е точно очевидното семейство: константните многочлени f(x)=kf(x)=k с k∈Kk\in K, многочлените f(x)=10exf(x)=10^e x и многочлените f(x)=10ex+kf(x)=10^e x+k, където e≥0e\ge0, k∈Kk\in K и 10e>k10^e\gt{}k. Ще наричаме един многочлен стабилен, ако праща всяко число от KK отново в KK. Първата стъпка е редукция до мономи. Ако f(x)=a0+a1x+a2x2+⋯f(x)=a_0+a_1x+a_2x^2+\cdots е стабилен, то всеки моном aixia_i x^i е стабилен: за фиксирано x∈Kx\in K избираме EE толкова голямо, че в десетичния запис на f(10Ex)f(10^E x) приносите a0,a1x,a2x2,…a_0,a_1x,a_2x^2,\ldots да стоят в отделни блокове, разделени с достатъчно нули. Ако някой блок съдържаше цифрата 77, цялото число също щеше да я съдържа. Сега разглеждаме линейния моном cxcx. От x=1x=1 следва c∈Kc\in K. Ако cc не е степен на 1010, според първите му цифри може да се избере число x∈Kx\in K, така че cxcx да започва с цифрата 77: например интервалите 9⋅10e≤c<10⋅10e9\cdot10^e\le c\lt{}10\cdot10^e, 8⋅10e≤c<9⋅10e8\cdot10^e\le c\lt{}9\cdot10^e, 7⋅10e≤c<8⋅10e7\cdot10^e\le c\lt{}8\cdot10^e се разбиват чрез x=8,88,1x=8,88,1, а останалите интервали се покриват с кратките избори 11≤x≤6611\le x\le66 или с число от вида 699…9699\ldots9. Следователно стабилен линеен моном има коефициент 10e10^e. Ако cxdcx^d е стабилен с d>1d\gt{}1, тогава и c(10x+3)dc(10x+3)^d е стабилен. По редукцията неговият линеен член 10dc3d−1x10dc3^{d-1}x трябва също да е стабилен, следователно коефициентът 10dc3d−110dc3^{d-1} трябва да е степен на 1010, което е невъзможно при d>1d\gt{}1. Остава само f(x)=10ex+kf(x)=10^e x+k или константа. Условието 10e>k10^e\gt{}k е точно това, което гарантира, че kk се добавя като долен десетичен блок без пренос към цифрите на xx, и така изброените многочлени наистина работят.
Отвори задачатаEvan Chen VONVON USAMO 2019/3Условие — източник

Задача 4

Пълен запис
Условие
Нека 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)!\,2^{n^2}. Първо фиксираме една гранична верига. Понеже S00=∅S_{00}=\varnothing и Snn={1,2,…,2n}S_{nn}=\{1,2,\ldots,2n\}, по някой монотонен път от долния ляв до горния десен ъгъл елементите се добавят един по един; това дава множителя (2n)!(2n)!. След преименуване можем да приемем, че по горната и дясната граница множествата са стандартните начални сегменти. Остава да запълним вътрешните n2n^2 клетки. По-силното твърдение е следното. Ако изберем форма TT от клетки, затворена нагоре и наляво, тоест диаграма на Юнг, броят на допустимите частични запълвания на тези клетки е 2∣T∣2^{|T|}. Доказваме това с индукция по ∣T∣|T|. При добавяне на нова ъглова клетка имаме локална картина с вече избрани множества A,B,CA,B,C и търсено множество SS, като A⊂B⊂CA\subset B\subset C, ∣B∣=∣A∣+1|B|=|A|+1 и ∣C∣=∣A∣+2|C|=|A|+2. Пишем B=A∪{x}B=A\cup\{x\} и C=A∪{x,y}C=A\cup\{x,y\}. Тогава за SS има точно две възможности: A∪{x}A\cup\{x\} и A∪{y}A\cup\{y\}, и двете запазват всички включвания и правилната големина. Следователно всяка добавена клетка в диаграмата на Юнг дава независим фактор 22. За пълния квадрат имаме ∣T∣=n2|T|=n^2, откъдето получаваме 2n22^{n^2} запълвания след фиксираната граница и общо (2n)! 2n2(2n)!\,2^{n^2}.
Отвори задачатаEvan Chen VONVON USAMO 2019/4Условие — източник

Задача 5

Пълен запис
Условие
Нека 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. Понеже mm и nn са взаимно прости, pp не дели mnmn, и получаваме q≡q−1≡−1(modp)q\equiv q^{-1}\equiv -1\pmod p. Ако две числа aa и bb са −1-1 по модул pp, то и a+b2\frac{a+b}{2}, и 2aba+b\frac{2ab}{a+b} са −1-1 по модул pp, защото 22 и a+b≡−2a+b\equiv -2 са обратими. Следователно всички числа на дъската завинаги остават −1-1 по модул pp, а 11 не може да се появи. Значи m+nm+n няма нечетен прост делител, тоест е степен на 22. Обратно, нека m+n=2rm+n=2^r. Достатъчни са само средноаритметични операции. Чрез последователно вземане на средни аритметични можем да построим всяка двоична изпъкнала комбинация aq+bq−12r\frac{a q+b q^{-1}}{2^r} с a+b=2ra+b=2^r: това е обикновено делене на интервала наполовина, повторено rr пъти. Избираме 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. Така конструкцията е завършена.
Отвори задачатаEvan Chen VONVON USAMO 2019/5Условие — източник

Задача 6

Пълен запис
Условие
Да се намерят всички многочлени PP с реални коефициенти, такива че P(x)yz+P(y)zx+P(z)xy=\frac{P(x)}{yz}+\frac{P(y)}{zx}+\frac{P(z)}{xy}=P(x−y)+P(y−z)+P(z−x)P(x-y)+P(y-z)+P(z-x) за всички ненулеви реални числа x,y,zx,y,z, удовлетворяващи 2xyz=x+y+z2xyz=x+y+z.
РешениеОтговорът е P(x)=c(x2+3),c∈R.P(x)=c(x^2+3),\qquad c\in\mathbb R. Първо умножаваме даденото равенство по xyzxyz и получаваме полиномиалното условие xP(x)+yP(y)+zP(z)=xP(x)+yP(y)+zP(z)=xyz(P(x−y)+P(y−z)+P(z−x))xyz\big(P(x-y)+P(y-z)+P(z-x)\big) винаги когато 2xyz=x+y+z2xyz=x+y+z. Нека разликата между двете страни е Q(x,y,z)Q(x,y,z). Понеже z=x+y2xy−1z=\frac{x+y}{2xy-1} дава реални решения за отворено множество от двойки (x,y)(x,y), рационалната функция, получена след заместването, е тъждествено нула. Следователно същото полиномиално тъждество важи и над комплексните числа за всички тройки с 2xyz=x+y+z2xyz=x+y+z. Вземаме комплексната тройка (x,y,z)=(t,−t,0)(x,y,z)=(t,-t,0). Тя удовлетворява условието и дава tP(t)−tP(−t)=0tP(t)-tP(-t)=0, така че PP е четен многочлен. Сега вземаме y=ix22y=\frac{i}{\sqrt{\vphantom{x^2}2}} и z=−ix22z=-\frac{i}{\sqrt{\vphantom{x^2}2}}; тогава 2xyz=x+y+z2xyz=x+y+z за всяко комплексно xx. От тъждеството и четността на PP следва, че P(x+ix22)+P(x−ix22)−2P(x)P\left(x+\frac{i}{\sqrt{\vphantom{x^2}2}}\right)+P\left(x-\frac{i}{\sqrt{\vphantom{x^2}2}}\right)-2P(x) е константа. Лявата страна е втора крайна разлика на PP с ненулева стъпка, затова ако deg⁡P=d\deg P=d, нейният водещ член има степен d−2d-2. Щом тази разлика е константна, получаваме d≤2d\le2. Понеже PP е четен, имаме P(x)=ax2+bP(x)=ax^2+b. Остава само да наложим условието. При P(x)=ax2+bP(x)=ax^2+b равенството се свежда, след използване на x+y+z=2xyzx+y+z=2xyz, до b=3ab=3a. Така всички решения са P(x)=a(x2+3)P(x)=a(x^2+3). Обратно, пряко заместване показва, че всеки многочлен от този вид работи, защото за 2xyz=x+y+z2xyz=x+y+z е валидно тъждеството x3+y3+z3xyz−(x−y)2−(y−z)2−(z−x)2=3.\frac{x^3+y^3+z^3}{xyz}-(x-y)^2-(y-z)^2-(z-x)^2=3. Това доказва и достатъчността.
Отвори задачатаEvan Chen VONVON USAMO 2019/6Условие — източник