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

Evan Chen / USAMO Solution Notes

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

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

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

2014

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
Нека a,b,c,da,b,c,d са реални числа, за които b−d≥5b-d\ge5, и всички корени x1,x2,x3,x4x_1,x_2,x_3,x_4 на полинома P(x)=x4+ax3+bx2+cx+dP(x)=x^4+ax^3+bx^2+cx+d са реални. Да се намери най-малката възможна стойност на произведението (x12+1)(x22+1)(x32+1)(x42+1).(x_1^2+1)(x_2^2+1)(x_3^2+1)(x_4^2+1).
РешениеОтговорът е 1616. Тази стойност се достига при x1=x2=x3=x4=1x_1=x_2=x_3=x_4=1: тогава произведението е 24=162^4=16, а за полинома (x−1)4(x-1)^4 имаме b=6b=6, d=1d=1, следователно b−d=5b-d=5. Остава да докажем, че по-малка стойност е невъзможна. Ще покажем тъждеството (x12+1)(x22+1)(x32+1)(x42+1)=(x_1^2+1)(x_2^2+1)(x_3^2+1)(x_4^2+1)=(b−d−1)2+(a−c)2.(b-d-1)^2+(a-c)^2. Нека i2=−1i^2=-1. Понеже корените на PP са x1,x2,x3,x4x_1,x_2,x_3,x_4, получаваме ∏j=14(xj2+1)=∏j=14(xj−i)(xj+i)=\prod_{j=1}^4(x_j^2+1)=\prod_{j=1}^4(x_j-i)(x_j+i)=P(i)P(−i)=∣P(i)∣2.P(i)P(-i)=|P(i)|^2. От друга страна P(i)=i4+ai3+bi2+ci+d=(1−b+d)+(c−a)i.P(i)=i^4+ai^3+bi^2+ci+d=(1-b+d)+(c-a)i. Следователно ∣P(i)∣2=(1−b+d)2+(c−a)2=(b−d−1)2+(a−c)2|P(i)|^2=(1-b+d)^2+(c-a)^2=(b-d-1)^2+(a-c)^2, както твърдяхме. От условието b−d≥5b-d\ge5 следва b−d−1≥4b-d-1\ge4, затова (b−d−1)2+(a−c)2≥42+02=16.(b-d-1)^2+(a-c)^2\ge4^2+0^2=16. Така най-малката възможна стойност е 1616.
Отвори задачатаEvan Chen VONVON USAMO 2014/1Условие — източник

Задача 2

