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

Evan Chen / EGMO Twitch Solution

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

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

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

2015

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

11-12

4 задачи

Задача 3

Пълен запис
Условие
Нека nn и mm са цели числа, по-големи от 11, и нека a1,a2,…,ama_1,a_2,\dots,a_m са положителни цели числа, не по-големи от nmn^m. Докажете, че съществуват цели числа b1,b2,…,bmb_1,b_2,\dots,b_m, не по-големи от nn, такива чеgcd⁡(a1+b1,a2+b2,…,am+bm)<n.\gcd(a_1+b_1,a_2+b_2,\dots,a_m+b_m)\lt{}n.
РешениеВсъщност ще докажем нещо по-силно: можем да изберем всички bib_i от множеството {0,1}\{0,1\}. Да допуснем противното, т.е. че за всеки избор на bi∈{0,1}b_i\in\{0,1\} полученият най-голям общ делител е поне nn. Разглеждаме следните mm избора. Първо вземамеb1=b2=⋯=bm=0b_1=b_2=\dots=b_m=0и нека съответният НОД е g1g_1. След това за всяко k=2,3,…,mk=2,3,\dots,m вземаме bk=1b_k=1, а всички останали bib_i равни на 00, и нека съответният НОД е gkg_k. По предположението всички числа g1,g2,…,gmg_1,g_2,\dots,g_m са поне nn. Освен това всяко gkg_k дели a1a_1, понеже във всички тези mm избора имаме b1=0b_1=0. Ще покажем, че числата g1,g2,…,gmg_1,g_2,\dots,g_m са две по две взаимнопрости. Ако 1≤i<j≤m1\le i\lt{}j\le m, тогава gig_i дели aja_j (при i=1i=1 това е очевидно, а при i≥2i\ge2 в избора за gig_i единствено aia_i е увеличено с 11). От друга страна, gjg_j дели aj+1a_j+1. Следователно всеки общ делител на gig_i и gjg_j дели и aja_j, и aj+1a_j+1, значи е равен на 11. Така произведениетоG=g1g2…gmG=g_1g_2\dots g_mдели a1a_1. Но понеже факторите са две по две взаимнопрости и всеки от тях е поне n>1n\gt{}1, имаме всъщност G>nmG\gt{}n^m: равенство G=nmG=n^m би изисквало всички gig_i да са равни на nn, което е невъзможно за две по две взаимнопрости числа при n>1n\gt{}1. Получавамеa1≥G>nm,a_1\ge G\gt{}n^m,което противоречи на условието a1≤nma_1\le n^m. Следователно предположението е невярно и съществува избор на bi∈{0,1}b_i\in\{0,1\}, за който НОД е по-малък от nn.
Отвори задачатаEvan Chen VONVON EGMO 2015/3Условие — източник

Задача 4

Пълен запис
Условие
Определете дали съществува безкрайна редица a1,a2,…a_1,a_2,\dots от положителни цели числа, такава че an+2=an+1+x2an+1+ana_{n+2}=a_{n+1}+\sqrt{\vphantom{x^2}a_{n+1}+a_n} за всяко положително цяло число nn.
РешениеТакава безкрайна редица не съществува. Всъщност може да има най-много пет члена; например (477,7,29,35,43)(477,7,29,35,43) показва, че пет члена са възможни. Да положимxn=an+1−an=x2an+an−1(n≥2).x_n=a_{n+1}-a_n=\sqrt{\vphantom{x^2}a_n+a_{n-1}}\qquad(n\ge2).Понеже всички aia_i са цели числа и рекурсията трябва да дава цели числа, всички xnx_n са положителни цели числа. От n≥2n\ge2 нататък редицата (an)(a_n) е строго растяща, следователно за n≥3n\ge3 и редицата (xn)(x_n) е строго растяща. За n≥2n\ge2 пресмятамеxn+12−xn2=(an+1+an)−(an+an−1)=x_{n+1}^2-x_n^2=(a_{n+1}+a_n)-(a_n+a_{n-1})=an+1−an−1=xn+xn−1.a_{n+1}-a_{n-1}=x_n+x_{n-1}.Следователноxn+1−xn=xn+xn−1xn+1+xn.x_{n+1}-x_n=\frac{x_n+x_{n-1}}{x_{n+1}+x_n}.Ако съществуват поне шест члена a1,…,a6a_1,\dots,a_6, можем да вземем n=4n=4. Тогава xn−1<xn<xn+1x_{n-1}\lt{}x_n\lt{}x_{n+1}, така че дясната страна е строго по-малка от 11. Но лявата страна е положително цяло число, следователно е поне 11. Това е противоречие. Значи не може да има шест последователни члена, удовлетворяващи рекурсията, а още по-малко безкрайна редица.
Отвори задачатаEvan Chen VONVON EGMO 2015/4Условие — източник

