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

Evan Chen / USAMO Solution Notes

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

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

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

2025

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Нека kk и dd са фиксирани положителни цели числа. Да се докаже, че за всяко достатъчно голямо нечетно положително цяло число nn всички цифри в записа на nkn^k в бройна система с основа 2n2n са по-големи от dd.
РешениеНека 1≤ℓ≤k1\le\ell\le k. Ще разгледаме най-десните ℓ\ell цифри на nkn^k в основа 2n2n, тоест остатъка rℓr_\ell на nkn^k при деление на (2n)ℓ(2n)^\ell. Твърдим, че съществува нечетно цяло число cℓc_\ell с 1≤cℓ≤2ℓ−11\le c_\ell\le 2^\ell-1 такова, че rℓ=cℓnℓ.r_\ell=c_\ell n^\ell. Действително остатъкът rℓr_\ell е кратен на nℓn^\ell, а след деление на nℓn^\ell трябва да изберем клас по модул 2ℓ2^\ell. Понеже nn е нечетно, китайската теорема за остатъците дава точно класа cℓ≡nk−ℓ(mod2ℓ),c_\ell\equiv n^{k-\ell}\pmod{2^\ell}, който е нечетен. Сега ще покажем, че прагът n≥(d+1)2k−1n\ge(d+1)2^{k-1} е достатъчен. При такова nn числото nkn^k има точно kk цифри в основа 2n2n, защото (2n)k−1≤nk<(2n)k.(2n)^{k-1}\le n^k\lt{}(2n)^k. За всяко ℓ=1,2,…,k\ell=1,2,\ldots,k имаме rℓ=cℓnℓ≥nℓ≥r_\ell=c_\ell n^\ell\ge n^\ell\ge(d+1)2ℓ−1nℓ−1=(d+1)(2n)ℓ−1.(d+1)2^{\ell-1}n^{\ell-1}=(d+1)(2n)^{\ell-1}. Но ℓ\ell-тата цифра отдясно е цялата част на rℓ/(2n)ℓ−1r_\ell/(2n)^{\ell-1}, следователно тя е поне d+1d+1. Това важи за всички kk цифри на nkn^k, така че всяка от тях е по-голяма от dd.
Отвори задачатаEvan Chen VONVON USAMO 2025/1Условие — източник

Задача 2

Пълен запис
Условие
Нека n>k≥1n\gt{}k\ge1 са цели числа. Нека P(x)∈R[x]P(x)\in\mathbb R[x] е полином от степен nn без кратни корени и с P(0)≠0P(0)\ne0. Да предположим, че за всякакви реални числа a0,a1,…,aka_0,a_1,\ldots,a_k, за които полиномът akxk+⋯+a1x+a0a_kx^k+\cdots+a_1x+a_0 дели P(x)P(x), произведението a0a1⋯aka_0a_1\cdots a_k е равно на нула. Да се докаже, че P(x)P(x) има нереален корен.
РешениеЩе докажем контрапозицията. Ако всички корени на PP са реални, то ще получим делител от степен kk, чиито всички коефициенти са ненулеви. Първо можем да сведем задачата до случая n=k+1n=k+1: избираме произволни k+1k+1 корена на PP и разглеждаме произведението на съответните линейни множители; всеки негов делител от степен kk е и делител на PP. Така нека P(x)=(x+r1)(x+r2)⋯(x+rn),P(x)=(x+r_1)(x+r_2)\cdots(x+r_n), където всички rir_i са реални, ненулеви и две по две различни. За всяко ii полиномът Pi(x)=P(x)x+riP_i(x)=\frac{P(x)}{x+r_i} има степен n−1=kn-1=k, следователно по условие поне един негов коефициент е нула. Водещият и свободният коефициент на PiP_i са ненулеви, така че нулевият коефициент трябва да е на някоя от степените x,x2,…,xn−2x,x^2,\ldots,x^{n-2}. Има nn полинома PiP_i, но само n−2n-2 такива позиции, затова по принципа на Дирихле два от тях имат нулев коефициент на една и съща степен. Нека това са P1P_1 и P2P_2, и нека общата степен е xtx^t. Пишем Q(x)=(x+r3)(x+r4)⋯(x+rn)=Q(x)=(x+r_3)(x+r_4)\cdots(x+r_n)=xn−2+bn−3xn−3+⋯+b0,x^{n-2}+b_{n-3}x^{n-3}+\cdots+b_0, като поставяме bn−2=1b_{n-2}=1. Коефициентът пред xtx^t в (x+r1)Q(x)(x+r_1)Q(x) е bt−1+r1btb_{t-1}+r_1b_t, а в (x+r2)Q(x)(x+r_2)Q(x) е bt−1+r2btb_{t-1}+r_2b_t. И двата са нула, следователно (r1−r2)bt=0(r_1-r_2)b_t=0. Понеже r1≠r2r_1\ne r_2, получаваме bt=0b_t=0, а после и bt−1=0b_{t-1}=0. Значи QQ има две последователни нулеви коефициента. Остава един стандартен факт: реален полином с всички корени реални и различни не може да има две последователни нулеви коефициента. Наистина, ако коефициентите пред xsx^s и xs+1x^{s+1} са нула, то ss-тата производна на полинома има двоен корен в 00. От друга страна, ако началният полином има само реални прости корени, то по теоремата на Рол всяка негова производна също има само реални прости корени. Това е противоречие. Следователно QQ, а значи и PP, има нереален корен.
Отвори задачатаEvan Chen VONVON USAMO 2025/2Условие — източник

