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

Evan Chen / EGMO Twitch Solution

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

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

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

2012

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

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

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

11-12

4 задачи

Задача 2

Пълен запис
Условие
Нека nn е положително цяло число. Да се намери най-голямото възможно цяло число mm в зависимост от nn със следното свойство: таблица с mm реда и nn стълба може да се попълни с реални числа така, че за всеки два различни реда[a1,a2,…,an]и[b1,b2,…,bn][a_1,a_2,\ldots,a_n]\quad\text{и}\quad[b_1,b_2,\ldots,b_n]да е изпълненоmax⁡{∣a1−b1∣,∣a2−b2∣,…,∣an−bn∣}=1.\max\{|a_1-b_1|,|a_2-b_2|,\ldots,|a_n-b_n|\}=1.
РешениеОтговорът еm=2n.m=2^n.Конструкцията е непосредствена: вземаме всички 2n2^n реда, чиито координати са само 00 или 11. За два различни такива реда всички координатни разлики са 00 или 11, а поне една от тях е 11, следователно максимумът е точно 11. Остава да докажем, че повече редове не са възможни. Нека M(n)M(n) е най-големият възможен брой редове. Ще докажем с индукция, че M(n)≤2nM(n)\le2^n. При n=1n=1 твърдението е ясно. За индукционната стъпка разглеждаме първия стълб. Нека rr е най-малката стойност в него. Понеже разстоянието по максимум между всеки два реда е 11, всички стойности в първия стълб лежат в интервала [r,r+1][r,r+1]. Разделяме редовете на две групи: тези с първа координата равна на rr и всички останали. В първата група, ако вземем два различни реда, първите им координати съвпадат, така че максимумът 11 трябва да се достига сред останалите n−1n-1 координати. Следователно след изтриване на първия стълб тази група дава допустима таблица с n−1n-1 стълба, и има най-много M(n−1)M(n-1) реда. Във втората група първите координати са строго по-големи от rr и най-много r+1r+1, затова разликата между първите координати на два реда е строго по-малка от 11. Отново максимумът 11 трябва да се достига сред последните n−1n-1 координати, така че и тази група има най-много M(n−1)M(n-1) реда. ПолучавамеM(n)≤M(n−1)+M(n−1)=2M(n−1).M(n)\le M(n-1)+M(n-1)=2M(n-1).По индукция M(n)≤2nM(n)\le2^n, а конструкцията по-горе показва, че равенство се достига.
Отвори задачатаEvan Chen VONVON EGMO 2012/2Условие — източник

Задача 3

Пълен запис
Условие
Да се реши върху R\mathbb R функционалното уравнениеf(yf(x+y)+f(x))=4x+2yf(x+y).f\left(yf(x+y)+f(x)\right)=4x+2yf(x+y).
РешениеЕдинственото решение еf(x)=2x,f(x)=2x,което се проверява директно. Нека P(x,y)P(x,y) означава даденото условие. От P(x,0)P(x,0) получавамеf(f(x))=4x.f(f(x))=4x.Следователно ff е биекция: тя е сюрективна, защото всяко реално число е от вида 4x4x, и е инективна, защото от f(a)=f(b)f(a)=f(b) следва f(f(a))=f(f(b))f(f(a))=f(f(b)), тоест 4a=4b4a=4b. Освен товаf(4x)=f(f(f(x)))=4f(x).f(4x)=f(f(f(x)))=4f(x).При x=0x=0 това дава f(0)=4f(0)f(0)=4f(0), значи f(0)=0f(0)=0. Сега прилагаме P(0,2)P(0,2). Получавамеf(2f(2))=4f(2).f(2f(2))=4f(2).От вече доказаното равенство f(4x)=4f(x)f(4x)=4f(x) дясната страна е f(8)f(8). Понеже ff е инективна, следва2f(2)=8,2f(2)=8,тоест f(2)=4f(2)=4. Прилагаме и P(0,1)P(0,1):f(f(1))=2f(1).f(f(1))=2f(1).Но от f(f(1))=4f(f(1))=4 получаваме f(1)=2f(1)=2. Накрая вземаме P(x,1−x)P(x,1-x). Тъй като x+(1−x)=1x+(1-x)=1 и f(1)=2f(1)=2, имамеf(2(1−x)+f(x))=4x+2(1−x)f(1)=4.f\left(2(1-x)+f(x)\right)=4x+2(1-x)f(1)=4.А понеже f(2)=4f(2)=4 и ff е инективна, следва2(1−x)+f(x)=2.2(1-x)+f(x)=2.Следователно f(x)=2xf(x)=2x за всяко реално xx, както трябваше да се докаже.
Отвори задачатаEvan Chen VONVON EGMO 2012/3Условие — източник

Задача 5