Задача 5

Пълен запис
Условие
Нека mm и nn са положителни цели числа, като m>1m\gt{}1. Анастасия разбива целите числа 1,2,…,2m1,2,\dots,2m на mm двойки. След това Борис избира по едно число от всяка двойка и намира сумата на избраните числа. Докажете, че Анастасия може да избере двойките така, че Борис да не може да получи сума, равна на nn.
РешениеЩе използваме няколко явни разбивания, които изключват всички възможни стойности на nn. Първо разглеждаме разбиването13…2m−32m−124…2m−22m\begin{array}{ccccc} 1&3&\dots&2m-3&2m-1\cr 2&4&\dots&2m-2&2m \end{array}на двойките (1,2),(3,4),…,(2m−1,2m)(1,2),(3,4),\dots,(2m-1,2m). Ако Борис избере долното число в точно kk от двойките, сумата му е m2+km^2+k. Следователно възможните суми са точно числата от интервала [m2,m2+m][m^2,m^2+m]. Ако nn не е в този интервал, това разбиване вече работи. Второ разглеждаме разбиването12…m−1mm+1m+2…2m−12m.\begin{array}{ccccc} 1&2&\dots&m-1&m\cr m+1&m+2&\dots&2m-1&2m \end{array}.Всяка смяна от горното към долното число добавя mm, затова всички възможни суми са сравними сS0=1+2+⋯+m=m(m+1)2(modm).S_0=1+2+\dots+m=\frac{m(m+1)}2\pmod{m}.Ако n≢S0(modm)n\not\equiv S_0\pmod{m}, това разбиване работи. Остава да разгледаме случаите, в които едновременно m2≤n≤m2+mm^2\le n\le m^2+m и n≡S0(modm)n\equiv S_0\pmod{m}. Ако mm е нечетно, тогава S0≡0(modm)S_0\equiv0\pmod{m} и значи nn е едно от m2m^2 и m2+mm^2+m. Ако mm е четно, тогава S0≡m2(modm)S_0\equiv\frac{m}{2}\pmod{m} и значи единствената останала стойност еn=m2+m2.n=m^2+\frac{m}{2}.За тези останали случаи използваме третото разбиване12…m−1mm+2m+3…2mm+1,\begin{array}{ccccc} 1&2&\dots&m-1&m\cr m+2&m+3&\dots&2m&m+1 \end{array},тоест двойките (1,m+2),(2,m+3),…,(m−1,2m),(m,m+1)(1,m+2),(2,m+3),\dots,(m-1,2m),(m,m+1). Сумата на горния ред отново е S0S_0. В първите m−1m-1 двойки изборът на долното число променя сумата с кратно на m+1m+1, а в последната двойка я променя с 11. Следователно по модул m+1m+1 всички възможни суми са самоS0илиS0+1.S_0\quad\text{или}\quad S_0+1.Ако mm е нечетно, имамеS0=m(m+1)2≡m+12(modm+1),S_0=\frac{m(m+1)}2\equiv\frac{m+1}{2}\pmod{m+1},така че възможните остатъци са m+12\frac{m+1}{2} и m+32\frac{m+3}{2}. Понеже m>1m\gt{}1 е нечетно, тези остатъци не са 00 и 11. Но двете останали цели m2m^2 и m2+mm^2+m дават остатъци съответно 11 и 00 по модул m+1m+1. Значи третото разбиване ги избягва. Ако mm е четно, числото S0=m2(m+1)S_0=\frac{m}{2}(m+1) се дели на m+1m+1, така че възможните остатъци са 00 и 11. От друга странаm2+m2≡1+m2(modm+1),m^2+\frac{m}{2}\equiv1+\frac{m}{2}\pmod{m+1},а този остатък е различен и от 00, и от 11, понеже m≥2m\ge2. Значи и в четния случай третото разбиване избягва останалата стойност на nn. Във всички случаи Анастасия има разбиване, при което Борис не може да получи сума nn.
Отвори задачатаEvan Chen VONVON EGMO 2015/5Условие — източник

