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

Evan Chen / USAMO Solution Notes

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

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

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

2005

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Да се определят всички съставни положителни цели числа nn, за които е възможно всички делители на nn, по-големи от 11, да се подредят в кръг така, че никои два съседни делителя да не са взаимно прости.
РешениеОтговорът е: всички съставни положителни цели числа, освен числата от вида pqpq, където pp и qq са различни прости числа. Ако n=pqn=pq с различни прости pp и qq, делителите, по-големи от 11, са само p,q,pqp,q,pq. В кръг делителите pp и qq неизбежно са съседни, а те са взаимно прости, така че такова подреждане е невъзможно. Ако nn е степен на просто число, всяко подреждане работи. Ако nn има поне три различни прости делителя p1,p2,...,pkp_1,p_2,...,p_k, първо поставяме около кръга p1p2,p2p3,...,pkp1p_1p_2,p_2p_3,...,p_kp_1, а после поставяме всеки делител, кратен на pip_i, в дъгата между pi−1pip_{i-1}p_i и pipi+1p_ip_{i+1}. Така всяка съседна двойка има общ прост делител. Остава случаят n=paqbn=p^a q^b. Ако поне един от показателите е по-голям от 11, например a>1a\gt{}1, поставяме първо pqpq и p2qp^2q на кръга. В едната дъга поставяме останалите делители, кратни на pp, а в другата - останалите делители, кратни на qq. Единственият неизключен случай е a=b=1a=b=1, който вече е невъзможен.
Отвори задачатаEvan Chen VONVON USAMO 2005/1Условие — източник

Задача 2

Пълен запис
Условие
Да се докаже, че системата от уравнения x6+x3+x3y+y=147157,x^6+x^3+x^3y+y=147157, x3+x3y+y2+y+z9=157147x^3+x^3y+y^2+y+z^9=157147 няма целочислени решения.
РешениеЩе докажем невъзможността по модул 1313. Нека u=x3u=x^3. Тогава uu може да бъде само 0,1,5,80,1,5,8 или 1212 по модул 1313. Първото уравнение става u2+u+y(u+1)≡10(mod13).u^2+u+y(u+1)\equiv 10\pmod{13}. Проверка на петте възможности за uu дава само следните случаи: (u,y)≡(0,10),(1,4),(5,1),(8,9)(mod13),(u,y)\equiv (0,10),(1,4),(5,1),(8,9)\pmod{13}, а при u≡12u\equiv 12 първото уравнение е невъзможно. От второто уравнение трябва да имаме (y+1)(u+y)+z9≡3(mod13).(y+1)(u+y)+z^9\equiv 3\pmod{13}. Деветите степени по модул 1313 са само 0,1,5,8,120,1,5,8,12. За четирите останали двойки (u,y)(u,y) стойността на (y+1)(u+y)(y+1)(u+y) е съответно 6,12,12,16,12,12,1, така че z9z^9 би трябвало да е съответно 10,4,4,210,4,4,2 по модул 1313. Никое от тези числа не е девета степен по модул 1313, противоречие.
Отвори задачатаEvan Chen VONVON USAMO 2005/2Условие — източник

Задача 3

Пълен запис
Условие
Нека ABCABC е остроъгълен триъгълник, а PP и QQ са две точки върху страната BCBC. Построена е точка C1C_1 така, че изпъкналият четириъгълник APBC1APBC_1 е вписан, QC1∥CAQC_1\parallel CA, а C1C_1 и QQ са от различни страни на правата ABAB. Построена е точка B1B_1 така, че изпъкналият четириъгълник APCB1APCB_1 е вписан, QB1∥BAQB_1\parallel BA, а B1B_1 и QQ са от различни страни на правата ACAC. Да се докаже, че точките B1,C1,P,QB_1,C_1,P,Q лежат на една окръжност.
РешениеДостатъчно е да докажем, че A,B1,C1A,B_1,C_1 са колинеарни. Тогава от успоредностите и вписаните четириъгълници следва ∠C1QP=∠ACP=∠AB1P=∠C1B1P,\angle C_1QP=\angle ACP=\angle AB_1P=\angle C_1B_1P, което дава, че B1,C1,P,QB_1,C_1,P,Q лежат на една окръжност. Нека TT е втората пресечна точка на правата AC1AC_1 с окръжността (APC)(APC). От вписаността на APBC1APBC_1 получаваме △PC1T∼△ABC\triangle PC_1T\sim\triangle ABC. Понеже QC1∥ACQC_1\parallel AC, това дава, че T,C1,Q,PT,C_1,Q,P са вписани. Оттук следва TQ∥ABTQ\parallel AB, а по единствеността в построението T=B1T=B_1. Значи A,B1,C1A,B_1,C_1 са колинеарни.
Отвори задачатаEvan Chen VONVON USAMO 2005/3Условие — източник