Задача 3

Пълен запис
Условие
Архитектката Алис и строителят Боб играят игра. Първо Алис избира две точки PP и QQ в равнината и подмножество S\mathcal S на равнината, като те се съобщават на Боб. След това Боб отбелязва безкрайно много точки в равнината и обявява всяка от тях за град. Той няма право да поставя два града на разстояние най-много 11 един от друг, а никои три от поставените градове не могат да бъдат колинеарни. Накрая между градовете се строят пътища по следното правило: всяка двойка градове A,BA,B се свързва с път по отсечката ABAB тогава и само тогава, когато е изпълнено условието: за всеки град CC, различен от AA и BB, съществува R∈SR\in\mathcal S, така че △PQR\triangle PQR е директно подобен (със същата ориентация) на △ABC\triangle ABC или на △BAC\triangle BAC. Алис печели, ако (i) получените пътища позволяват пътуване между всеки два града чрез краен брой пътища и (ii) никои два пътя не се пресичат. В противен случай печели Боб. Определете, с доказателство, кой от двамата играчи има печеливша стратегия.
РешениеОтговорът е, че Алис печели. Ще наричаме множество V⊆R2V\subseteq\mathbb R^2 множество на Боб, ако никои три негови точки не са колинеарни и разстоянието между всеки две негови точки е по-голямо от 11. За такова множество построяваме графа на Боб: върховете са точките на VV, а две точки a,b∈Va,b\in V са свързани с ребро тогава и само тогава, когато затвореният диск с диаметър ab‾\overline{ab} не съдържа друга точка от VV нито във вътрешността си, нито върху границата си. Ще докажем, че всеки такъв граф е свързан и планарен. Това ще даде стратегия за Алис: тя избира S\mathcal S да бъде множеството от точките извън затворения диск с диаметър PQPQ. Тогава за градове A,BA,B и трети град CC съществуването на подходяща точка R∈SR\in\mathcal S е точно условието CC да не лежи в затворения диск с диаметър ABAB. Следователно построените пътища са точно ребрата на графа на Боб. Първо доказваме свързаността. Да допуснем противното и да изберем точки pp и qq в различни свързани компоненти. Понеже pqpq не е ребро, има трета точка rr в затворения диск с диаметър pq‾\overline{pq}. Точката rr е в различна компонента от поне една от точките p,qp,q; без ограничение нека това е pp. Сега повтаряме същия аргумент за двойката p,rp,r: понеже тези две точки са в различни компоненти, отсечката prpr не е ребро и в диска с диаметър pr‾\overline{pr} има нова точка. Продължавайки така, получаваме безкрайна редица от разстояния δ1,δ2,δ3,…\delta_1,\delta_2,\delta_3,\ldots между двойки точки, които лежат в различни компоненти. На всяка стъпка новата точка лежи в диска с диаметър на предишната двойка. Ако новото разстояние е δi\delta_i, а предишното е δi−1\delta_{i-1}, то другото разстояние от новата точка до краищата на предишната двойка е по-голямо от 11. От неравенството на Питагор за точка в диск с даден диаметър получавамеδi2<δi−12−1.\delta_i^2\lt{}\delta_{i-1}^2-1.Следователно 0≤δi2<δ12−(i−1)0\le\delta_i^2\lt{}\delta_1^2-(i-1), което е невъзможно за достатъчно голямо ii. Значи графът на Боб е свързан. Остава планарността. Ако две ребра acac и bdbd се пресичат, то abcdabcd е изпъкнал четириъгълник. Някой от ъглите му е поне 90∘90^\circ; без ограничение нека ∠bad≥90∘\angle bad\ge90^\circ. Тогава точката aa лежи в затворения диск с диаметър bd‾\overline{bd}, което противоречи на това, че bdbd е ребро. Следователно никои две ребра не се пресичат, тоест графът е планарен. Това завършва доказателството на стратегията на Алис.pqrsδ1δ2δ3
Отвори задачатаEvan Chen VONVON USAMO 2025/3Условие — източник

