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

Evan Chen / USAMO Solution Notes

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

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

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

2024

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Да се намерят всички цели числа n≥3n\ge3 със следното свойство: ако делителите на n!n! са подредени във възходящ ред като1=d1<d2<⋯<dk=n!,1=d_1\lt{}d_2\lt{}\cdots\lt{}d_k=n!,тоd2−d1≤d3−d2≤⋯≤dk−dk−1.d_2-d_1\le d_3-d_2\le\cdots\le d_k-d_{k-1}.
РешениеОтговорът е n∈{3,4}n\in\{3,4\}. Това се проверява директно: за n=3n=3 делителите са 1,2,3,61,2,3,6, а за n=4n=4 са1,2,3,4,6,8,12,24.1,2,3,4,6,8,12,24.Ще докажем, че други стойности няма. Числата 5≤n≤125\le n\le12 отпадат директно: за n=5n=5 имаме 20−15>24−2020-15\gt{}24-20, за n=6n=6 имаме 120−90>144−120120-90\gt{}144-120, а за 7≤n≤127\le n\le12 числата 12,14,1512,14,15 са последователни делители около липсващото просто число 1313, така че 14−12>15−1414-12\gt{}15-14. Нека n≥13n\ge13. Тогава⌊n2⌋2−1≥2n.\left\lfloor\frac n2\right\rfloor^2-1\ge2n.По постулата на Бертран съществува просто число pp такова, чеn<p<⌊n2⌋2−1.n\lt{}p\lt{}\left\lfloor\frac n2\right\rfloor^2-1.Числата⌊n2⌋2−1=(⌊n2⌋−1)(⌊n2⌋+1)\left\lfloor\frac n2\right\rfloor^2-1=\left(\left\lfloor\frac n2\right\rfloor-1\right)\left(\left\lfloor\frac n2\right\rfloor+1\right)и⌊n2⌋2\left\lfloor\frac n2\right\rfloor^2са две последователни цели числа, които делят n!n!. Между тях обаче има просто число p>np\gt{}n, което не дели n!n!. Това нарушава монотонността на разликите между съседни делители. Следователно единствените решения са 33 и 44.
Отвори задачатаEvan Chen VONVON USAMO 2024/1Условие — източник

Задача 2