Пълен запис
Условие
Да се намерят всички функции f:Z→Zf:\mathbb Z\to\mathbb Z, за които xf(2f(y)−x)+y2f(2x−f(y))=xf(2f(y)-x)+y^2f(2x-f(y))=f(x)2x+f(yf(y))f(x)^2x+f(yf(y)) за всички x,y∈Zx,y\in\mathbb Z с x≠0x\ne0.
РешениеОтговорът е f(x)≡0f(x)\equiv0 и f(x)≡x2f(x)\equiv x^2; директна проверка показва, че и двете функции удовлетворяват условието. Слагаме y=0y=0. Получаваме xf(2f(0)−x)=f(x)2x+f(0).xf(2f(0)-x)=f(x)^2x+f(0). Първо ще докажем, че f(0)=0f(0)=0. Ако f(0)≠0f(0)\ne0, избираме просто число pp, което не дели f(0)f(0), и полагаме x=px=p. От последното равенство следва, че p∣f(p)2p\mid f(p)^2, следователно p∣f(p)p\mid f(p), а тогава и p∣f(p)2pp\mid f(p)^2p. Връщайки се в равенството, получаваме p∣f(0)p\mid f(0), противоречие. Значи f(0)=0f(0)=0. Тогава от същото равенство следва x2f(−x)=f(x)2x^2f(-x)=f(x)^2 за всяко xx. Аналогично получаваме и f(−x)2=x2f(x)f(-x)^2=x^2f(x). Ако за някое x≠0x\ne0 имаме f(x)≠f(−x)f(x)\ne f(-x), след изваждане и разлагане се стига до f(x)+f(−x)=−x2f(x)+f(-x)=-x^2. Замяната в двете равенства дава (f(x)+x22)2=−34x4,\left(f(x)+\frac{x^2}{2}\right)^2=-\frac34x^4, което е невъзможно. Следователно ff е четна и f(x)2=x2f(x)f(x)^2=x^2f(x), тоест за всяко xx е изпълнено f(x)∈{0,x2}.f(x)\in\{0,x^2\}.Да допуснем, че съществува ненулево цяло число tt с f(t)=0f(t)=0. Ще докажем, че тогава f≡0f\equiv0. Полагаме y=ty=t в условието и получаваме t2f(2x)=0t^2f(2x)=0 за всяко x≠0x\ne0, следователно ff е нула върху всички четни цели числа. Сега полагаме x=2k≠0x=2k\ne0 и имаме y2f(4k−f(y))=f(yf(y)).y^2f(4k-f(y))=f(yf(y)). Ако за някое нечетно m≠0m\ne0 е вярно f(m)=m2f(m)=m^2, то m2f(4k−m2)=f(m3).m^2f(4k-m^2)=f(m^3). При f(m3)≠0f(m^3)\ne0 това би наложило m2(4k−m2)2=m6m^2(4k-m^2)^2=m^6 за произволно k≠0k\ne0, абсурд. Значи f(4k−m2)=f(m3)=0f(4k-m^2)=f(m^3)=0 за всяко k≠0k\ne0. Понеже mm е нечетно, m2≡1(mod4)m^2\equiv1\pmod4, така всички цели числа с изключение евентуално на ±m2\pm m^2 имат стойност 00. Но f(m)=m2f(m)=m^2 тогава дава m=±1m=\pm1. Остава възможността f(±1)=1f(\pm1)=1, а всички други стойности да са 00; тя се изключва, като заместим x=5x=5 и y=1y=1 в първоначалното равенство. Следователно, ако някъде има ненулево tt с f(t)=0f(t)=0, то f≡0f\equiv0. В противен случай за всяко x≠0x\ne0 трябва да е f(x)=x2f(x)=x^2, а и f(0)=0f(0)=0, тоест f(x)≡x2f(x)\equiv x^2. Така решенията са точно двете посочени функции.
Отвори задачатаEvan Chen VONVON USAMO 2014/2Условие — източник

Задача 3

Пълен запис
Условие
Да се докаже, че съществува безкрайно множество от точки …,P−3,P−2,P−1,P0,P1,P2,P3,…\ldots,P_{-3},P_{-2},P_{-1},P_0,P_1,P_2,P_3,\ldots в равнината със следното свойство: за всеки три различни цели числа a,b,ca,b,c точките Pa,Pb,PcP_a,P_b,P_c лежат на една права тогава и само тогава, когато a+b+c=2014a+b+c=2014.
РешениеДаваме явна конструкция. За всяко цяло число nn полагаме Pn=(n−20143,(n−20143)3).P_n=\left(n-\frac{2014}{3},\left(n-\frac{2014}{3}\right)^3\right). Ще използваме следния факт: ако x,y,zx,y,z са различни реални числа, то точките (x,x3)(x,x^3), (y,y3)(y,y^3) и (z,z3)(z,z^3) са колинеарни тогава и само тогава, когато x+y+z=0x+y+z=0. Наистина, по формулата за лице с детерминанта трите точки са колинеарни точно когато 0=det⁡(xx31yy31zz31).0=\det\begin{pmatrix}x&x^3&1\\y&y^3&1\\z&z^3&1\end{pmatrix}. Този детерминант е равен на (x−y)(y−z)(z−x)(x+y+z).(x-y)(y-z)(z-x)(x+y+z). Понеже x,y,zx,y,z са различни, първите три множителя са ненулеви, затова колинеарността е еквивалентна на x+y+z=0x+y+z=0. Сега за Pa,Pb,PcP_a,P_b,P_c вземаме x=a−20143,y=b−20143,z=c−20143.x=a-\frac{2014}{3},\qquad y=b-\frac{2014}{3},\qquad z=c-\frac{2014}{3}. Тогава x+y+z=a+b+c−2014x+y+z=a+b+c-2014. Следователно Pa,Pb,PcP_a,P_b,P_c лежат на една права точно когато a+b+c=2014a+b+c=2014, както се искаше.
Отвори задачатаEvan Chen VONVON USAMO 2014/3Условие — източник