Пълен запис
Условие
Простите числа pp и qq удовлетворяватpp+1+q+1q=2nn+2\frac{p}{p+1}+\frac{q+1}{q}=\frac{2n}{n+2}за някое положително цяло число nn. Да се намерят всички възможни стойности на q−pq-p.
РешениеОтговорът еq−p∈{2,3,5}.q-p\in\{2,3,5\}.Преобразуваме уравнението:(1−1p+1)+(1+1q)=2−4n+2.\left(1-\frac1{p+1}\right)+\left(1+\frac1q\right)=2-\frac4{n+2}.Следователно4n+2=1p+1−1q=q−p−1q(p+1).\frac4{n+2}=\frac1{p+1}-\frac1q=\frac{q-p-1}{q(p+1)}.Тъй като nn е положително, лявата страна е положителна, значи q−p−1>0q-p-1\gt{}0. Оттукn+2=4q(p+1)q−p−1,n+2=\frac{4q(p+1)}{q-p-1},така чеq−p−1∣4q(p+1).q-p-1\mid 4q(p+1).Освен това 0<q−p−1<q0\lt{}q-p-1\lt{}q. Понеже qq е просто число, получавамеq−p−1∣4(p+1).q-p-1\mid4(p+1).Но тогаваq−p−1∣4(p+1)+4(q−p−1)=4q.q-p-1\mid4(p+1)+4(q-p-1)=4q.Отново използваме, че qq е просто и 0<q−p−1<q0\lt{}q-p-1\lt{}q; следователноq−p−1∣4.q-p-1\mid4.Значи q−p−1q-p-1 е едно от 1,2,41,2,4, тоестq−p∈{2,3,5}.q-p\in\{2,3,5\}.Остава да покажем, че трите стойности наистина се достигат. Например двойките(p,q)=(3,5),(2,5),(2,7)(p,q)=(3,5),\quad(2,5),\quad(2,7)дават съответно q−p=2,3,5q-p=2,3,5, а формулата за n+2n+2 дава положителни цели стойности на nn. Следователно това са точно всички възможности.
Отвори задачатаEvan Chen VONVON EGMO 2012/5Условие — източник

Задача 6

Пълен запис
Условие
В социалната мрежа Mugbook са регистрирани безкрайно много хора. Някои двойки различни потребители са отбелязани като приятели, но всеки човек има само краен брой приятели. Всеки потребител има поне един приятел. Приятелството е симетрично: ако AA е приятел на BB, то BB е приятел на AA. Всеки човек трябва да посочи един от приятелите си като свой най-добър приятел. Ако AA посочи BB за най-добър приятел, не е задължително BB също да посочи AA. Човек, който е посочен за най-добър приятел от някого, се нарича 11-най-добър приятел. По-общо, ако n>1n\gt{}1, потребител е nn-най-добър приятел, ако е посочен за най-добър приятел от някой, който е (n−1)(n-1)-най-добър приятел. Човек, който е kk-най-добър приятел за всяко положително цяло число kk, се нарича популярен. (a) Докажете, че всеки популярен човек е най-добрият приятел на популярен човек. (b) Покажете, че ако хората могат да имат безкрайно много приятели, е възможно популярен човек да не е най-добрият приятел на популярен човек.
РешениеПърво ще използваме следното просто наблюдение. Ако някой е nn-най-добър приятел, то той е и kk-най-добър приятел за всяко 1≤k<n1\le k\lt{}n. Наистина, свойството да бъдеш nn-най-добър приятел означава, че има верига от nn последователни посочвания на най-добър приятел, която завършва в този човек. Като вземем последните kk посочвания от тази верига, получаваме, че същият човек е kk-най-добър приятел. (a) Нека Дани е популярен. Неговите приятели са краен брой; означаваме ги сP1,P2,…,Pm.P_1,P_2,\ldots,P_m.Понеже Дани е популярен, за всяко n≥1n\ge1 той е (n+1)(n+1)-най-добър приятел. Следователно за всяко nn има приятел на Дани, който е nn-най-добър приятел и е посочил Дани за свой най-добър приятел. Имаме само краен брой приятели PiP_i, затова по принципа на Дирихле някой от тях е nn-най-добър приятел за безкрайно много стойности на nn. От наблюдението по-горе този човек е kk-най-добър приятел за всяко фиксирано kk, тоест е популярен. Понеже той е посочил Дани за най-добър приятел, получаваме, че Дани е най-добрият приятел на популярен човек. (b) Ако позволим безкрайно много приятели, предишният аргумент вече няма крайния избор, върху който да приложим принципа на Дирихле. Даваме явна конструкция. Нека има един човек DD и за всяко положително цяло число rr - верига от rr душиPr1,Pr2,…,Prr.P_{r1},P_{r2},\ldots,P_{rr}.Най-добрите приятелства са насочени така:Pr1→D,Pr2→Pr1,…,Prr→Pr,r−1.P_{r1}\to D,\qquad P_{r2}\to P_{r1},\qquad\ldots,\qquad P_{rr}\to P_{r,r-1}.Тоест за всяко rr имаме веригаD⟵Pr1⟵Pr2⟵⋯⟵Prr.D\longleftarrow P_{r1}\longleftarrow P_{r2}\longleftarrow\cdots\longleftarrow P_{rr}.Нека още DD посочи P11P_{11} за свой най-добър приятел, а приятелствата са точно двойките, които се появяват в тези посочвания. Тогава всеки има поне един приятел, а единствено DD има безкрайно много приятели. Човекът DD е популярен, защото за всяко kk съществува верига с дължина поне kk, която завършва в DD. От друга страна, никой от хората PrjP_{rj} не е популярен: зад него в неговата верига има само краен брой хора, така че той може да бъде kk-най-добър приятел само за крайно много стойности на kk. Следователно DD е единственият популярен човек. Но DD не може да бъде най-добрият приятел на популярен човек: единственият популярен човек е самият DD, а DD не посочва себе си за най-добър приятел. Това дава искания пример.
Отвори задачатаEvan Chen VONVON EGMO 2012/6Условие — източник