Задача 5

Пълен запис
Условие
Да се намерят всички положителни цели числа kk, такива че за всяко положително цяло число nn сумата (n0)k+(n1)k+⋯+(nn)k\binom{n}{0}^k+\binom{n}{1}^k+\cdots+\binom{n}{n}^k се дели на n+1n+1.
РешениеОтговорът е: точно четните положителни цели числа kk. Нека S(n)=∑i=0n(ni)k.S(n)=\sum_{i=0}^n\binom{n}{i}^k. Необходимостта е кратка: при n=2n=2 трябва 33 да дели S(2)=2+2kS(2)=2+2^k. Това става точно когато kk е четно. Сега нека kk е фиксирано четно число. Ще докажем, че всяка проста степен, която дели n+1n+1, дели и S(n)S(n). Нека pe∣n+1p^e\mid n+1. Ще използваме следната лема: за всяко 0≤i≤n0\le i\le n е изпълнено (ni)≡±((n+1)/p−1⌊i/p⌋)(modpe).\binom{n}{i}\equiv\pm\binom{(n+1)/p-1}{\lfloor i/p\rfloor}\pmod{p^e}. За доказателство записваме (ni)=∏j=1in−j+1j.\binom{n}{i}=\prod_{j=1}^i\frac{n-j+1}{j}. Ако p∤jp\nmid j, то n−j+1≡−j(modpe)n-j+1\equiv-j\pmod{p^e} и съответният множител дава само знак. Ако j=ℓpj=\ell p, тогава съответният множител е точно n−ℓp+1ℓp=(n+1)/p−ℓℓ.\frac{n-\ell p+1}{\ell p}=\frac{(n+1)/p-\ell}{\ell}. Произведението на тези специални множители за ℓ=1,2,…,⌊i/p⌋\ell=1,2,\ldots,\lfloor i/p\rfloor е ((n+1)/p−1⌊i/p⌋),\binom{(n+1)/p-1}{\lfloor i/p\rfloor}, което доказва лемата. Понеже kk е четно, знаците изчезват след повдигане на kk-та степен. Като групираме членовете според стойността на ⌊i/p⌋\lfloor i/p\rfloor, всяка стойност се среща точно pp пъти, и получаваме S(n)≡p S((n+1)/p−1)(modpe).S(n)\equiv p\,S((n+1)/p-1)\pmod{p^e}. Индукция по ee вече завършва доказателството. За e=1e=1 дясната страна е кратна на pp. Ако e>1e\gt{}1, то pe−1∣(n+1)/pp^{e-1}\mid (n+1)/p, затова по индукционното предположение S((n+1)/p−1)S((n+1)/p-1) е кратно на pe−1p^{e-1}, а след умножение по pp получаваме pe∣S(n)p^e\mid S(n). Това важи за всяка проста степен в разлагането на n+1n+1, следователно n+1∣S(n)n+1\mid S(n) за всяко положително nn.
Отвори задачатаEvan Chen VONVON USAMO 2025/5Условие — източник