Задача 6

Пълен запис
Условие
Нека HH е ортоцентърът, а GG - медицентърът на остроъгълен триъгълник ABCABC с AB≠ACAB\ne AC. Правата AGAG пресича описаната окръжност на ABCABC в точките AA и PP. Нека P′P' е отражението на PP спрямо правата BCBC. Докажете, че ∠CAB=60∘\angle CAB=60^\circ тогава и само тогава, когато HG=GP′HG=GP'.
РешениеЩе използваме комплексни числа. Нека описаната окръжност е единичната, а комплексните координати на A,B,C,P,P′,H,GA,B,C,P,P',H,G са съответно a,b,c,p,p′,h,ga,b,c,p,p',h,g. Тогава ∣a∣=∣b∣=∣c∣=∣p∣=1|a|=|b|=|c|=|p|=1, h=a+b+ch=a+b+c и g=13(a+b+c)g=\frac13(a+b+c). От колинеарността на A,G,PA,G,P получаваме стандартното уравнениеpa(b+c)−bc(p+a)pa−bc=b+c2,\frac{pa(b+c)-bc(p+a)}{pa-bc}=\frac{b+c}{2},откъдетоp=−2bc−ab−acbc(2a−b−c).p=-\frac{2bc-ab-ac}{bc(2a-b-c)}.Отражението спрямо правата BCBC се записва катоp′=b+c−bcp‾,p'=b+c-bc\overline p,и след заместване на намереното pp получавамеp′=ab+ac−b2−c22a−b−c.p'=\frac{ab+ac-b^2-c^2}{2a-b-c}.Нека DD е средата на HP′HP' и нека комплексната му координата е dd. Тогаваd=h+p′2=a2−b2−c2+ab+ac−bc2a−b−c,h−p′=2(a2−bc)2a−b−c,g−d=2b2+2c2−a2+bc−2ab−2ac3(2a−b−c).\begin{aligned} d=\frac{h+p'}2&=\frac{a^2-b^2-c^2+ab+ac-bc}{2a-b-c},\\ h-p'&=\frac{2(a^2-bc)}{2a-b-c},\\ g-d&=\frac{2b^2+2c^2-a^2+bc-2ab-2ac}{3(2a-b-c)}. \end{aligned}Условието HG=GP′HG=GP' означава, че GG лежи на симетралата на HP′HP', тоест GD⊥HP′GD\perp HP'. В комплексна форма това е равносилно на това числотоX=g−dh−p′=X=\frac{g-d}{h-p'}=2b2+2c2−a2+bc−2ab−2ac6(a2−bc) \frac{2b^2+2c^2-a^2+bc-2ab-2ac}{6(a^2-bc)}да е чисто имагинерно. Използвайки a‾=1/a\overline a=1/a, b‾=1/b\overline b=1/b и c‾=1/c\overline c=1/c, условието X+X‾=0X+\overline X=0 след умножаване с ненулевите знаменатели се свежда доb3c+bc3+b2c2=a2bc+a2c2+a2b2,b^3c+bc^3+b^2c^2=a^2bc+a^2c^2+a^2b^2,или(b2+bc+c2)(a2−bc)=0.(b^2+bc+c^2)(a^2-bc)=0.Понеже AB≠ACAB\ne AC, не може да имаме a2=bca^2=bc; иначе AA би била средата на дъгата BCBC и би следвало AB=ACAB=AC. Оставаb2+bc+c2=0.b^2+bc+c^2=0.След деление на c2c^2 получаваме, че b/cb/c е примитивен трети корен от единицата. Това е еквивалентно на централен ъгъл 120∘120^\circ над дъгата BCBC, тоест на ∠CAB=60∘\angle CAB=60^\circ. Доказахме и двете посоки.
Отвори задачатаEvan Chen VONVON EGMO 2015/6Условие — източник