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

Evan Chen / USAMO Solution Notes

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

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

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

2009

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

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

  • 2009 · 11-12: липсва задача 5

11-12

4 задачи

Задача 2

Пълен запис
Условие
Нека nn е положително цяло число. Да се определи най-големият възможен брой елементи на подмножество на {−n,−n+1,…,n−1,n}\{-n,-n+1,\ldots,n-1,n\}, което не съдържа три елемента a,b,ca,b,c, не непременно различни, за които a+b+c=0a+b+c=0.
РешениеОтговорът е nn при четно nn и n+1n+1 при нечетно nn. Конструкцията е да вземем всички нечетни числа в интервала: сборът на три нечетни числа е нечетен, следователно не може да е 00. При четно nn тези числа са nn, а при нечетно nn са n+1n+1. Остава да докажем, че това е максимумът. Достатъчно е да разгледаме четно nn, защото ако nn е нечетно, всяко допустимо множество в {−n,…,n}\{-n,\ldots,n\} е също допустимо подмножество на {−(n+1),…,n+1}\{-(n+1),\ldots,n+1\}, а n+1n+1 е четно. Ще докажем твърдението за четно nn с индукция по nn. Базата n=2n=2 е непосредствена. Нека AA е допустимо множество. Ако∣A∩{−n,−n+1,n−1,n}∣≤2,|A\cap\{-n,-n+1,n-1,n\}|\le2,то от индукционното предположение за интервала {−(n−2),…,n−2}\{-(n-2),\ldots,n-2\} получаваме∣A∣≤(n−2)+2=n.|A|\le(n-2)+2=n.Затова можем да предположим, че сред четирите крайни числа са избрани поне три. Ако и nn, и −n-n са в AA, тогава 00 не може да е в AA, а за всяко 1≤k≤n−11\le k\le n-1 не можем едновременно да изберем kk и n−kn-k, нито едновременно −k-k и −(n−k)-(n-k). При k=n/2k=n/2 това означава, че n/2n/2 и −n/2-n/2 изобщо не могат да се изберат. Следователно извън {−n,n}\{-n,n\} има най-много n−2n-2 елемента и пак ∣A∣≤n|A|\le n. Остава случаят, в който точно едно от числата nn и −n-n е избрано. След смяна на знаците можем да считаме, че n∈An\in A и −n∉A-n\notin A. Понеже са избрани поне три крайни числа, трябва да имаме n−1,−n+1∈An-1,-n+1\in A. Тогава −1-1 и 00 не могат да принадлежат на AA. Освен това от числата 1,2,…,n−21,2,\ldots,n-2 можем да изберем най-много по едно от всяка двойка със сбор n−1n-1, а от числата −2,−3,…,−n+2-2,-3,\ldots,-n+2 можем да изберем най-много по едно от всяка двойка със сбор −n-n; при средната стойност това дори забранява съответното число. Така към трите вече избрани крайни числа могат да се добавят най-много n−3n-3 други елемента. Следователно ∣A∣≤3+(n−3)=n|A|\le3+(n-3)=n. Индукцията завършва доказателството за четно nn, а с това и цялото твърдение.
Отвори задачатаEvan Chen VONVON USAMO 2009/2Условие — източник

Задача 3

