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

Evan Chen / EGMO Twitch Solution

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

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

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

2017

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

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

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

11-12

4 задачи

Задача 2

Пълен запис
Условие
Да се намери най-малкото положително цяло число kk, за което съществуват оцветяване на положителните цели числа Z>0\mathbb Z_{\gt{}0} в kk цвята и функция f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0} със следните две свойства: 1. За всички едноцветни положителни цели числа m,nm,n е изпълнено f(m+n)=f(m)+f(n)f(m+n)=f(m)+f(n). 2. Съществуват положителни цели числа m,nm,n, за които f(m+n)≠f(m)+f(n)f(m+n)\ne f(m)+f(n).
РешениеОтговорът е k=3k=3. Конструкцията за k=3k=3 е следната. Оцветяваме числата според остатъка им по модул 33 и дефинирамеf(n)={n/3,n≡0(mod3),n,иначе.f(n)=\begin{cases} n/3, & n\equiv0\pmod3,\\ n, & \text{иначе}. \end{cases}Ако mm и nn са едноцветни, то лесно се проверява, че f(m+n)=f(m)+f(n)f(m+n)=f(m)+f(n). От друга страна, f(1+2)=f(3)=1f(1+2)=f(3)=1, докато f(1)+f(2)=3f(1)+f(2)=3, така че второто свойство също е изпълнено. Остава да докажем, че два цвята не стигат. Всъщност ще докажем малко по-силно твърдение: при два цвята всяка функция f:Z>0→R>0f:\mathbb Z_{\gt{}0}\to\mathbb R_{\gt{}0}, която удовлетворява първото свойство, е линейна. След умножаване с положителна константа можем да считаме, че f(1)=1f(1)=1. Цветовете ще наричаме червен и син. Първо, за всяко nn имамеf(2n)=f(n+n)=2f(n),f(2n)=f(n+n)=2f(n),защото nn е едноцветно със себе си. Ще докажем по индукция, че f(r)=rf(r)=r за всяко положително цяло rr. Нека вече знаем това за 1,2,…,2n1,2,\dots,2n, и поставяме m=2n+1m=2n+1. Без ограничение нека mm е червено. Да допуснем, че f(m)≠mf(m)\ne m. Числото m−2m-2 не може да е червено, защото тогаваf(2m−2)=f(m)+f(m−2),f(2m-2)=f(m)+f(m-2),а лявата страна е 2f(m−1)=2m−22f(m-1)=2m-2, докато f(m−2)=m−2f(m-2)=m-2, откъдето би следвало f(m)=mf(m)=m. Значи m−2m-2 е синьо. Тогава числото 22 трябва да е червено; ако беше синьо, щяхме да имамеf(m)=f(2+(m−2))=f(2)+f(m−2)=m,f(m)=f(2+(m-2))=f(2)+f(m-2)=m,противоречие. Понеже mm и 22 са червени, получавамеf(m+2)=f(m)+2.f(m+2)=f(m)+2.Ако m+2m+2 е червено, тоf(2m+2)=f(m+2)+f(m)=2f(m)+2.f(2m+2)=f(m+2)+f(m)=2f(m)+2.Но f(2m+2)=2f(m+1)=2m+2f(2m+2)=2f(m+1)=2m+2, следователно f(m)=mf(m)=m, противоречие. Ако пък m+2m+2 е синьо, то2f(m)=f(2m)=f((m+2)+(m−2))=2f(m)=f(2m)=f((m+2)+(m-2))=f(m+2)+f(m−2)=f(m)+m,f(m+2)+f(m-2)=f(m)+m,откъдето пак f(m)=mf(m)=m. И в двата случая получаваме противоречие, така че наистина f(m)=mf(m)=m. Индукцията доказва f(r)=rf(r)=r за всички rr. Следователно при два цвята първото свойство принуждава функцията да бъде адитивна за всички двойки, което прави второто свойство невъзможно. При един цвят това е още по-ясно. Затова минималното kk е 33.
Отвори задачатаEvan Chen VONVON EGMO 2017/2Условие — източник

Задача 3

Пълен запис
Условие
В равнината са дадени 20172017 прави, като никои три от тях не минават през една точка. Охлювът Турбо стои в точка, която лежи върху точно една от правите, и започва да се плъзга по правите по следния начин. Тя се движи по дадена права, докато стигне до пресечна точка на две прави. В пресечната точка продължава по другата права, като завива наляво или надясно, и редува избора си при всяка пресечна точка, която достигне. Тя може да сменя посоката си само в пресечни точки. Възможно ли е да съществува отсечка от права, през която Турбо минава и в двете посоки по време на своето движение?
РешениеОтговорът е не. Оцветяваме областите, на които правите разделят равнината, шахматно в черно и бяло: две области с обща страна имат различни цветове. Това е възможно, защото при преминаване през права цветът просто се сменя. Да проследим движението на Турбо. Когато тя стигне до пресечна точка и мине на другата права, завиването наляво или надясно определя около коя от съседните области се движи в този момент. Понеже при следващата пресечна точка изборът се сменя, а цветът на областта от съответната страна също се сменя, получаваме следния инвариант: Турбо винаги обхожда границите на черните области с една и съща ориентация, а границите на белите области с противоположната ориентация. Ако някоя отсечка бъде премината в двете посоки, то двете области от двете страни на тази отсечка биха били обхождани веднъж в едната и веднъж в обратната ориентация. Това противоречи на описания инвариант. Следователно такава отсечка не може да съществува.
Отвори задачатаEvan Chen VONVON EGMO 2017/3Условие — източник

Задача 4

Пълен запис
Условие
Нека n≥1n\ge1 е цяло число и нека t1<t2<⋯<tnt_1\lt{}t_2\lt{}\dots\lt{}t_n са положителни цели числа. В група от tn+1t_n+1 души се играят няколко партии шах. Всеки двама души могат да играят помежду си най-много веднъж. Докажете, че е възможно едновременно да са изпълнени следните две условия: 1. Броят партии, изиграни от всеки човек, е едно от числата t1,t2,…,tnt_1,t_2,\dots,t_n. 2. За всяко ii с 1≤i≤n1\le i\le n има човек, който е изиграл точно tit_i партии шах.
РешениеЩе преведем задачата на езика на графите. Търсим прост граф GG с tn+1t_n+1 върха, така че всички степени да принадлежат на множеството {t1,t2,…,tn}\{t_1,t_2,\dots,t_n\} и всяка от тези степени да се среща поне веднъж. Доказваме съществуването с индукция по nn. При n=1n=1 вземаме пълен граф върху t1+1t_1+1 върха; тогава всяка степен е t1t_1. При n=2n=2 вземаме пълен граф върху t1t_1 върха и празен граф върху t2+1−t1t_2+1-t_1 върха, след което свързваме всеки връх от първата част с всеки връх от втората част. Върховете от първата част имат степен t2t_2, а върховете от втората имат степен t1t_1, така че и двете степени се срещат. Нека сега n≥3n\ge3. По индукционното предположение съществува пример за (n−2)(n-2)-торката(t2−t1, t3−t1, …, tn−1−t1),(t_2-t_1,\ t_3-t_1,\ \dots,\ t_{n-1}-t_1),който има tn−1−t1+1t_{n-1}-t_1+1 върха. Към него добавяме tn−tn−1t_n-t_{n-1} изолирани върха. Накрая добавяме още t1t_1 универсални върха, тоест върхове, свързани с всички останали върхове и помежду си. Сега старите върхове от индукционния пример увеличават степените си с t1t_1 и така дават степените t2,t3,…,tn−1t_2,t_3,\dots,t_{n-1}. Новите изолирани върхове стават със степен t1t_1, защото са свързани само с универсалните върхове. Самите универсални върхове имат степен tnt_n, понеже общият брой върхове е tn+1t_n+1. Следователно всички степени t1,t2,…,tnt_1,t_2,\dots,t_n се срещат и други степени няма. Това завършва индукцията и доказателството.
Отвори задачатаEvan Chen VONVON EGMO 2017/4Условие — източник

Задача 6

Пълен запис
Условие
Нека ABCABC е остроъгълен разностранен триъгълник. Отраженията на медицентъра GG и на центъра OO на описаната окръжност на ABCABC спрямо страните BCBC, CACA и ABAB се означават съответно с G1G_1, G2G_2, G3G_3 и O1O_1, O2O_2, O3O_3. Докажете, че описаните окръжности на триъгълниците G1G2CG_1G_2C, G1G3BG_1G_3B, G2G3AG_2G_3A, O1O2CO_1O_2C, O1O3BO_1O_3B, O2O3AO_2O_3A и ABCABC имат обща точка.
РешениеЩе използваме комплексни числа върху единичната описана окръжност на ABCABC. Нека PP е произволна точка. Нека PBP_B и PCP_C са отраженията на PP съответно спрямо правите ABAB и ACAC, а QBQ_B и QCQ_C са вторите пресечни точки на правите APBAP_B и APCAP_C с описаната окръжност. Ще намерим втората пресечна точка на окръжностите (APBPC)(AP_BP_C) и (AQBQC)=(ABC)(AQ_BQ_C)=(ABC). От формулата за отражение спрямо хорда на единичната окръжност имамеpB=a+c−acp‾,pC=a+b−abp‾.p_B=a+c-ac\overline p,\qquad p_C=a+b-ab\overline p.За да намерим qBq_B, използваме колинеарността на AA, PBP_B и QBQ_B:a+qB=pB+aqBpB‾=a+c−acp‾+aqB(1a+1c−pac),\begin{aligned} a+q_B&=p_B+aq_B\overline{p_B}\\ &=a+c-ac\overline p+aq_B\left(\frac1a+\frac1c-\frac{p}{ac}\right), \end{aligned}откъдетоqB=c2ap‾−1a−p.q_B=c^2\frac{a\overline p-1}{a-p}.АналогичноqC=b2ap‾−1a−p.q_C=b^2\frac{a\overline p-1}{a-p}.Следователно търсената пресечна точка еpBqC−pCqBpB−pC+qC−qB=(ap‾−1a−p)(b2(a+c−acp‾)−c2(a+b−abp‾))(b−c)(ap‾−1)+(b2−c2)⋅ap‾−1a−p=b2(a+c−acp‾)−c2(a+b−abp‾)(b−c)(a−p)+(b2−c2)=(b−c)(a(b+c)+bc)−(b−c)abcp‾(a−p)+(b+c)=ab+bc+ca−abcp‾a+b+c−p.\begin{aligned} \frac{p_Bq_C-p_Cq_B}{p_B-p_C+q_C-q_B} &=\frac{\left(\frac{a\overline p-1}{a-p}\right)\left(b^2(a+c-ac\overline p)-c^2(a+b-ab\overline p)\right)}{(b-c)(a\overline p-1)+(b^2-c^2)\cdot\frac{a\overline p-1}{a-p}}\\ &=\frac{b^2(a+c-ac\overline p)-c^2(a+b-ab\overline p)}{(b-c)(a-p)+(b^2-c^2)}\\ &=\frac{(b-c)(a(b+c)+bc)-(b-c)abc\overline p}{(a-p)+(b+c)}\\ &=\frac{ab+bc+ca-abc\overline p}{a+b+c-p}. \end{aligned}Този израз е симетричен по aa, bb и cc. Сега вземаме P=GP=G, т.е. p=13(a+b+c)p=\frac13(a+b+c), и P=OP=O, т.е. p=0p=0. В двата случая получаваме една и съща точка от описаната окръжност на ABCABC; същата формула е симетрична, затова при циклична смяна на ролите на върховете тя лежи върху всички шест окръжности, построени от отраженията на GG и OO. Следователно тези шест окръжности и описаната окръжност на ABCABC имат обща точка.
Отвори задачатаEvan Chen VONVON EGMO 2017/6Условие — източник