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

Evan Chen / USAMO Solution Notes

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

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

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

2020

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

11-12

4 задачи

Задача 3

Пълен запис
Условие
Нека pp е нечетно просто число. Цяло число xx се нарича квадратичен неостатък по модул pp, ако pp не дели x−t2x-t^2 за никое цяло число tt. Нека AA е множеството от всички aa с 1≤a<p1\le a\lt{}p, за които и aa, и 4−a4-a са квадратични неостатъци. Да се намери остатъкът по модул pp на произведението на елементите на AA.
РешениеОтговорът е 22 по модул pp. Работим в Fp\mathbb F_p и пишем КО за квадратичен остатък и КНО за квадратичен неостатък. Нека AA е множеството от aa, за които aa и 4−a4-a са КНО, а BB е множеството от b≠0,4b\ne0,4, за които bb и 4−b4-b са КО. Тогава A∪BA\cup B са точно ненулевите n≠4n\ne4, за които n(4−n)n(4-n) е КО. Разглеждаме φ(n)=n(4−n)\varphi(n)=n(4-n) върху A∪B∖{2}A\cup B\setminus\{2\}. Понеже 4−n(4−n)=(n−2)24-n(4-n)=(n-2)^2, образът лежи в BB. Обратно, за всяко b∈Bb\in B уравнението n(4−n)=bn(4-n)=b има дискриминанта 4(4−b)4(4-b), тоест два корена nn и 4−n4-n. Значи φ\varphi е двукратно покритие на BB. Умножавайки произведенията на двата прообраза, получаваме ∏n∈A∪B∖{2}n=∏b∈Bb\prod_{n\in A\cup B\setminus\{2\}}n=\prod_{b\in B}b. Лявата страна е 12∏a∈Aa∏b∈Bb\frac12\prod_{a\in A}a\prod_{b\in B}b, така че след съкращаване ∏a∈Aa≡2(modp)\prod_{a\in A}a\equiv2\pmod p.
Отвори задачатаEvan Chen VONVON USAMO 2020/3Условие — източник

Задача 4

Пълен запис
Условие
Нека (a1,b1),…,(a100,b100)(a_1,b_1),\ldots,(a_{100},b_{100}) са различни решетъчни точки с неотрицателни координати. Нека NN е броят на двойките i<ji\lt{}j, за които ∣aibj−ajbi∣=1|a_i b_j-a_j b_i|=1. Да се намери най-голямата възможна стойност на NN.
РешениеОтговорът е 197197. По-общо за nn точки максимумът е 2n−32n-3. Конструкцията е (1,0),(1,1),(2,1),…,(n−1,1)(1,0),(1,1),(2,1),\ldots,(n-1,1). Добри триъгълници са O,(k,1),(k+1,1)O,(k,1),(k+1,1) за 1≤k≤n−21\le k\le n-2 и O,(1,0),(k,1)O,(1,0),(k,1) за 1≤k≤n−11\le k\le n-1, общо 2n−32n-3. За горната граница нека P=(a,b)P=(a,b) е най-далечната избрана решетъчна точка от началото. Ако gcd⁡(a,b)>1\gcd(a,b)\gt{}1, тя не участва в добър триъгълник, защото общият делител дели всеки детерминант av−buav-bu. Ако gcd⁡(a,b)=1\gcd(a,b)=1, решетъчните точки Q=(u,v)Q=(u,v) с лице [OPQ]=12[OPQ]=\frac12 лежат върху двете прави ∣av−bu∣=1|av-bu|=1, успоредни на OPOP. На всяка такава права решетъчните точки се различават с кратно на (a,b)(a,b); поради избора на най-далечна точка най-много една от всяка права може да присъства. Значи PP е в най-много два добри триъгълника. Изтриваме PP и прилагаме индукция: получаваме най-много 2(n−1)−3+2=2n−32(n-1)-3+2=2n-3. При n=100n=100 това дава 197197.
Отвори задачатаEvan Chen VONVON USAMO 2020/4Условие — източник

Задача 5

