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

Evan Chen / USAMO Solution Notes

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

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

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

2010

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

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

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

11-12

4 задачи

Задача 2

Пълен запис
Условие
В кръг стоят nn ученици, един зад друг. Височините им са h1<h2<⋯<hnh_1\lt{}h_2\lt{}\cdots\lt{}h_n. Ако ученик с височина hkh_k стои непосредствено зад ученик с височина hk−2h_{k-2} или по-малка, двамата ученици могат да разменят местата си. Да се докаже, че не е възможно да се направят повече от (n3)\binom{n}{3} такива размени, преди да се стигне до разположение, при което повече размени не са възможни.
РешениеЩе докажем по-силно твърдение: учениците с височини hih_i и hjh_j могат да разменят местата си най-много ∣j−i∣−1|j-i|-1 пъти. Това очевидно е вярно при ∣j−i∣=1|j-i|=1, защото двама ученици със съседни индекси по височина никога не могат да бъдат разрешена двойка за размяна. Нека j>ij\gt{}i и d=j−i≥2d=j-i\ge2. Допускаме индукционно, че твърдението вече е доказано за по-малки стойности на dd. Проследяваме само тримата ученици hj,hi+1,hih_j,h_{i+1},h_i, като игнорираме всички останали. След първата размяна между hjh_j и hih_i техният относителен ред около кръга става такъв, че hjh_j трябва първо да размени място с hi+1h_{i+1}, преди отново да може да размени място с hih_i. По индукционното предположение двойката hj,hi+1h_j,h_{i+1} се разменя най-много j−(i+1)−1j-(i+1)-1 пъти. Следователно двойката hj,hih_j,h_i се разменя най-много1+igl(j-(i+1)-1igr)=j-i-1пъти, както искахме. Всяка размяна е размяна на някаква двойка ученици. Затова общият брой размени е най-много∑1≤i<j≤n(j−i−1).\sum_{1\le i\lt{}j\le n}(j-i-1).За всяка тройка индекси i<k<ji\lt{}k\lt{}j тя се брои точно веднъж в тази сума, именно като един от j−i−1j-i-1 избори за средния индекс kk. Следователно сумата е (n3)\binom{n}{3}, което завършва доказателството.
Отвори задачатаEvan Chen VONVON USAMO 2010/2Условие — източник

Задача 3