Пълен запис
Условие
Нека S1,S2,…,S100S_1,S_2,\ldots,S_{100} са крайни множества от цели числа, чието сечение е непразно. За всяко непразно подмножество T⊆{S1,S2,…,S100}T\subseteq\{S_1,S_2,\ldots,S_{100}\} броят на елементите в сечението на множествата от TT се дели на ∣T∣|T|. Да се намери най-малкият възможен брой елементи, които принадлежат на поне 5050 от множествата.
РешениеОтговорът е50(10050).50\binom{100}{50}.Ще кодираме всеки елемент с двоичен вектор v∈{0,1}100v\in\{0,1\}^{100}: vi=1v_i=1 означава, че елементът лежи в SiS_i. Нека f(v)f(v) е броят елементи с точно този вектор на принадлежност. Ако пишем u⊆vu\subseteq v, когато всички единици на uu са и единици на vv, условието на задачата ставаP(u):∣u∣∣∑v⊇uf(v)P(u):\qquad |u|\mid\sum_{v\supseteq u} f(v)за всеки ненулев uu. Търсената величина еA=∑∣v∣≥50f(v).A=\sum_{|v|\ge50} f(v).Достатъчно е да разглеждаме стойностите на f(v)f(v) за ∣v∣≥50|v|\ge50: след като те са избрани така, че P(u)P(u) е изпълнено за ∣u∣≥50|u|\ge50, стойностите за ∣v∣<50|v|\lt{}50 могат да се допълнят надолу по индукция, без да променят AA. Първо даваме конструкция. За ∣v∣≥50|v|\ge50 поставямеf0(v)=2∣v∣−100.f_0(v)=2|v|-100.Ако ∣u∣=100−k|u|=100-k, където 0≤k≤500\le k\le50, тогава∑v⊇uf0(v)=\sum_{v\supseteq u} f_0(v)=(k0)100+(k1)98+(k2)96+⋯+(kk)(100−2k)=\binom{k}{0}100+\binom{k}{1}98+\binom{k}{2}96+\cdots+\binom{k}{k}(100-2k)=(100−k)2k,(100-k)2^k,което се дели на ∣u∣|u|. При тази конструкцияA=∑i=50100(100i)(2i−100)=50(10050).A=\sum_{i=50}^{100}\binom{100}{i}(2i-100)=50\binom{100}{50}.Следователно тази стойност е достижима. Остава да докажем, че по-малка стойност е невъзможна. Ще използваме операция „сваляне“ върху вектор vv с ∣v∣≥50|v|\ge50 и f(v)≥∣v∣f(v)\ge |v|: намаляваме f(v)f(v) с ∣v∣|v|, а за всеки w⊆vw\subseteq v с ∣w∣=∣v∣−1|w|=|v|-1 увеличаваме f(w)f(w) с 11. Тази операция запазва всички условия P(u)P(u) с ∣u∣≥50|u|\ge50. Наистина, ако u⊆vu\subseteq v, сумата в P(u)P(u) се променя с−∣v∣+(∣v∣−∣u∣)=−∣u∣,-|v|+(|v|-|u|)=-|u|,а това не влияе на делимостта на ∣u∣|u|. Освен това AA не се променя, когато ∣v∣>50|v|\gt{}50, а при ∣v∣=50|v|=50 намалява с 5050. Започваме с произволна допустима конфигурация. Първо сваляме вектора 11…111\ldots1, докато f(11…1)=100f(11\ldots1)=100; това е възможно, понеже общото сечение е непразно и броят му се дели на 100100. После сваляме последователно всички вектори с 9999 единици, докато стойностите им станат по-малки от 9999, после всички с 9898 единици и така нататък до 5050 единици. Получаваме конфигурация с 0≤f(v)<∣v∣0\le f(v)\lt{}|v| за 50≤∣v∣≤10050\le |v|\le100, без да сме увеличили AA. Сега надолу по индукция от ∣v∣=99|v|=99 до 5050 условието P(v)P(v) даваf(v)≡f0(v)(mod∣v∣).f(v)\equiv f_0(v)\pmod{|v|}.Понеже и f(v)f(v), и f0(v)f_0(v) лежат между 00 и ∣v∣−1|v|-1, следва f(v)=f0(v)f(v)=f_0(v). Следователно след свалянията неизбежно стигаме до конструкцията f0f_0, чиято стойност на AA е 50(10050)50\binom{100}{50}. Понеже свалянията не увеличават AA, началната конфигурация също има A≥50(10050)A\ge50\binom{100}{50}.
Отвори задачатаEvan Chen VONVON USAMO 2024/2Условие — източник

Задача 3