Задача 4

Пълен запис
Условие
Краката L1,L2,L3,L4L_1,L_2,L_3,L_4 на квадратна маса имат дължина nn, където nn е положително цяло число. За колко наредени четворки (k1,k2,k3,k4)(k_1,k_2,k_3,k_4) от неотрицателни цели числа можем да отрежем парче с дължина kik_i от края на крака LiL_i и масата все още да бъде стабилна? Масата е стабилна, ако може да бъде поставена така, че краищата на всичките четири крака да докосват пода. Позволено е отрязан крак да има дължина 00.
РешениеОтговорът е (n+1)(2n2+4n+3)3.\frac{(n+1)(2n^2+4n+3)}3.Да обърнем масата с плота към пода. Тогава искаме краищата A,B,C,DA,B,C,D на скъсените крака да са копланарни. Това става точно когато ABCDABCD е успоредник. Наистина, ако ABCDABCD е успоредник, четирите точки очевидно лежат в една равнина. Обратно, ако са копланарни, нека D′D' е точката, за която ABCD′ABCD' е успоредник. Тогава D′D' лежи в същата равнина, но е разположена точно над DD, защото горната част на масата е квадрат. Следователно D′=DD'=D. Остава само да преброим решенията на условието(n−k1)+(n−k3)=(n−k2)+(n−k4),(n-k_1)+(n-k_3)=(n-k_2)+(n-k_4),тоест k1+k3=k2+k4.k_1+k_3=k_2+k_4.Некаar=#{(a,b)∣a+b=r, 0≤a,b≤n}.a_r=\#\{(a,b)\mid a+b=r,\ 0\le a,b\le n\}.Броят на решенията с k1+k3=k2+k4=rk_1+k_3=k_2+k_4=r е ar2a_r^2, затова общият брой е∑r=02nar2=\sum_{r=0}^{2n}a_r^2=12+22+⋯+n2+(n+1)2+n2+⋯+12=1^2+2^2+\cdots+n^2+(n+1)^2+n^2+\cdots+1^2=(n+1)(2n2+4n+3)3.\frac{(n+1)(2n^2+4n+3)}3.
Отвори задачатаEvan Chen VONVON USAMO 2005/4Условие — източник

Задача 5

Пълен запис
Условие
Нека n>1n\gt{}1 е цяло число. Дадени са 2n2n точки в равнината, никои три от които не са колинеарни. Нека nn от точките са оцветени в синьо, а останалите nn - в червено. Една права се нарича балансираща, ако минава през една синя и една червена точка и от всяка страна на правата броят на сините точки от тази страна е равен на броя на червените точки от същата страна. Да се докаже, че съществуват поне две балансиращи прави.
РешениеНека HH е изпъкналата обвивка на дадените точки. Разглеждаме два случая. Първо, ако върховете на HH не са всички от един и същи цвят, по границата на HH има поне две страни с разноцветни краища. Продълженията на тези страни са балансиращи прави: от едната страна на такава права няма точки, а от другата остават точно n−1n-1 сини и n−1n-1 червени точки. Остава случаят, когато всички върхове на HH са от един цвят; без ограничение нека са сини. Ще докажем, че през всеки връх на HH минава балансираща права. Нека A,B,CA,B,C са три последователни сини върха на HH. Завъртаме права ℓ\ell през BB, започвайки от правата BABA и стигайки до правата BCBC, като я въртим през вътрешността на фигурата. Във всеки момент гледаме точките от същата страна на ℓ\ell като CC и означаваме с xx броя на червените минус броя на сините точки от тази страна. Когато ℓ\ell срещне синя точка, xx се увеличава с 11, а когато срещне червена точка, xx намалява с 11. В началото x=1x=1, а непосредствено преди края x=−1x=-1. Следователно в първия момент, в който x=0x=0, правата минава през BB и през червена точка, и е балансираща. Така получаваме балансираща права през всеки връх на HH. Тези прави са различни, понеже никои три от дадените точки не са колинеарни. Следователно има поне две балансиращи прави.
Отвори задачатаEvan Chen VONVON USAMO 2005/5Условие — източник

Задача 6