Пълен запис
Условие
20102010 положителни реални числа a1,a2,…,a2010a_1,a_2,\ldots,a_{2010} удовлетворяват неравенството aiaj≤i+ja_i a_j\le i+j за всички 1≤i<j≤20101\le i\lt{}j\le2010. Определете, с доказателство, най-голямата възможна стойност на произведението a1a2⋯a2010a_1a_2\cdots a_{2010}.
РешениеОтговорът е3⋅7⋅11⋯4019=∏k=11005(4k−1).3\cdot7\cdot11\cdots4019=\prod_{k=1}^{1005}(4k-1).Горната оценка е непосредствена: групираме членовете по двойки и използваме даденото неравенство:a1a2⋅a3a4⋯a2009a2010≤a_1a_2\cdot a_3a_4\cdots a_{2009}a_{2010}\le3⋅7⋅11⋯4019. 3\cdot7\cdot11\cdots4019.Остава да покажем, че тази стойност може да се достигне. За k=1,2,…,1005k=1,2,\ldots,1005 полагамеa2k=x24k,a2k−1=4k−1x24k.a_{2k}=\sqrt{\vphantom{x^2}4k},\qquad a_{2k-1}=\frac{4k-1}{\sqrt{\vphantom{x^2}4k}}.Тогава a2k−1a2k=4k−1a_{2k-1}a_{2k}=4k-1, така че произведението на всички aia_i е точно търсеното. Ще проверим, че всички неравенства aiaj≤i+ja_i a_j\le i+j са изпълнени. Ако i=2ri=2r и j=2sj=2s са четни, тоaiaj=4x2rs≤2r+2s=i+ja_i a_j=4\sqrt{\vphantom{x^2}rs}\le 2r+2s=i+jпо AM-GM. Ако i=2r−1i=2r-1 е нечетно, а j=2sj=2s е четно, от i<ji\lt{}j следва r≤sr\le s. След повдигане на квадрат желаното неравенство е еквивалентно на(2r+2s−1)2≥(4r−1)2sr.\left(2r+2s-1\right)^2\ge \frac{(4r-1)^2s}{r}.Разликата между лявата и дясната страна, умножена по rr, е(s−r)(4r(s−r)+4r−1)≥0,(s-r)\bigl(4r(s-r)+4r-1\bigr)\ge0,така че и този случай е доказан. Остава случаят i=2r−1i=2r-1, j=2s−1j=2s-1, където s>rs\gt{}r. Нека t=s−r≥1t=s-r\ge1. След повдигане на квадрат трябва да докажем2r+2s−2≥(4r−1)(4s−1)4x2rs.2r+2s-2\ge \frac{(4r-1)(4s-1)}{4\sqrt{\vphantom{x^2}rs}}.След умножаване на разликата на квадратите по 16rs16rs получавамеF(t)=F(t)=64r2t2−32r2+64rt3−32rt+16r−16t2+8t−1.64r^2t^2-32r^2+64rt^3-32rt+16r-16t^2+8t-1.При t=1t=1 имаме F(1)=32r2+48r−9>0F(1)=32r^2+48r-9\gt{}0. Освен това за t≥1t\ge1F′(t)=8(16r2t+24rt2−4r−4t+1)>0,F'(t)=8\bigl(16r^2t+24rt^2-4r-4t+1\bigr)\gt{}0,понеже r≥1r\ge1. Следователно F(t)>0F(t)\gt{}0 за всеки t≥1t\ge1, което завършва проверката на конструкцията. Така най-голямата възможна стойност на произведението е 3⋅7⋅11⋯40193\cdot7\cdot11\cdots4019.
Отвори задачатаEvan Chen VONVON USAMO 2010/3Условие — източник

Задача 5

Пълен запис
Условие
Нека q=3p−52q=\frac{3p-5}{2}, където pp е нечетно просто число, и нека Sq=S_q=12⋅3⋅4+15⋅6⋅7\frac1{2\cdot3\cdot4}+\frac1{5\cdot6\cdot7}+⋯+1q(q+1)(q+2).+\cdots+\frac1{q(q+1)(q+2)}. Да се докаже, че ако 1p−2Sq=mn\frac1p-2S_q=\frac mn за цели числа mm и nn, то pp дели m−nm-n.
РешениеИзползваме разлагането на прости дроби2(3k−1)(3k)(3k+1)=\frac{2}{(3k-1)(3k)(3k+1)}=13k−1−23k+13k+1.\frac1{3k-1}-\frac2{3k}+\frac1{3k+1}.Тъй като q=3p−52q=\frac{3p-5}{2}, последният член в сумата е с първи множител qq, а броят на членовете е q+13=p−12\frac{q+1}{3}=\frac{p-1}{2}. Следователно2Sq=2S_q=\left(\frac12+\frac13+\cdots+\frac1{q+2} ight)-\left(1+\frac12+\cdots+\frac1{(q+1)/3} ight).Изваждаме члена 1/p1/p от първата хармонична сума и добавяме 11 от двете страни, за да получим2Sq−1p+1=2S_q-\frac1p+1=\left(1+\frac12+\cdots+\frac1{p-1} ight)+\left(\frac1{p+1}+\frac1{p+2}+\cdots+\frac1{q+2} ight)-\left(1+\frac12+\cdots+\frac1{(q+1)/3} ight).Сега работим по модул pp; всички знаменатели в последния израз са взаимно прости с pp. Понежеq−p+2=q+13=p−12,q-p+2=\frac{q+1}{3}=\frac{p-1}{2},имаме1p+r≡1r(modp)(1≤r≤q−p+2).\frac1{p+r}\equiv\frac1r\pmod p\qquad (1\le r\le q-p+2).Затова втората и третата сума се съкращават по модул pp. Остава2Sq−1p+1≡1+12+⋯+1p−1≡0(modp),2S_q-\frac1p+1\equiv1+\frac12+\cdots+\frac1{p-1}\equiv0\pmod p,защото членовете rr и p−rp-r имат реципрочни стойности, чиято сума е 00 по модул pp. Следователно1p−2Sq≡1(modp).\frac1p-2S_q\equiv1\pmod p.Ако тази рационална стойност е m/nm/n, последното сравнение означава m≡n(modp)m\equiv n\pmod p, тоест p∣m−np\mid m-n.
Отвори задачатаEvan Chen VONVON USAMO 2010/5Условие — източник