Пълен запис
Условие
Нека (m,n)(m,n) са положителни цели числа с n≥3n\ge3 и е даден правилен nn-ъгълник. Искаме да го триангулираме на n−2n-2 триъгълника, като всеки триъгълник е оцветен в един от mm цвята, така че сборът от лицата на триъгълниците от всеки цвят да е един и същ. За кои (m,n)(m,n) е възможно това?
РешениеОтговорът е: точно когато mm е собствен делител на nn, тоест m∣nm\mid n и m<nm\lt{}n. Първо построяваме пример. Нека върховете на правилния nn-ъгълник са1,ω,ω2,…,ωn−1,ω=e2πi/n.1,\omega,\omega^2,\ldots,\omega^{n-1},\qquad \omega=e^{2\pi i/n}.Вземаме триангулацията с всички диагонали от върха 11. За удобство добавяме и двата дегенерирали триъгълника при j=0j=0 и j=n−1j=n-1, чиито лица са 00; това не променя задачата. Оцветяваме триъгълника с върхове 1,ωj,ωj+11,\omega^j,\omega^{j+1} според остатъка на jj по модул mm. Ще използваме следната стандартна формула: ориентираното лице на триъгълника с върхове ωk,ωk+a,ωk+b\omega^k,\omega^{k+a},\omega^{k+b} еT(a,b)=(ωa−1)(ωb−1)(ω−b−ω−a)4i.T(a,b)=\frac{(\omega^a-1)(\omega^b-1)(\omega^{-b}-\omega^{-a})}{4i}.Тя се получава директно от формулата на Гаус за лице след завъртане с ω−k\omega^{-k}. Ако фиксираме остатък rr по модул mm, сборът от лицата на този цвят е∑j≡r ( mod m)T(j,j+1)=ω−14i∑j≡r ( mod m)(ω−j−1)(ωj−ω−1).\begin{align*} \sum_{j\equiv r\, (\bmod m)} T(j,j+1) &=\frac{\omega-1}{4i}\sum_{j\equiv r\, (\bmod m)}(\omega^{-j}-1)(\omega^j-\omega^{-1}). \end{align*}Понеже m∣nm\mid n, но m<nm\lt{}n, имаме∑j≡r ( mod m)ωj=\sum_{j\equiv r\, (\bmod m)}\omega^j=ωr(1+ωm+ω2m+⋯+ωn−m)=0,\omega^r(1+\omega^m+\omega^{2m}+\cdots+\omega^{n-m})=0,и също така ∑j≡r ( mod m)ω−1−j=0\sum_{j\equiv r\, (\bmod m)}\omega^{-1-j}=0. Следователно горният сбор еnm⋅ω−ω−14i,\frac{n}{m}\cdot\frac{\omega-\omega^{-1}}{4i},което не зависи от rr. Значи всички цветове имат равни сборове от лица. Остава да докажем, че други случаи няма. Първо m<nm\lt{}n, защото всеки цвят трябва да има положителен общ сбор от лица, а триъгълниците са само n−2n-2. Да допуснем, че има валидно оцветяване. Тогава всеки цвят има общо лицеS=nm⋅ω−ω−14i.S=\frac{n}{m}\cdot\frac{\omega-\omega^{-1}}{4i}.За всеки триъгълник от върхове на правилния nn-ъгълник числото4iT(a,b)=(ωa−1)(ωb−1)(ω−b−ω−a)4iT(a,b)=(\omega^a-1)(\omega^b-1)(\omega^{-b}-\omega^{-a})е алгебрично цяло. Следователно и 4iS4iS трябва да е алгебрично цяло. Умножаваме по ω\omega и получавамеω⋅4iS=nm(ω2−1).\omega\cdot4iS=\frac{n}{m}(\omega^2-1).В циклотомичното поле Q(ω)\mathbb Q(\omega) пръстенът на целите е Z[ω]\mathbb Z[\omega], така че ако m∤nm\nmid n, последното число не е алгебрично цяло. Противоречие. Значи m∣nm\mid n, а с m<nm\lt{}n получаваме точно посочените двойки.
Отвори задачатаEvan Chen VONVON USAMO 2024/3Условие — източник

Задача 4