Задача 6

Пълен запис
Условие
Да се докаже, че съществува константа c>0c\gt{}0 със следното свойство: ако a,b,na,b,n са положителни цели числа и gcd⁡(a+i,b+j)>1\gcd(a+i,b+j)\gt{}1 за всички i,j∈{0,1,…,n}i,j\in\{0,1,\ldots,n\}, то min⁡{a,b}>(cn)n/2.\min\{a,b\}\gt{}(cn)^{n/2}.
РешениеНека N=n+1N=n+1. Първо ще докажем твърдението за достатъчно големи nn; накрая ще намалим константата cc, за да покрием и крайно многото малки стойности на nn. Разглеждаме таблица N×NN\times N с клетки (i,j)(i,j), където 0≤i,j≤n0\le i,j\le n. Във всяка клетка избираме едно просто число pp, което дели gcd⁡(a+i,b+j)\gcd(a+i,b+j). Основното твърдение е, че за големи nn поне половината клетки са запълнени с прости числа, по-големи от 0.001n20.001n^2. Наистина, за фиксирано просто pp броят на клетките, в които може да се появи pp, е най-много ⌈Np⌉2,\left\lceil\frac{N}{p}\right\rceil^2, защото pp трябва едновременно да дели някое от числата a,a+1,…,a+na,a+1,\ldots,a+n и някое от числата b,b+1,…,b+nb,b+1,\ldots,b+n. Следователно броят на клетките, които могат да бъдат запълнени с просто p≤0.001n2p\le0.001n^2, е най-много ∑p≤0.001n2⌈Np⌉2≤\sum_{p\le0.001n^2}\left\lceil\frac{N}{p}\right\rceil^2\le∑p≤0.001n2(Np+1)2.\sum_{p\le0.001n^2}\left(\frac{N}{p}+1\right)^2. Последната сума е N2∑p1p2+2N∑p1p+∑p1,N^2\sum_p\frac1{p^2}+2N\sum_p\frac1p+\sum_p1, където сумираме по простите p≤0.001n2p\le0.001n^2. Имаме ∑p1/p2<0.46\sum_p1/p^2\lt{}0.46, а ако r=π(0.001n2)r=\pi(0.001n^2), то ∑p1p≤∑k=1r1k=O(log⁡r)=o(N)\sum_p\frac1p\le\sum_{k=1}^r\frac1k=O(\log r)=o(N) и ∑p1=r=O(N2ln⁡N)=o(N2)\sum_p1=r=O\left(\frac{N^2}{\ln N}\right)=o(N^2) по теоремата за простите числа. Затова за достатъчно голямо NN малките прости числа покриват по-малко от N2/2N^2/2 клетки. Следователно поне половината клетки съдържат избрано просто число, по-голямо от 0.001n20.001n^2. Тогава в някой стълб има поне N/2N/2 такива клетки. Всички съответни прости числа делят едно и също число a+ia+i. Освен това те са различни: ако едно и също просто p>np\gt{}n делеше и b+j1b+j_1, и b+j2b+j_2 с 0≤j1,j2≤n0\le j_1,j_2\le n, то pp би деляло j1−j2j_1-j_2, което е възможно само при j1=j2j_1=j_2. Следователно a+i≥∏p>(0.001n2)N/2.a+i\ge\prod p\gt{}(0.001n^2)^{N/2}. Понеже 0≤i≤n0\le i\le n, оттук за достатъчно голямо nn следва a>(cn)n/2a\gt{}(c n)^{n/2} за някоя положителна абсолютна константа cc. Същият аргумент, приложен към редовете вместо към стълбовете, дава b>(cn)n/2b\gt{}(c n)^{n/2} след евентуално още едно намаляване на cc. Остава само да се погрижим за крайно многото малки стойности на nn, които не попадат в асимптотичния аргумент. Намаляваме c>0c\gt{}0 достатъчно, така че неравенството да е вярно и за тях. Така получаваме исканото min⁡{a,b}>(cn)n/2.\min\{a,b\}\gt{}(cn)^{n/2}.
Отвори задачатаEvan Chen VONVON USAMO 2014/6Условие — източник