Пълен запис
Условие
Наричаме шахматен многоъгълник прост многоъгълник, чиито страни лежат върху прави от вида x=ax=a или y=by=b, където aa и bb са цели числа. Тези прави разделят вътрешността му на единични квадратчета, оцветени последователно в сиво и бяло така, че съседни квадратчета имат различни цветове. Замощаване с домина означава точно покриване на многоъгълника с неприпокриващи се правоъгълници 1×21\times2. Накрая наричаме едно замощаване изящно, ако в никой квадрат 2×22\times2 не се среща някоя от следните две лоши локални конфигурации: два хоризонтални домина, когато долното ляво квадратче на този квадрат е бяло, или два вертикални домина, когато долното ляво квадратче е черно. Докажете, че: (а) ако шахматен многоъгълник може да бъде замощен с домина, то той може да бъде замощен изящно; и (б) такова изящно замощаване е единствено.
РешениеПърво ще докажем съществуването с индукция по броя квадратчета. Избираме най-долното ляво квадратче ss на многоъгълника; без ограничение можем да приемем, че то е бяло, защото иначе разменяме имената на цветовете. Ако съществува някакво замощаване, в което ss е покрито от вертикално домино, изтриваме това домино и прилагаме индукционното предположение към останалия шахматен многоъгълник. Когато върнем вертикалното домино, не се появява лоша локална конфигурация, защото около най-долното ляво квадратче няма квадратчета отдолу и отляво. Остава случаят, в който във всяко замощаване квадратчето ss е покрито от хоризонтално домино. Изтриваме това домино и отново прилагаме индукция. Когато го върнем, единствената възможна нова лоша конфигурация би била друго хоризонтално домино точно над него в същия квадрат 2×22\times2. Но тогава тези две хоризонтални домина могат да се заменят с две вертикални, което би дало замощаване, в което ss е покрито вертикално. Това противоречи на предположението за случая. Следователно изящно замощаване съществува. Сега доказваме единствеността. Да допуснем, че има две различни изящни замощавания. Наслагваме ги; там, където се различават, домината образуват една или повече затворени вериги. Избираме една такава верига γ\gamma, която огражда област QQ, и я обхождаме обратно на часовниковата стрелка. Изместваме координатите така, че най-долният ляв връх на QQ да е s=(0,0)s=(0,0). В двете замощавания доминото при ss е различно: в едното е хоризонтално, а в другото вертикално. Проследяваме замощаването, което започва с вертикалното домино при ss. Условието за изящност принуждава следващите домина да образуват стълбицаp0=s=(0,0),p1=(1,0),p_0=s=(0,0),\quad p_1=(1,0),p2=(1,1),p3=(2,1),…,\quad p_2=(1,1),\quad p_3=(2,1),\quad \ldots,като домината се редуват вертикално, хоризонтално, вертикално, хоризонтално и т.н. Началото на тази принудена стълбица е показано на диаграмата. Нека ℓ\ell е правата y=x−1y=x-1. Веригата γ\gamma пресича ℓ\ell първо в точката b=(1,0)b=(1,0), а след това в някаква точка aa по пътя си. Домината от стълбицата са принудени да следват ℓ\ell от bb към aa. При точката aa следващото принудено домино трябва едновременно да остане вътре в QQ и да спази ориентацията на граничната верига γ\gamma; това е невъзможно, защото тогава или получаваме една от забранените локални конфигурации, или пресичаме ℓ\ell по-рано от избора на aa. Полученото противоречие показва, че две различни изящни замощавания не могат да съществуват. Заедно със съществуването това доказва, че изящното замощаване е точно едно.sab
Отвори задачатаEvan Chen VONVON USAMO 2009/3Условие — източник

Задача 4

Пълен запис
Условие
За n≥2n\ge2 нека a1,a2,…,ana_1,a_2,\ldots,a_n са положителни реални числа, за които (a1+a2+⋯+an)(1a1+1a2+⋯+1an)≤\left(a_1+a_2+\cdots+a_n\right)\left(\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}\right)\le(n+12)2.\left(n+\frac12\right)^2. Да се докаже, че max⁡(a1,a2,…,an)≤4min⁡(a1,a2,…,an).\max(a_1,a_2,\ldots,a_n)\le4\min(a_1,a_2,\ldots,a_n).
РешениеНека a1a_1 е най-голямото, а a2a_2 най-малкото от числата, и поставяме M=a1/a2M=a_1/a_2. Тогава M≥1M\ge1 и трябва да докажем M≤4M\le4. В лявата страна на даденото неравенство просто подреждаме първата сума като a2+a1+a3+⋯+ana_2+a_1+a_3+\cdots+a_n. По неравенството на Коши-Шварц получаваме(n+12)2≥\left(n+\frac12\right)^2\ge(a2+a1+a3+⋯+an)(1a1+1a2+1a3+⋯+1an)\left(a_2+a_1+a_3+\cdots+a_n\right)\left(\frac1{a_1}+\frac1{a_2}+\frac1{a_3}+\cdots+\frac1{a_n}\right)≥\ge(x2a2a1+x2a1a2+1+⋯+1)2=\left(\sqrt{\vphantom{x^2}\frac{a_2}{a_1}}+\sqrt{\vphantom{x^2}\frac{a_1}{a_2}}+1+\cdots+1\right)^2=(1M+M+n−2)2.\left(\frac1{\sqrt M}+\sqrt M+n-2\right)^2.Всички величини са положителни, следователноM+1M≤52.\sqrt M+\frac1{\sqrt M}\le\frac52.Ако означим t=Mt=\sqrt M, то t≥1t\ge1 и последното неравенство дава2t2−5t+2≤0,2t^2-5t+2\le0,тоест(2t−1)(t−2)≤0.(2t-1)(t-2)\le0.Понеже t≥1t\ge1, оттук следва t≤2t\le2, а значи M=t2≤4M=t^2\le4. Това е точно исканото неравенство.
Отвори задачатаEvan Chen VONVON USAMO 2009/4Условие — източник

Задача 6