Пълен запис
Условие
Нека mm и nn са положителни цели числа. Кръгова огърлица има mnmn мъниста, всяко от които е червено или синьо. Оказало се, че както и да разрежем огърлицата на mm блока от по nn последователни мъниста, блоковете имат различен брой червени мъниста. Да се намерят, с доказателство, всички възможни стойности на наредената двойка (m,n)(m,n).
РешениеОтговорът еm≤n+1.m\le n+1.Необходимостта е непосредствена: всеки блок има между 00 и nn червени мъниста, тоест има само n+1n+1 възможни броя. Щом mm блока трябва винаги да дават различни броеве, необходимо е m≤n+1m\le n+1. Остава конструкцията. Първо разглеждаме граничния случай m=n+1m=n+1. Подреждаме огърлицата като таблица с n+1n+1 реда и nn стълба, четена ред по ред. В реда с номер kk отдолу нагоре поставяме първо kk червени мъниста, а след тях n−kn-k сини мъниста. Ако k<nk\lt{}n, последното синьо мънисто в този ред означаваме с Bn−kB_{n-k}; тези означения са само за проследяване при разместване на разрезите. След ii премествания на всички разрези с една позиция, където 0≤i<n0\le i\lt{}n, проследяването на мънистата B1,B2,…,BnB_1,B_2,\ldots,B_n дава следния брой червени мъниста в реда с номер kk отдолу нагоре:{k,k>i,k−1,i≥k>0,i,k=0.\begin{cases} k,&k\gt{}i,\\ k-1,&i\ge k\gt{}0,\\ i,&k=0. \end{cases}Тези числа са точно 0,1,…,n0,1,\ldots,n в някакъв ред, следователно всички n+1n+1 блока имат различен брой червени мъниста. Понеже всеки възможен разрез се получава от някое i=0,1,…,n−1i=0,1,\ldots,n-1, конструкцията работи за m=n+1m=n+1. Ако m<n+1m\lt{}n+1, започваме от вече построената огърлица за двойката (m,m−1)(m,m-1). След това към началото на всеки блок добавяме n+1−mn+1-m сини мъниста. Тези добавени сини мъниста не променят броя на червените мъниста; при преместване на разрезите те само забавят момента, в който се стига до старата конструкция. Следователно различните блокове отново имат различен брой червени мъниста за всеки разрез. Така конструкция съществува за всички m≤n+1m\le n+1, а необходимостта вече беше доказана.
Отвори задачатаEvan Chen VONVON USAMO 2024/4Условие — източник

Задача 5

Пълен запис
Условие
Вътре в остроъгълен триъгълник ABCABC е избрана точка DD така, че ∠DAC=∠ACB\angle DAC=\angle ACB и ∠BDC=90∘+∠BAC\angle BDC=90^\circ+\angle BAC. Точка EE е избрана върху лъча BDBD така, че AE=ECAE=EC. Нека MM е средата на BCBC. Да се докаже, че правата ABAB е допирателна към описаната окръжност на триъгълника BEMBEM.
РешениеДострояваме равнобедрен трапец ABQCABQC с основи ACAC и BQBQ, така че DD лежи на диагонала AQAQ; това е точно условието ∠DAC=∠ACB\angle DAC=\angle ACB. Нека FF е образът на BB при централна симетрия спрямо EE, т.е. EE е средата на BFBF. Ще докажем, че точките D,Q,C,FD,Q,C,F лежат на една окръжност. Понеже EA=ECEA=EC, точката EE лежи на симетралата на ACAC. Хомотетията с център BB и коефициент 22 изпраща EE във FF и тази симетрала в правата QFQF, следователно QF⊥ACQF\perp AC. Оттук ∠FQC=90∘−∠QCA\angle FQC=90^\circ-\angle QCA. В равнобедрения трапец ABQCABQC имаме ∠QCA=∠BAC\angle QCA=\angle BAC, а от условието ∠BDC=90∘+∠BAC\angle BDC=90^\circ+\angle BAC. Следователно ∠FDC=180∘−∠BDC=90∘−∠BAC=∠FQC\angle FDC=180^\circ-\angle BDC=90^\circ-\angle BAC=\angle FQC, което доказва, че DQCFDQCF е вписан. Накрая EE е средата на BFBF, а MM е средата на BCBC, затова в триъгълника BCFBCF отсечката EMEM е средна отсечка и EM∥CFEM\parallel CF. Следователно ∠BEM=∠BFC=∠DFC=∠DQC=∠AQC=∠ABC=∠ABM\angle BEM=\angle BFC=\angle DFC=\angle DQC=\angle AQC=\angle ABC=\angle ABM. Равенството между ъгъла между допирателната ABAB и хордата BMBM и вписания ъгъл BEMBEM показва, че ABAB е допирателна към описаната окръжност на BEMBEM в точката BB.ABCQDEMF
Отвори задачатаEvan Chen VONVON USAMO 2024/5Условие — източник

Задача 6

Пълен запис
Условие
Нека n>2n\gt{}2 е цяло число и нека ℓ∈{1,2,…,n}\ell\in\{1,2,\ldots,n\}. Колекция A1,…,AkA_1,\ldots,A_k от не непременно различни подмножества на {1,2,…,n}\{1,2,\ldots,n\} се нарича ℓ\ell-голяма, ако ∣Ai∣≥ℓ|A_i|\ge\ell за всяко 1≤i≤k1\le i\le k. Да се намери, чрез nn и ℓ\ell, най-голямото реално число cc, за което неравенството∑i=1k∑j=1kxixj∣Ai∩Aj∣2∣Ai∣⋅∣Aj∣≥\sum_{i=1}^k\sum_{j=1}^k x_ix_j\frac{|A_i\cap A_j|^2}{|A_i|\cdot|A_j|}\gec(∑i=1kxi)2 c\left(\sum_{i=1}^k x_i\right)^2е изпълнено за всяко положително цяло число kk, всички неотрицателни реални числа x1,x2,…,xkx_1,x_2,\ldots,x_k и всички ℓ\ell-големи колекции A1,A2,…,AkA_1,A_2,\ldots,A_k от подмножества на {1,2,…,n}\{1,2,\ldots,n\}.
РешениеОтговорът еc=n+ℓ2−2ℓn(n−1).c=\frac{n+\ell^2-2\ell}{n(n-1)}.Без ограничение можем да приемем, че ∑ixi=1\sum_i x_i=1. Пишем [n]={1,2,…,n}[n]=\{1,2,\ldots,n\}. За всяка наредена двойка (p,q)∈[n]2(p,q)\in[n]^2 дефинирамеvp,q=∑i: p,q∈Aixi∣Ai∣.v_{p,q}=\sum_{i:\ p,q\in A_i}\frac{x_i}{|A_i|}.Тогава, понеже ∣Ai∩Aj∣2|A_i\cap A_j|^2 брои наредените двойки (p,q)(p,q), за които p,q∈Ai∩Ajp,q\in A_i\cap A_j, имаме∑i,jxixj∣Ai∩Aj∣2∣Ai∣∣Aj∣=∑p∈[n]∑q∈[n]vp,q2.\begin{align*} \sum_{i,j}x_ix_j\frac{|A_i\cap A_j|^2}{|A_i||A_j|} &=\sum_{p\in[n]}\sum_{q\in[n]}v_{p,q}^2. \end{align*}Сега разделяме сумата на диагонални и недиагонални членове. За диагонала получаваме∑p∈[n]vp,p=∑i∣Ai∣⋅xi∣Ai∣=∑ixi=1.\sum_{p\in[n]}v_{p,p}=\sum_i |A_i|\cdot\frac{x_i}{|A_i|}=\sum_i x_i=1.По неравенството между квадратично и аритметично средно∑p∈[n]vp,p2≥1n.\sum_{p\in[n]}v_{p,p}^2\ge\frac1n.За недиагоналните членове имаме∑p≠qvp,q=∑i∣Ai∣(∣Ai∣−1)⋅xi∣Ai∣=∑i(∣Ai∣−1)xi≥(ℓ−1)∑ixi=ℓ−1.\begin{align*} \sum_{p\ne q}v_{p,q} &=\sum_i |A_i|(|A_i|-1)\cdot\frac{x_i}{|A_i|}\\ &=\sum_i (|A_i|-1)x_i\ge(\ell-1)\sum_i x_i=\ell-1. \end{align*}Отново по същото неравенство,∑p≠qvp,q2≥(ℓ−1)2n(n−1).\sum_{p\ne q}v_{p,q}^2\ge\frac{(\ell-1)^2}{n(n-1)}.Следователно лявата страна на задачата е поне1n+(ℓ−1)2n(n−1)=n+ℓ2−2ℓn(n−1).\frac1n+\frac{(\ell-1)^2}{n(n-1)}=\frac{n+\ell^2-2\ell}{n(n-1)}.Това доказва, че посоченото cc винаги работи. Остава да покажем, че то е най-голямото възможно. Вземаме k=(nℓ)k=\binom n\ell и нека множествата AiA_i са всички ℓ\ell-елементни подмножества на [n][n], всяко по веднъж. Избираме всички xix_i равни. По симетрия всички диагонални величини vp,pv_{p,p} са равни, всички недиагонални vp,qv_{p,q} с p≠qp\ne q също са равни, и навсякъде ∣Ai∣=ℓ|A_i|=\ell. Затова всички неравенства в доказаната по-горе оценка стават равенства. Следователно по-голямо cc не може да работи, и отговорът е именноn+ℓ2−2ℓn(n−1).\boxed{\frac{n+\ell^2-2\ell}{n(n-1)}}.
Отвори задачатаEvan Chen VONVON USAMO 2024/6Условие — източник