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

Evan Chen / USAMO Solution Notes

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

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

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

2016

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Нека X1,X2,…,X100X_1,X_2,\ldots,X_{100} е редица от различни непразни подмножества на множество SS. Всеки две съседни множества XiX_i и Xi+1X_{i+1} са непресичащи се и обединението им не е цялото множество SS, тоест Xi∩Xi+1=∅X_i\cap X_{i+1}=\varnothing и Xi∪Xi+1≠SX_i\cup X_{i+1}\ne S за всички i∈{1,…,99}i\in\{1,\ldots,99\}. Да се намери най-малкият възможен брой елементи на SS.
РешениеОтговорът е 88. Първо, понеже са нужни 100100 различни непразни подмножества, имаме 2∣S∣≥1002^{|S|}\ge100, откъдето ∣S∣≥7|S|\ge7. Ще покажем, че ∣S∣=7|S|=7 е невъзможно. Ако ∣S∣=7|S|=7, всяко подмножество с поне 44 елемента може да бъде съседно само на подмножество с най-много 22 елемента: съседът трябва да е непресичащ се с него, а ако запълни целия допълнителен остатък, обединението ще бъде SS. Подмножествата с размер 11 или 22 са (71)+(72)=28.\binom71+\binom72=28. Затова в редицата може да има най-много 2929 подмножества с размер поне 44. Подмножествата с размер 33 са само (73)=35\binom73=35, така че общият брой членове е най-много 29+28+35=92<10029+28+35=92\lt{}100, противоречие. Остава конструкция за ∣S∣=8|S|=8. Ще построим за всяко n≥4n\ge4 редица с дължина 2n−1+12^{n-1}+1 от непразни различни подмножества на {1,2,…,n}\{1,2,\ldots,n\} със същото свойство. За n=4n=4 работи редицата {3,4},{1},{2,3},{4},\{3,4\},\{1\},\{2,3\},\{4\},{1,2},{3},{1,4},{2},{1,3}.\{1,2\},\{3\},\{1,4\},\{2\},\{1,3\}. Да предположим, че имаме такава редица за nn. Изтриваме един неин член, така че дължината да стане четна, правим две копия на получената редица, поставяме ∅\varnothing между двете копия и после добавяме елемента n+1n+1 към множествата на нечетните позиции. Съседните множества остават непресичащи се, защото n+1n+1 се добавя само към едното от всеки две съседни множества; обединението им не е цялото ново множество, защото старото обединение е пропускало стар елемент, а около средното множество {n+1}\{n+1\} съседът не е цялото старо множество. Двете копия също не създават повторения, понеже едното копие получава n+1n+1 в точно обратните позиции спрямо другото. Така получаваме редица с дължина 2n+12^n+1. При n=8n=8 тя има 129129 члена, от които можем да вземем първите 100100.
Отвори задачатаEvan Chen VONVON USAMO 2016/1Условие — източник

Задача 2

Пълен запис
Условие
Да се докаже, че за всяко положително цяло число kk числото (k2)!∏j=0k−1j!(j+k)!(k^2)!\prod_{j=0}^{k-1}\frac{j!}{(j+k)!} е цяло.
РешениеДостатъчно е да докажем, че показателят на всяко просто число pp в разлагането на даденото число е неотрицателен. По формулата на Льожандр показателят на pp в N!N! е ∑r≥1⌊Npr⌋.\sum_{r\ge1}\left\lfloor\frac{N}{p^r}\right\rfloor. Следователно е достатъчно за всяка степен q=prq=p^r на просто число да имаме ⌊k2q⌋+∑j=0k−1⌊jq⌋≥\left\lfloor\frac{k^2}{q}\right\rfloor+\sum_{j=0}^{k-1}\left\lfloor\frac{j}{q}\right\rfloor\ge∑j=0k−1⌊j+kq⌋.\sum_{j=0}^{k-1}\left\lfloor\frac{j+k}{q}\right\rfloor. Тъй като двете страни са цели числа, стига да докажем малко по-силното неравенство със строг запас 11: ⌊k2q⌋+∑j=0k−1⌊jq⌋>\left\lfloor\frac{k^2}{q}\right\rfloor+\sum_{j=0}^{k-1}\left\lfloor\frac{j}{q}\right\rfloor\gt{}−1+∑j=0k−1⌊j+kq⌋.-1+\sum_{j=0}^{k-1}\left\lfloor\frac{j+k}{q}\right\rfloor. Ако {x}\{x\} означава дробната част на xx, това е равносилно на {k2q}+∑j=0k−1{jq}<1+∑j=0k−1{j+kq}.\left\{\frac{k^2}{q}\right\}+\sum_{j=0}^{k-1}\left\{\frac{j}{q}\right\}\lt{}1+\sum_{j=0}^{k-1}\left\{\frac{j+k}{q}\right\}. Но q{t/q}q\{t/q\} е остатъкът на tt при деление на qq. Сумата от остатъците на 0,1,…,k−10,1,\ldots,k-1 по модул qq е не по-голяма от сумата от остатъците на k,k+1,…,2k−1k,k+1,\ldots,2k-1. Наистина, ако k=aq+bk=aq+b и 0≤b<q0\le b\lt{}q, разликата между втората и първата сума е b2b^2 при 2b<q2b\lt{}q и (q−b)2(q-b)^2 при 2b≥q2b\ge q. Понеже {k2/q}<1\{k^2/q\}\lt{}1, последното веднага дава исканото строго неравенство. Значи всеки прост показател е неотрицателен и числото е цяло.
Отвори задачатаEvan Chen VONVON USAMO 2016/2Условие — източник