Задача 6

Пълен запис
Условие
На дъската са записани 6868 наредени двойки, не непременно различни, от ненулеви цели числа. Известно е, че не съществува цяло число kk, за което едновременно да са записани двойките (k,k)(k,k) и (−k,−k)(-k,-k). Ученик изтрива някои от 136136-те записани числа така, че никои две изтрити числа да нямат сума 00, и получава една точка за всяка наредена двойка, в която е изтрито поне едно число. Какъв е най-големият брой точки, който ученикът може да си гарантира?
РешениеОтговорът е 4343. Ще преведем задачата на езика на мултиграфите. Групираме всяко ненулево число с противоположното му: за всяка такава двойка пишем върхове aia_i и bib_i, където bi=−aib_i=-a_i. Всяка наредена двойка от дъската разглеждаме като ребро между съответните върхове; ориентацията не влияе на това дали реброто носи точка. Условието за двойките (k,k)(k,k) и (−k,−k)(-k,-k) позволява да означим върховете така, че примките да са само при върхове от вида aia_i. Ученикът може да избере точно един от двата върха ai,bia_i,b_i за всяко ii: ако не е избрал нито един, добавянето на един от тях не нарушава условието и не намалява резултата. Точките са точно ребрата, инцидентни с избраните върхове. Първо доказваме, че винаги могат да се гарантират поне 4343 точки. Избираме независимо aia_i с вероятностp=5−12,p=\frac{\sqrt5-1}{2},а bib_i с вероятност 1−p1-p. Тогава p=1−p2p=1-p^2. Всяка примка при aia_i се брои с вероятност pp. Всяко ребро между два върха от вида bi,bjb_i,b_j се брои с вероятност 1−p2=p1-p^2=p. Всички останали ребра се броят с вероятност поне pp. Следователно математическото очакване на броя точки е поне 68p68p. А68p=34(5−1)>42,68p=34(\sqrt5-1)\gt{}42,защото 345>7634\sqrt5\gt{}76 е еквивалентно след повдигане на квадрат на 342⋅5>76234^2\cdot5\gt{}76^2. Значи съществува избор с поне 4343 точки, понеже броят точки е цяло число. Остава да покажем, че 4343 не може да бъде подобрено. Даваме пример. Нека имаме 88 двойки върхове ai,bia_i,b_i. Поставяме по пет примки при всеки aia_i, общо 4040 ребра, и поставяме по едно ребро между всяка двойка различни върхове bi,bjb_i,b_j, тоест граф K8K_8 върху върховете bib_i, с още (82)=28\binom{8}{2}=28 ребра. Общо ребрата са 6868, а примки при bib_i няма, така че условието на задачата е изпълнено. Ако ученикът избере точно mm от върховете aia_i и съответно 8−m8-m от върховете bib_i, резултатът му е5m+(82)−(m2).5m+\binom{8}{2}-\binom{m}{2}.Това е 28+5m−m(m−1)/228+5m-m(m-1)/2, чиято максимална стойност за 0≤m≤80\le m\le8 е 4343 (при m=5m=5 или m=6m=6). Следователно в този пример не могат да се гарантират повече от 4343 точки. Значи търсеният максимум е 4343.
Отвори задачатаEvan Chen VONVON USAMO 2010/6Условие — източник