Пълен запис
Условие
Нека s1,s2,s3,…s_1,s_2,s_3,\ldots е безкрайна неконстантна редица от рационални числа, тоест не е вярно, че s1=s2=s3=⋯s_1=s_2=s_3=\cdots. Да предположим, че t1,t2,t3,…t_1,t_2,t_3,\ldots също е безкрайна неконстантна редица от рационални числа със свойството, че (si−sj)(ti−tj)(s_i-s_j)(t_i-t_j) е цяло число за всички ii и jj. Да се докаже, че съществува рационално число rr, такова че (si−sj)r(s_i-s_j)r и (ti−tj)/r(t_i-t_j)/r са цели числа за всички ii и jj.
РешениеПърво изключваме един граничен случай. Ще покажем, че има индекси i,ji,j, за които(si−sj)(ti−tj)≠0.(s_i-s_j)(t_i-t_j)\ne0.Ако това не е така, избираме s1≠s2s_1\ne s_2; тогава непременно t1=t2t_1=t_2. Понеже редицата tt е неконстантна, има индекс kk с tk≠t1t_k\ne t_1. От условието за двойките (k,1)(k,1) и (k,2)(k,2) следва едновременно sk=s1s_k=s_1 и sk=s2s_k=s_2, противоречие. След преномериране некаn=(s1−s2)(t1−t2)≠0.n=(s_1-s_2)(t_1-t_2)\ne0.По условие nn е цяло число. Сега правим нормализация, която не променя произведенията на разликите: изваждаме s1s_1 и t1t_1 и умножаваме редицата ss по 1/(s2−s1)1/(s_2-s_1), а редицата tt по s2−s1s_2-s_1. Така можем да работим приs1=t1=0,s2=1,t2=n.s_1=t_1=0,\qquad s_2=1,\qquad t_2=n.Ако намерим подходящо число в тази нормализирана ситуация, после връщането на мащаба дава търсеното рационално rr в първоначалната задача. От условието с j=1j=1 получавамеsiti∈Zза всички i.s_it_i\in\mathbb Z\qquad\text{за всички }i.Освен това, като разпишем (si−sj)(ti−tj)(s_i-s_j)(t_i-t_j) и използваме вече доказаното, намирамеsitj+sjti∈Zза всички i,j.s_it_j+s_jt_i\in\mathbb Z\qquad\text{за всички }i,j.В частност при j=2j=2 имамеti+nsi∈Zза всички i.t_i+ns_i\in\mathbb Z\qquad\text{за всички }i.Ще докажем, че ti∈Zt_i\in\mathbb Z и nsi∈Zns_i\in\mathbb Z за всяко ii. Нека pp е просто число и нека c=νp(n)≥0c=\nu_p(n)\ge0. От siti∈Zs_it_i\in\mathbb Z и ti+nsi∈Zt_i+ns_i\in\mathbb Z следва следното. Ако νp(ti)<0\nu_p(t_i)\lt{}0, то νp(si)>0\nu_p(s_i)\gt{}0, така че nsins_i има неотрицателна pp-адична оценка; тогава сумата ti+nsit_i+ns_i би имала отрицателна оценка, противоречие. Значи tit_i е цяло число. Ако пък νp(nsi)<0\nu_p(ns_i)\lt{}0, тоест νp(si)<−c\nu_p(s_i)\lt{}-c, тогава от siti∈Zs_it_i\in\mathbb Z следва νp(ti)>c\nu_p(t_i)\gt{}c; тогава отново ti+nsit_i+ns_i би имало отрицателна pp-адична оценка, противоречие. Следователно nsins_i също е цяло число. Нека dd е положителният най-голям общ делител на всички цели числа tit_i. Ще докажем, че dsi∈Zds_i\in\mathbb Z за всяко ii. За просто число pp поставяме e=νp(d)=min⁡jνp(tj)e=\nu_p(d)=\min_j\nu_p(t_j) и избираме индекс jj, за който минимумът се достига. От sjtj∈Zs_jt_j\in\mathbb Z следва νp(sj)≥−e\nu_p(s_j)\ge-e. Да допуснем, че за някой ii имаме νp(si)<−e\nu_p(s_i)\lt{}-e. Тогава от siti∈Zs_it_i\in\mathbb Z следва νp(ti)>e\nu_p(t_i)\gt{}e. Но в целия сборsitj+sjti∈Zs_it_j+s_jt_i\in\mathbb Zпървият член има pp-адична оценка νp(si)+e<0\nu_p(s_i)+e\lt{}0, а вторият има оценка поне −e+νp(ti)>0-e+\nu_p(t_i)\gt{}0. Следователно самият сбор би имал отрицателна pp-адична оценка, противоречие. Значи νp(si)≥−e\nu_p(s_i)\ge-e за всяко pp, тоест dsi∈Zds_i\in\mathbb Z. В нормализираната задача вече сме готови: понеже dsids_i е цяло число за всички ii, то d(si−sj)d(s_i-s_j) е цяло число за всички i,ji,j; а понеже dd дели всяко tit_i, числото (ti−tj)/d(t_i-t_j)/d също е цяло. Така можем да вземем r=dr=d в нормализираните означения, а след връщане на първоначалното мащабиране получаваме рационално число rr за изходните редици.
Отвори задачатаEvan Chen VONVON USAMO 2009/6Условие — източник