Задача 4

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb R\to\mathbb R, за които за всички реални числа xx и yy е изпълнено (f(x)+xy) f(x−3y)+(f(y)+xy) f(3x−y)=(f(x)+xy)\,f(x-3y)+(f(y)+xy)\,f(3x-y)=(f(x+y))2.(f(x+y))^2.
РешениеОтговорите са f(x)≡0f(x)\equiv0 и f(x)≡x2f(x)\equiv x^2; директна проверка показва, че и двете функции работят. Поставяйки x=y=0x=y=0, получаваме f(0)=0f(0)=0. После при x=0x=0 имаме f(y)f(−y)=f(y)2f(y)f(-y)=f(y)^2, а след замяна на yy с −y-y получаваме и f(y)f(−y)=f(−y)2f(y)f(-y)=f(-y)^2. Следователно ff е четна функция. Сега поставяме x=−yx=-y. Понеже f(0)=0f(0)=0 и ff е четна, следва 2(f(x)−x2)f(4x)=0.2(f(x)-x^2)f(4x)=0. Значи за всяко реално xx е вярно, че или f(x)=x2f(x)=x^2, или f(4x)=0f(4x)=0. Ще докажем още, че f(z)=0точно тогава, когатоf(2z)=0.f(z)=0\quad\text{точно тогава, когато}\quad f(2z)=0. При (x,y)=(3t,t)(x,y)=(3t,t) началното уравнение дава (f(t)+3t2)f(8t)=f(4t)2.(f(t)+3t^2)f(8t)=f(4t)^2. Ако f(4t)≠0f(4t)\ne0, то f(8t)≠0f(8t)\ne0, откъдето чрез контрапозиция следва f(2z)=0⇒f(z)=0f(2z)=0\Rightarrow f(z)=0. За обратната посока, ако f(4t)≠0f(4t)\ne0, предишната алтернатива дава f(t)=t2≠0f(t)=t^2\ne0, а вече доказаната посока чрез контрапозиция дава f(2t)≠0f(2t)\ne0. Това е точно контрапозицията на f(z)=0⇒f(2z)=0f(z)=0\Rightarrow f(2z)=0. Комбинирайки тази еквивалентност с алтернативата по-горе, получаваме за всяко xx, че f(x)f(x) е или 00, или x2x^2. Ако няма ненулево aa с f(a)=0f(a)=0, тогава веднага f(x)=x2f(x)=x^2 за всички xx. Нека сега има a≠0a\ne0 и f(a)=0f(a)=0. Ще докажем, че тогава f≡0f\equiv0. Нека bb е произволно реално число; поради четността можем да приемем a,b>0a,b\gt{}0, а случаят b=0b=0 вече е ясен. От еквивалентността за нулите получаваме f(2ra)=0f(2^r a)=0 за всяко rr, затова избираме c=2ra>bc=2^r a\gt{}b. Вземаме x=3c+b4,y=c−b4,x=\frac{3c+b}{4},\qquad y=\frac{c-b}{4}, така че x,y>0x,y\gt{}0, x−3y=bx-3y=b и x+y=cx+y=c. След заместване в началното уравнение получаваме 0=(f(x)+xy)f(b)+(f(y)+xy)f(3x−y).0=(f(x)+xy)f(b)+(f(y)+xy)f(3x-y). Всички стойности на ff са неотрицателни, а xy>0xy\gt{}0, следователно първият множител f(x)+xyf(x)+xy е положителен и оттук f(b)=0f(b)=0. Значи всяко bb е нула на ff, тоест f≡0f\equiv0.
Отвори задачатаEvan Chen VONVON USAMO 2016/4Условие — източник