Задача 6

Пълен запис
Условие
Нека mm и nn са положителни цели числа с m≥nm\ge n. В кръг са наредени mm кексчета с различни вкусове и има nn души, които обичат кексчета. Всеки човек задава неотрицателна реална оценка на всяко кексче според това колко го харесва. Да предположим, че за всеки човек PP е възможно кръгът от mm кексчета да се раздели на nn групи от последователни кексчета така, че сумата от оценките на PP за кексчетата във всяка група да е поне 11. Да се докаже, че е възможно mm-те кексчета да се разпределят между nn-те души така, че всеки човек PP да получи кексчета с обща оценка поне 11 според неговите оценки.
РешениеДоказваме твърдението с индукция по nn, като случаят n=1n=1 е очевиден. Избираме произволно един човек и ще го наричаме Пип. Фиксираме едно разделяне на кръга на nn дъги, което е добро за Пип, тоест всяка от тези дъги има стойност поне 11 според Пип. Построяваме двуделен граф GG между хората и тези nn дъги: свързваме човек QQ с дъга AA, ако QQ оценява кексчетата в AA с обща стойност поне 11. Пип е свързан с всички дъги. Ще използваме лемата на Хол. Ако GG има съчетание, което покрива всички хора, веднага раздаваме на всеки човек съответната дъга и сме готови. Иначе има лошо множество B1B_1 от хора, чието съседство има по-малко от ∣B1∣|B_1| дъги. Изтриваме хората от B1B_1 и всички техни съседни дъги и повтаряме същата процедура върху останалия двуделен граф. Ако пак няма съчетание, което покрива всички останали хора, намираме ново лошо множество B2B_2, изтриваме него и неговите съседи, и продължаваме. Процесът задължително спира. На всяка стъпка изтриваме повече хора, отколкото дъги, така че броят на оставащите дъги е поне броя на оставащите хора. Освен това Пип никога не може да лежи в лошо множество, защото е съседен на всички оставащи дъги. Следователно накрая остава непразен граф, в който по Хол има съчетание MM, покриващо всички останали хора. Раздаваме на тези хора съответните дъги от MM. Остават хората, които са били изтрити в някое от лошите множества. Нека Куин е един от тях. Куин не харесва нито една от дъгите, раздадени чрез MM: ако харесваше такава дъга, тя щеше да е съседна на Куин и щеше да бъде изтрита още когато е било изтрито лошото множество, съдържащо Куин. Значи всяка дъга от MM има стойност по-малка от 11 според Куин. Да видим какво става със собственото добро разделяне на Куин, когато изтрием една дъга AA от MM. Понеже стойността на AA за Куин е по-малка от 11, тази дъга не може да съдържа изцяло нито една от групите на Куин, всяка от които има стойност поне 11. Следователно AA пресича най-много една граница между групите на Куин. Ако пресече такава граница, двете съседни групи се сливат; новата група има стойност поне 1+1−1=1,1+1-1=1, защото сме премахнали част с обща стойност по-малка от 11. Ако не пресече граница, след премахването все още имаме групи със стойност поне 11 и просто сливаме произволни две съседни групи. И в двата случая броят на групите намалява с 11, а всички останали групи имат стойност поне 11. Повтаряме това за всички дъги от MM. За всеки останал човек получаваме разделяне на оставащите кексчета на точно толкова последователни групи, колкото са останалите хора, и всяка група има стойност поне 11 за съответния човек. По индукционното предположение можем да разпределим оставащите кексчета между останалите хора. Заедно с вече раздадените дъги от MM това дава търсеното разпределение за всички nn души.граф на Холиндукционна стъпкаПипQ1Q2Q3A1A2A3A4BN(B)зелените ребра образуват Mгрупи на КуинA от Mсъседни групи се сливат<1
Отвори задачатаEvan Chen VONVON USAMO 2025/6Условие — източник