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

Evan Chen / USAMO Solution Notes

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

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

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

2013

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

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

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

11-12

3 задачи

Задача 2

Пълен запис
Условие
За положително цяло число n≥3n\ge3 са разположени nn равноотдалечени точки върху окръжност. Една от тях е означена с AA, а в AA е поставен маркер. На всеки ход маркерът може да се премести напред по часовниковата стрелка или до следващата точка, или до точката след нея. Така има общо 2n2n различни хода, по два от всяка точка. Нека ana_n е броят на начините маркерът да обиколи окръжността точно два пъти, започвайки и завършвайки в AA, без да повтаря ход. Докажете, че an−1+an=2na_{n-1}+a_n=2^n за всяко n≥4n\ge4.
РешениеЩе заменим движението по окръжността с движение по множествотоS={0,1,2,…,2n},S=\{0,1,2,\ldots,2n\},като започваме от 00, завършваме в 2n2n и правим скокове с дължина 11 или 22. Нека pi=1p_i=1, ако точката ii е посетена, и pi=0p_i=0 иначе. Записваме тези данни в матрицата[p0p1p2⋯pn−1pnpnpn+1pn+2⋯p2n−1p2n].\begin{bmatrix} p_0&p_1&p_2&\cdots&p_{n-1}&p_n\\ p_n&p_{n+1}&p_{n+2}&\cdots&p_{2n-1}&p_{2n} \end{bmatrix}.Имаме p0=p2n=1p_0=p_{2n}=1, а горният десен и долният ляв елемент са равни. Условието, че скоковете са само с дължина 11 или 22 и че никой ход не се повтаря, е еквивалентно на това в матрицата да не се срещат съседни подматрици от видовете[00],[00],[1111].\begin{bmatrix}0&0\end{bmatrix},\qquad \begin{bmatrix}0\\0\end{bmatrix},\qquad \begin{bmatrix}1&1\\1&1\end{bmatrix}.Затова можем да гледаме само трите възможни стълбови вектораu=[10],v=[01],w=[11].\mathbf u=\begin{bmatrix}1\\0\end{bmatrix},\qquad \mathbf v=\begin{bmatrix}0\\1\end{bmatrix},\qquad \mathbf w=\begin{bmatrix}1\\1\end{bmatrix}.Валидните матрици са точно редици от n+1n+1 такива стълба, в които няма два съседни еднакви стълба, и граничното условие е едно от следните две:начало u и край v,\text{начало }\mathbf u\text{ и край }\mathbf v,илиначало w и край w.\qquad\text{или}\qquad\text{начало }\mathbf w\text{ и край }\mathbf w.Фиксираме началния стълб. Нека xnx_n е броят на редиците от n+1n+1 стълба, които завършват в един предварително фиксиран различен от началния стълб, а yny_n е броят на редиците, които завършват в началния стълб. Тогава по симетрияan=xn+yn.a_n=x_n+y_n.Освен това имаме рекурентните зависимостиxn+1=xn+yn,yn+1=2xn.x_{n+1}=x_n+y_n,\qquad y_{n+1}=2x_n.Наистина, за да завършим в фиксиран различен стълб, предишният стълб може да е началният или третият стълб; а за да завършим в началния стълб, предишният стълб може да бъде който и да е от двата различни стълба. Ще използваме още, че2xn+yn=2n.2x_n+y_n=2^n.Това може да се докаже от рекурсиите и началните стойности x1=1x_1=1, y1=0y_1=0, но има и директно броене: след първия стълб всеки от следващите nn стълба има точно два избора, защото не може да бъде равен на предишния. Лявата страна брои всички възможни крайни стълбове - двата различни дават по xnx_n, а началният дава yny_n. Накрая получавамеan+1+an=(xn+1+yn+1)+(xn+yn)=(xn+yn+2xn)+(xn+yn)=2(2xn+yn)=2n+1.\begin{aligned} a_{n+1}+a_n&=(x_{n+1}+y_{n+1})+(x_n+y_n)\\ &=(x_n+y_n+2x_n)+(x_n+y_n)\\ &=2(2x_n+y_n)=2^{n+1}. \end{aligned}След замяна на n+1n+1 с nn това е точно an−1+an=2na_{n-1}+a_n=2^n за всяко n≥4n\ge4.
Отвори задачатаEvan Chen VONVON USAMO 2013/2Условие — източник

Задача 4