Задача 5

Пълен запис
Условие
Равностранен петоъгълник AMNPQAMNPQ е вписан в триъгълник ABCABC така, че M∈AB‾M\in\overline{AB}, Q∈AC‾Q\in\overline{AC} и N,P∈BC‾N,P\in\overline{BC}. Нека SS е пресечната точка на правите MNMN и PQPQ. С ℓ\ell означаваме ъглополовящата на ∠MSQ\angle MSQ. Докажете, че OI∥ℓOI\parallel\ell, където OO е центърът на описаната окръжност на триъгълника ABCABC, а II е инцентърът на триъгълника ABCABC.
РешениеПърво решение, с комплексни числа. Всъщност е достатъчно да имаме AM=AQ=NPAM=AQ=NP и MN=QPMN=QP. Работим с комплексни числа така, че описаната окръжност на ABCABC да е единичната окръжност с център O=0O=0, като без ограничение върховете A,B,CA,B,C са подредени обратно на часовниковата стрелка. Нека x,y,zx,y,z са комплексните числа на средите на дъгите BCBC, CACA, ABAB съответно; тогава инцентърът II има посока x+y+zx+y+z от OO. Нека s>0s\gt{}0 е общата дължина AM=AQ=NPAM=AQ=NP. Понеже MA=sMA=s и MA⊥OZMA\perp OZ, получавамеm−a=i⋅sz.m-a=i\cdot sz.Аналогичноp−n=i⋅sy,a−q=i⋅sx.p-n=i\cdot sy,\qquad a-q=i\cdot sx.Като съберем трите равенства, намирамеi⋅s(x+y+z)=(p−q)+(m−n)=(m−n)−(q−p).i\cdot s(x+y+z)=(p-q)+(m-n)=(m-n)-(q-p).Понеже MN=PQMN=PQ, векторът (m−n)−(q−p)(m-n)-(q-p) е по външната ъглополовяща на ъгъла, образуван от правите MNMN и PQPQ, и следователно е перпендикулярен на ℓ\ell. От друга страна умножението по ii завърта на 90∘90^\circ, така че x+y+zx+y+z е успоредно на ℓ\ell. Но x+y+zx+y+z има същата посока като OIOI, следователно OI∥ℓOI\parallel\ell. Второ решение, с тригонометрия, от Danielle Wang. Нека δ=∠MNB\delta=\angle MNB и ε=∠CPQ\varepsilon=\angle CPQ. Да нормализираме страната на равностранния петоъгълник до 11 и да използваме стандартните означения a=BCa=BC, b=CAb=CA, c=ABc=AB. Ще разгледаме случая AB<ACAB\lt{}AC; другият е симетричен. От проекции върху правата BCBC имамеBN=(c−1)cos⁡B+cos⁡δ,CP=(b−1)cos⁡C+cos⁡ε,a=1+BN+CP.\begin{align*} BN&=(c-1)\cos B+\cos\delta,\\ CP&=(b-1)\cos C+\cos\varepsilon,\\ a&=1+BN+CP. \end{align*}Понеже също a=ccos⁡B+bcos⁡Ca=c\cos B+b\cos C, следваcos⁡δ+cos⁡ε=cos⁡B+cos⁡C−1.\cos\delta+\cos\varepsilon=\cos B+\cos C-1.От синусовата теорема в триъгълниците BMNBMN и CPQCPQ получавамеc−1sin⁡δ=1sin⁡B,b−1sin⁡ε=1sin⁡C,\frac{c-1}{\sin\delta}=\frac1{\sin B},\qquad \frac{b-1}{\sin\varepsilon}=\frac1{\sin C},а оттук, използвайки csin⁡B=bsin⁡Cc\sin B=b\sin C,sin⁡ε−sin⁡δ=sin⁡B−sin⁡C.\sin\varepsilon-\sin\delta=\sin B-\sin C.Формулите за сума и разлика даватsin⁡ε−sin⁡δ=2cos⁡(ε+δ2)sin⁡(ε−δ2),cos⁡ε+cos⁡δ=2cos⁡(ε+δ2)cos⁡(ε−δ2),\begin{align*} \sin\varepsilon-\sin\delta&=2\cos\left(\frac{\varepsilon+\delta}{2}\right)\sin\left(\frac{\varepsilon-\delta}{2}\right),\\ \cos\varepsilon+\cos\delta&=2\cos\left(\frac{\varepsilon+\delta}{2}\right)\cos\left(\frac{\varepsilon-\delta}{2}\right), \end{align*}следователноtan⁡(ε−δ2)=sin⁡ε−sin⁡δcos⁡ε+cos⁡δ=\tan\left(\frac{\varepsilon-\delta}{2}\right)=\frac{\sin\varepsilon-\sin\delta}{\cos\varepsilon+\cos\delta}=sin⁡B−sin⁡Ccos⁡B+cos⁡C−1.\frac{\sin B-\sin C}{\cos B+\cos C-1}.Правата ℓ\ell сключва с BCBC ъгъл 12(π+ε−δ)\frac12(\pi+\varepsilon-\delta). Ако правата OIOI пресича BCBC под ъгъл φ\varphi, тоtan⁡φ=r−Rcos⁡A12(b−c),\tan\varphi=\frac{r-R\cos A}{\frac12(b-c)},където rr и RR са съответно радиусите на вписаната и описаната окръжност на ABCABC. Затова остава да проверимr−Rcos⁡A12(b−c)=cos⁡B+cos⁡C−1sin⁡B−sin⁡C.\frac{r-R\cos A}{\frac12(b-c)}=\frac{\cos B+\cos C-1}{\sin B-\sin C}.След заместване b=2Rsin⁡Bb=2R\sin B и c=2Rsin⁡Cc=2R\sin C това се свежда точно доrR+1=cos⁡A+cos⁡B+cos⁡C,\frac rR+1=\cos A+\cos B+\cos C,което е стандартната формула на Карно за триъгълник. Следователно OI∥ℓOI\parallel\ell.
Отвори задачатаEvan Chen VONVON USAMO 2016/5Условие — източник