Пълен запис
Условие
За положително цяло число mm нека s(m)s(m) означава сумата на десетичните цифри на mm. Множество SS от положителни цели числа наричаме kk-стабилно, ако s(∑x∈Xx)=ks\left(\sum_{x\in X}x\right)=k за всяко непразно подмножество X⊆SX\subseteq S. За всяко цяло число n≥2n\ge 2 нека f(n)f(n) е най-малкото kk, за което съществува kk-стабилно множество с nn цели числа. Да се докаже, че съществуват константи 0<C1<C20\lt{}C_1\lt{}C_2, такива че C1log⁡10n≤f(n)≤C2log⁡10n.C_1\log_{10} n\le f(n)\le C_2\log_{10} n.
РешениеПърво ще построим достатъчно голямо стабилно множество. Нека ee е положително цяло число, за което1+2+⋯+n≤10e,1+2+\cdots+n\le 10^e,и разгледамеS={10e−1, 2(10e−1), …, n(10e−1)}.S=\{10^e-1,\ 2(10^e-1),\ \ldots,\ n(10^e-1)\}.Ако XX е непразно подмножество на SS, сумата на елементите на XX има вида t(10e−1)t(10^e-1), където 1≤t≤1+2+⋯+n≤10e1\le t\le 1+2+\cdots+n\le 10^e. За всяко такова tt числото t(10e−1)=t⋅10e−tt(10^e-1)=t\cdot 10^e-t има сума на цифрите 9e9e: при t<10et\lt{}10^e то се записва като (t−1)(t-1), последвано от последните ee цифри на 10e−t10^e-t, а при t=10et=10^e получаваме 102e−10e10^{2e}-10^e. И в двата случая сумата на цифрите е 9e9e. Следователно SS е 9e9e-стабилно. Избирайки e=⌈log⁡10(n+12)⌉e=\left\lceil\log_{10}\binom{n+1}{2}\right\rceil, получаваме горната оценка f(n)≤9ef(n)\le 9e, а значи f(n)≤C2log⁡10nf(n)\le C_2\log_{10}n за подходяща абсолютна константа C2C_2. Остава долната оценка. Ще докажем следното твърдение: ако в мултимножество има повече от 12k12^k положителни цели числа, то съществува непразно подмножество, за което сумата на цифрите на сбора на елементите е по-голяма от kk. Това веднага дава n≤12kn\le 12^k за всяко kk-стабилно множество с nn елемента, тоест k≥log⁡12n=log⁡10nlog⁡1012k\ge \log_{12}n=\frac{\log_{10}n}{\log_{10}12}. Да докажем твърдението. Записваме числата на дъска и поддържаме текуща сума Σ\Sigma, първоначално равна на 00. Ще запазваме инварианта, че всяко число на дъската, както и Σ\Sigma, е сума на някои от първоначалните числа, като използваните групи са разединени. На ii-тата стъпка искаме в края всички числа на дъската да се делят на 10i10^i. Ако ii-тата цифра отдясно на Σ\Sigma е ненулева, разделяме произволно числата на дъската на групи по 1010 и изтриваме остатъка, ако има такъв. Във всяка група има непразно подмножество със сума, деляща се на 10i10^i: след деление на 10i−110^{i-1} това е стандартният факт, че сред 1010 цели числа има непразно подмножество със сума, деляща се на 1010. Заменяме всяка група с тази сума. Ако ii-тата цифра отдясно на Σ\Sigma е нула, но на дъската има число, което не се дели на 10i10^i, изтриваме едно такова число и го прибавяме към Σ\Sigma. После правим същото групиране по 1010. Ако пък ii-тата цифра отдясно на Σ\Sigma е нула и всички числа на дъската вече се делят на 10i10^i, не правим нищо и преминаваме нататък. Процесът свършва, когато на дъската не останат числа. При всяка нетривиална стъпка броят на числата на дъската намалява с фактор най-много 1212, затова, щом началният брой е по-голям от 12k12^k, първите два случая се случват поне k+1k+1 пъти. Всеки път при тях в Σ\Sigma се появява нова ненулева десетична цифра, която по-нататък не се променя, защото следващите прибавяни числа са делими на все по-високи степени на 1010. Следователно накрая s(Σ)≥k+1s(\Sigma)\ge k+1. По инварианта Σ\Sigma е сума на непразно подмножество от първоначалните числа, което доказва твърдението и долната оценка.
Отвори задачатаEvan Chen VONVON USAMO 2005/6Условие — източник