Пълен запис
Условие
Крайно множество SS от точки се нарича свръхопределено, ако ∣S∣≥2|S|\ge2 и има ненулев реален многочлен P(t)P(t) от степен най-много ∣S∣−2|S|-2, който минава през всички точки на SS. За всяко n≥2n\ge2 да се намери най-голямото kk, за което има множество от nn различни точки, което не е свръхопределено, но има kk свръхопределени подмножества.
РешениеОтговорът е 2n−1−n2^{n-1}-n. За конструкция избираме различни ненулеви a,ba,b и точките (1,a),(2,b),(3,b),…,(n,b)(1,a),(2,b),(3,b),\ldots,(n,b). Цялото множество не е свръхопределено: ако многочлен от степен най-много n−2n-2 минава през всички точки, то P(t)−bP(t)-b има корени 2,3,…,n2,3,\ldots,n, но не е нулев, защото P(1)=a≠bP(1)=a\ne b. От друга страна всяко подмножество от последните n−1n-1 точки с поне два елемента лежи върху константния многочлен P(t)=bP(t)=b, следователно е свръхопределено; техният брой е 2n−1−1−(n−1)=2n−1−n2^{n-1}-1-(n-1)=2^{n-1}-n. За горната граница наричаме множество свободно, ако не е свръхопределено. Ако свободно mm-множество има две свръхопределени (m−1)(m-1)-подмножества, съответните многочлени от степен най-много m−3m-3 съвпадат върху m−2m-2 общи точки и по единствеността от интерполация са един и същ многочлен; тогава цялото множество би било свръхопределено. Значи всяко свободно mm-множество има поне m−1m-1 свободни подмножества от размер m−1m-1. Низходяща индукция дава поне (n−1m−1)\binom{n-1}{m-1} свободни mm-подмножества, откъдето свръхопределените са най-много 2n−1−n2^{n-1}-n.
Отвори задачатаEvan Chen VONVON USAMO 2020/5Условие — източник

Задача 6

Пълен запис
Условие
Нека n≥2n\ge2 и нека x1≥x2≥⋯≥xnx_1\ge x_2\ge\cdots\ge x_n, y1≥y2≥⋯≥yny_1\ge y_2\ge\cdots\ge y_n са реални числа, за които сумите на всяка от двете редици са 00, а сумите на квадратите им са 11. Да се докаже, че ∑i=1n(xiyi−xiyn+1−i)≥2x2n−1\sum_{i=1}^n(x_i y_i-x_i y_{n+1-i})\ge\frac{2}{\sqrt{\vphantom{x^2}n-1}}.
РешениеНека σ\sigma е равномерно случайна пермутация и Sσ=∑i=1nxiyσ(i)S_\sigma=\sum_{i=1}^n x_i y_{\sigma(i)}. От условията ∑xi=∑yi=0\sum x_i=\sum y_i=0 следва ESσ=0\mathbb E S_\sigma=0. Освен това E(yσ(i)2)=1n\mathbb E(y_{\sigma(i)}^2)=\frac1n, а при i≠ji\ne j имаме E(yσ(i)yσ(j))=−1n(n−1)\mathbb E(y_{\sigma(i)}y_{\sigma(j)})=-\frac1{n(n-1)}, защото сумата на квадратите на yiy_i е 11 и сумата им е 00. Следователно, използвайки ∑xi2=1\sum x_i^2=1 и 2∑i<jxixj=−12\sum_{i\lt{}j}x_i x_j=-1, получаваме E(Sσ2)=1n+1n(n−1)=1n−1\mathbb E(S_\sigma^2)=\frac1n+\frac1{n(n-1)}=\frac1{n-1}. Това е дисперсията. Ако MM и mm са съответно най-голямата и най-малката стойност на SσS_\sigma, всяка случайна величина в интервал с дължина M−mM-m има дисперсия най-много (M−m)24\frac{(M-m)^2}{4}, например от (Z−m)(M−Z)≥0(Z-m)(M-Z)\ge0. Значи M−m≥2x2n−1M-m\ge\frac2{\sqrt{\vphantom{x^2}n-1}}. По неравенството за пренареждане максимумът е M=∑xiyiM=\sum x_i y_i, а минимумът е m=∑xiyn+1−im=\sum x_i y_{n+1-i}. Разликата им е точно лявата страна, което доказва твърдението.
Отвори задачатаEvan Chen VONVON USAMO 2020/6Условие — източник