Задача 6

Пълен запис
Условие
Дадени са цели числа nn и kk, като n≥k≥2n\ge k\ge2. Играете следната игра срещу зъл магьосник. Магьосникът има 2n2n карти; за всяко i=1,…,ni=1,\ldots,n има две карти с надпис ii. Първоначално магьосникът поставя всички карти с лице надолу в редица, в неизвестен ред. На всеки ход можете да посочите произволни kk карти. Магьосникът обръща тези карти с лице нагоре. Ако някои две от тях съвпадат, играта приключва и печелите. Иначе трябва да погледнете настрани, докато магьосникът произволно размества избраните kk карти и после отново ги обръща с лице надолу. След това е ваш ред. Казваме, че играта е печеливша, ако съществуват положително цяло число mm и стратегия, която гарантира победа за най-много mm хода, независимо как отговаря магьосникът. За кои стойности на nn и kk играта е печеливша?
РешениеИграта е печеливша точно когато k<nk\lt{}n. Първо нека 2≤k<n2\le k\lt{}n. Последователно питаме за интервалите от позиции {1,…,k},{2,…,k+1},…,{2n−k+1,…,2n}.\{1,\ldots,k\},\{2,\ldots,k+1\},\ldots,\{2n-k+1,\ldots,2n\}. Ако на някой ход се появят две еднакви карти, вече сме спечелили. Ако това не стане, всеки отговор съдържа kk различни надписа. Сравнявайки видените надписи в първия прозорец с надписите на общите k−1k-1 позиции при следващия прозорец, определяме надписа на картата, която напуска прозореца. Това остава вярно и когато двата пълни прозореца имат един и същ набор от надписи, защото общите k−1k-1 позиции пак показват точно кой надпис е излязъл и после е заместен от същия надпис. Така научаваме надписите на 2n−k2n-k карти, които повече няма да бъдат местени. Понеже k<nk\lt{}n, имаме 2n−k>n2n-k\gt{}n, следователно сред тези карти има две с еднакъв надпис. На следващ ход посочваме тези две карти заедно с произволни още k−2k-2 карти и печелим. Остава да покажем, че при k=nk=n няма гарантирана победа. След първия ход, ако играчът не е спечелил, избраните nn карти имат всички nn различни надписа, а останалите nn карти също имат по една карта от всеки надпис. Магьосникът може да поддържа следната неопределеност: във всяка от двете половини редът на надписите е напълно неизвестен за играча. Ако играчът избере само карти от една от половините, той не може да получи съвпадение, защото в нея има по една карта от всеки надпис. Ако избере част от едната и част от другата половина, магьосникът може да е подредил неизвестната половина така, че избраните надписи от едната страна да са точно допълнение на избраните надписи от другата; тогава отново няма съвпадение. След показването той размества избраните карти и същата неопределеност се запазва. Значи при k=nk=n магьосникът може да избягва победата неограничено дълго, а играта не е печеливша.
Отвори задачатаEvan Chen VONVON USAMO 2016/6Условие — източник