Пълен запис
Условие
Да се намерят всички реални числа x,y,z≥1x,y,z\ge1, за които min⁡{x2x+xyz,x2y+xyz,x2z+xyz}=\min\{\sqrt{\vphantom{x^2}x+xyz},\sqrt{\vphantom{x^2}y+xyz},\sqrt{\vphantom{x^2}z+xyz}\}=x2x−1+x2y−1+x2z−1.\sqrt{\vphantom{x^2}x-1}+\sqrt{\vphantom{x^2}y-1}+\sqrt{\vphantom{x^2}z-1}.
РешениеНека x=1+ax=1+a, y=1+by=1+b, z=1+cz=1+c, където a,b,c≥0a,b,c\ge0. Поради симетрия можем да приемем, че a≤b≤ca\le b\le c, така че x≤y≤zx\le y\le z и минимумът вляво е първият член. Трябва да имаме x2(1+a)(1+(1+b)(1+c))=a+b+c.\sqrt{\vphantom{x^2}(1+a)(1+(1+b)(1+c))}=\sqrt a+\sqrt b+\sqrt c.Ще докажем неравенството в правилната посока и после ще проследим кога има равенство. Имаме 1+(1+b)(1+c)=2+b+c+bc≥1+(1+b)(1+c)=2+b+c+bc\ge1+b+c+2x2bc=1+(b+c)2, 1+b+c+2\sqrt{\vphantom{x^2}bc}=1+(\sqrt b+\sqrt c)^2, като равенство има точно когато bc=1bc=1. Следователно x2(1+a)(1+(1+b)(1+c))≥\sqrt{\vphantom{x^2}(1+a)(1+(1+b)(1+c))}\gex2(1+a)(1+(b+c)2).\sqrt{\vphantom{x^2}(1+a)(1+(\sqrt b+\sqrt c)^2)}. От друга страна, след повдигане на квадрат, (1+a)(1+(b+c)2)≥(a+b+c)2(1+a)(1+(\sqrt b+\sqrt c)^2)\ge(\sqrt a+\sqrt b+\sqrt c)^2 е еквивалентно на 1+a(b+c)2≥2a(b+c),1+a(\sqrt b+\sqrt c)^2\ge2\sqrt a(\sqrt b+\sqrt c), тоест на (a(b+c)−1)2≥0.(\sqrt a(\sqrt b+\sqrt c)-1)^2\ge0. Равенство във второто неравенство има точно когато a(b+c)=1\sqrt a(\sqrt b+\sqrt c)=1. Значи равенство в първоначалното уравнение е възможно и необходимо точно при условията bc=1,a(b+c)=1,bc=1,\qquad \sqrt a(\sqrt b+\sqrt c)=1, след евентуална пермутация на a,b,ca,b,c. Нека c=t2c=t^2 и b=t−2b=t^{-2} за някое t>0t\gt{}0. Тогава a=1t+t−1,a=t2(t2+1)2.\sqrt a=\frac1{t+t^{-1}},\qquad a=\frac{t^2}{(t^2+1)^2}.Следователно всички решения са всички пермутации на тройките (1+t2(t2+1)2,  1+1t2,  1+t2),t>0.\left(1+\frac{t^2}{(t^2+1)^2},\;1+\frac1{t^2},\;1+t^2\right),\qquad t\gt{}0. Обратно, всяка такава тройка удовлетворява двете условия за равенство, затова действително е решение.
Отвори задачатаEvan Chen VONVON USAMO 2013/4Условие — източник

Задача 5

Пълен запис
Условие
Нека mm и nn са положителни цели числа. Да се докаже, че съществува положително цяло число cc, така че cmcm и cncn да имат едни и същи ненулеви цифри в десетичния си запис.
РешениеЩе построим множител CC, който върши работа. Първо ще намерим положителни цели числа DD и ee такива, че gcd⁡(D,10)=1\gcd(D,10)=1, D>max⁡{m,n}D\gt{}\max\{m,n\} и 10em≡n(modD).10^e m\equiv n\pmod D. Нека r=ν2(n)r=\nu_2(n) и s=ν5(n)s=\nu_5(n). Избираме e>max⁡{r,s}e\gt{}\max\{r,s\} толкова голямо, че A=10em−n>2r5smax⁡{m,n}.A=10^e m-n\gt{}2^r5^s\max\{m,n\}. Тогава ν2(A)=r\nu_2(A)=r и ν5(A)=s\nu_5(A)=s, понеже 10em10^e m се дели на по-високи степени на 22 и 55 от тези, които делят nn. Поставяме D=A2r5s.D=\frac{A}{2^r5^s}. Получаваме gcd⁡(D,10)=1\gcd(D,10)=1, D>max⁡{m,n}D\gt{}\max\{m,n\}, а от A=10em−nA=10^e m-n следва исканото сравнение 10em≡n(modD)10^e m\equiv n\pmod D. Понеже DD е взаимно просто с 1010, съществува положително цяло число LL, за което 10L≡1(modD)10^L\equiv1\pmod D. Нека C=10L−1D.C=\frac{10^L-1}{D}. Тъй като m,n<Dm,n\lt{}D, произведенията mCmC и nCnC са по-малки от 10L−110^L-1, затова можем да ги разглеждаме като блокове от точно LL десетични цифри, допускайки водещи нули. Умножавайки сравнението 10em≡n(modD)10^e m\equiv n\pmod D по CC, получаваме 10emC≡nC(mod10L−1).10^e mC\equiv nC\pmod{10^L-1}.Сравнение по модул 10L−110^L-1 има точно следния смисъл за блокове от LL цифри: умножението по 1010 премества цифрите циклично, а умножението по 10e10^e прави ee такива циклични премествания. Значи mCmC и nCnC имат едни и същи цифри като LL-цифрени блокове, евентуално в различен цикличен ред и с водещи нули. След премахване на водещите нули, нулите може да се появяват на различни места, но всички ненулеви цифри са едни и същи. Следователно търсеното число е c=Cc=C.
Отвори задачатаEvan Chen VONVON USAMO 2013/5Условие — източник