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

Evan Chen / EGMO Twitch Solution

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

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

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

2018

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

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

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

11-12

4 задачи

Задача 2

Пълен запис
Условие
Разгледайте множествотоA={1+1k:k=1,2,3,… }.A=\left\{1+\frac1k:k=1,2,3,\dots\right\}.За всяко цяло число x≥2x\ge2 нека f(x)f(x) означава най-малкото цяло число, за което xx може да се представи като произведение на f(x)f(x) елемента на AA (не задължително различни). Докажете, че съществуват безкрайно много двойки цели числа x≥2x\ge2 и y≥2y\ge2, за коитоf(xy)<f(x)+f(y).f(xy)\lt{}f(x)+f(y).
РешениеЕдна от многото възможни конструкции е следната. Нека n=2e+1n=2^e+1, където e≡5(mod10)e\equiv5\pmod {10}, и вземамеx=11,y=n11.x=11,\qquad y=\frac n{11}.Тогава yy е цяло число, защото 25≡−1(mod11)2^5\equiv-1\pmod {11}. Първо ще използваме две малки наблюдения. За всяко m≥2m\ge2 имамеf(m)≥⌈log⁡2m⌉,f(m)\ge \left\lceil\log_2 m\right\rceil,понеже всеки елемент на AA е най-много 22. От друга страна,n=nn−1⋅2e=(1+1n−1)⋅2e,n=\frac n{n-1}\cdot 2^e=\left(1+\frac1{n-1}\right)\cdot 2^e,така че f(n)=e+1f(n)=e+1. Остава да знаем, че f(11)=5f(11)=5. Действително,11=3332⋅43⋅23,11=\frac{33}{32}\cdot\frac43\cdot2^3,следователно f(11)≤5f(11)\le5. Ако имаше представяне с най-много четири множителя, някой от множителите трябва да има числител, делящ се на 1111; всеки такъв множител е най-много 1110\frac{11}{10}. Но тогава останалите най-много три множителя са най-много 22, и произведението е най-много23⋅1110<11,2^3\cdot\frac{11}{10}\lt{}11,противоречие. Значи f(11)=5f(11)=5. Накрая получавамеf(11)+f(n/11)≥f(11)+f(n/11)\ge5+log⁡2(n/11)=1+log⁡2(16n/11)>1+e=f(n).5+\log_2(n/11)=1+\log_2(16n/11)\gt{}1+e=f(n).Понеже xy=nxy=n, това дава f(xy)<f(x)+f(y)f(xy)\lt{}f(x)+f(y). Такива ee има безкрайно много, следователно и търсените двойки са безкрайно много.
Отвори задачатаEvan Chen VONVON EGMO 2018/2Условие — източник

Задача 3

Пълен запис
Условие
nn-те състезателки на EGMO са означени с C1,C2,…,CnC_1,C_2,\dots,C_n. След състезанието те се нареждат на опашка пред ресторанта по следните правила. - Журито избира началния ред на състезателките в опашката. - Всяка минута журито избира цяло число ii с 1≤i≤n1\le i\le n. - Ако пред състезателката CiC_i има поне ii други състезателки, тя плаща едно евро на журито и се премества напред в опашката с точно ii позиции. - Ако пред състезателката CiC_i има по-малко от ii други състезателки, ресторантът отваря и процесът завършва. За всяко nn докажете, че този процес непременно завършва, и намерете най-големия брой евро, който журито може да събере чрез хитър избор на началния ред и на последователността от ходове.
РешениеМаксималната сума е1+3+7+⋯+(2n−1−1)=2n−n−1.1+3+7+\dots+(2^{n-1}-1)=2^n-n-1.Това число е крайно, така че едновременно ще докажем и че процесът не може да продължава безкрайно. Да наречем всеки платен ход скок и нека xix_i е броят скокове на CiC_i. Забелязваме две неща. Първо, когато CiC_i скача, тя прескача поне една състезателка CjC_j с j>ij\gt{}i. Второ, фиксирана състезателка CiC_i може да прескочи дадена CjC_j с j>ij\gt{}i най-много 1+xj1+x_j пъти: първото прескачане може да се случи преди CjC_j изобщо да се е движила, а всяко следващо изисква CjC_j междувременно да е скочила обратно пред CiC_i. Оттук xn=0x_n=0, а за всяко i<ni\lt{}n имамеxi≤∑j=i+1n(1+xj).x_i\le\sum_{j=i+1}^n(1+x_j).Следователноxn−1≤1,xn−2≤(1+xn−1)+(1+xn)≤3,x_{n-1}\le1,\qquad x_{n-2}\le(1+x_{n-1})+(1+x_n)\le3,и по същия начин индуктивноxi≤2n−i−1.x_i\le 2^{n-i}-1.Сумирането по всички ii дава горната граница 2n−n−12^n-n-1. Остава да построим стратегия, която я достига. Конструкцията е индуктивна. За n=3n=3 например, ако ресторантът е отдясно, може да се получи последователносттаC1C2C3C2C1C3C2C3C1C3C1C2C3C2C1\begin{array}{ccc} C_1&C_2&C_3\cr C_2&C_1&C_3\cr C_2&C_3&C_1\cr C_3&C_1&C_2\cr C_3&C_2&C_1 \end{array}с четири платени скока. В общия случай започваме от обратния ред. Първо прилагаме индукционната стратегия само върху C1,C2,…,Cn−1C_1,C_2,\dots,C_{n-1}, така че техният ред да се обърне. После всяка от C1,C2,…,Cn−1C_1,C_2,\dots,C_{n-1} скача веднъж през CnC_n. След това повтаряме същата индукционна стратегия върху първите n−1n-1 състезателки. Така броят събрани евро ana_n удовлетворяваa1=0,an=2an−1+(n−1),a_1=0,\qquad a_n=2a_{n-1}+(n-1),откъдето an=2n−n−1a_n=2^n-n-1. Това съвпада с горната граница.
Отвори задачатаEvan Chen VONVON EGMO 2018/3Условие — източник

Задача 4

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число. Върху дъска n×nn\times n са поставени няколко неприпокриващи се домина. Стойността на ред или колона е броят домина, които покриват поне една клетка от този ред или тази колона. Конфигурация от домина се нарича балансирана, ако съществува k≥1k\ge1, така че всеки ред и всяка колона има стойност kk. Докажете, че за всяко n≥3n\ge3 съществува балансирана конфигурация, и намерете най-малкия възможен брой домина в такава конфигурация.
РешениеОтговорът е2n3ако n≡0(mod3),\frac{2n}{3}\quad\text{ако } n\equiv0\pmod3,и2nвъв всички останали случаи.2n\quad\text{във всички останали случаи}.Първо доказваме, че по-малко не може. Нека в балансирана конфигурация има dd домина и общата стойност на всеки ред и всяка колона е kk. Броим наредените двойки(ред или колона, домино, което докосва този ред или колона).(\text{ред или колона},\ \text{домино, което докосва този ред или колона}).От една страна, има 2n2n реда и колони общо, всеки със стойност kk, така че броят е 2nk2nk. От друга страна, всяко домино докосва или един ред и две колони, или два реда и една колона; във всички случаи то допринася точно 33. Значи2nk=3d,2nk=3d,тоестd=2n⋅k3.d=2n\cdot\frac{k}{3}.Понеже k≥1k\ge1, първите възможни стойности са 2n3,4n3,2n,…\frac{2n}{3},\frac{4n}{3},2n,\dots; вземаме първата, която е цяло число. Това дава долната граница по-горе. Сега даваме конструкции. Ако n≡0(mod3)n\equiv0\pmod3, поставяме по главния диагонал блокове 3×33\times3 от вида[AABB].\begin{bmatrix} A&A& \\ & &B\\ & &B \end{bmatrix}.Във всеки такъв блок има две домина и k=1k=1, следователно общият брой е 2n/32n/3. Остава случаят n≢0(mod3)n\not\equiv0\pmod3. За n=4,5,6,7n=4,5,6,7 имаме следните блокове с k=3k=3 и съответно 2n2n домина:[AABCDDBCWXYYWXZZ][AABBCHXCHXDGYYDGFFEE]\begin{bmatrix} A&A&B&C\\ D&D&B&C\\ W&X&Y&Y\\ W&X&Z&Z \end{bmatrix} \qquad \begin{bmatrix} A&A&B&B&C\\ H&X& & &C\\ H&X& & &D\\ G& &Y&Y&D\\ G&F&F&E&E \end{bmatrix}[AABCDDBCWWYZXXYZPQRRPQSS][AABBCWWXCPXDHPDHZQQGZYYGFFEE].\begin{bmatrix} A&A&B&C& & \\ D&D&B&C& & \\ & &W&W&Y&Z\\ & &X&X&Y&Z\\ P&Q& & &R&R\\ P&Q& & &S&S \end{bmatrix} \qquad \begin{bmatrix} A&A&B&B& & &C\\ &W&W& & &X&C\\ & &P& & &X&D\\ H& &P& & & &D\\ H&Z& &Q&Q& & \\ G&Z& & &Y&Y& \\ G& & &F&F&E&E \end{bmatrix}.Всеки по-голям размер nn може да се получи като сбор на числа от {4,5,6,7}\{4,5,6,7\}, а блоковете се поставят по главния диагонал. Така получаваме балансирана конфигурация с k=3k=3 и точно 2n2n домина за всички останали n≥4n\ge4.n=3ABn=4ABCDWXYZn=5ABCHXDGYFEn=6ABCDWYZXPQRSn=7ABCWXPDHZQGYFE
Отвори задачатаEvan Chen VONVON EGMO 2018/4Условие — източник

Задача 6

Пълен запис
Условие
Фиксирано е реално число 0<t<120\lt{}t\lt{}\frac12. (a) Докажете, че съществува положително цяло число nn, такова че за всяко множество SS от nn положителни цели числа е изпълнено следното: съществуват различни x,y∈Sx,y\in S и неотрицателно цяло число m≥0m\ge0, за които∣x−my∣≤ty.|x-my|\le ty.(b) Определете дали съществува безкрайно множество SS от положителни цели числа със следното свойство: за всеки две различни x,y∈Sx,y\in S и всяко положително цяло число m>0m\gt{}0 имаме∣x−my∣>ty.|x-my|\gt{}ty.
РешениеПърво доказваме (a). Да допуснем противното за някакво голямо nn и некаS={s1<s2<⋯<sn}.S=\{s_1\lt{}s_2\lt{}\dots\lt{}s_n\}.Понеже условието не трябва да се случва дори при m=0m=0, за всяко j≥2j\ge2 имамеs1>tsj,s_1\gt{}t s_j,и следователно1>s1s2>s1s3>⋯>s1sn>t.1\gt{}\frac{s_1}{s_2}\gt{}\frac{s_1}{s_3}\gt{}\dots\gt{}\frac{s_1}{s_n}\gt{}t.Избираме nn толкова голямо, че (1−t)n−2<t(1-t)^{n-2}\lt{}t. Ако всяко две съседни отношения в горната редица се различаваха по множител повече от 1−t1-t, щяхме да получимs1sn<(1−t)n−2<t,\frac{s_1}{s_n}\lt{}(1-t)^{n-2}\lt{}t,което противоречи на вече доказаното s1sn>t\frac{s_1}{s_n}\gt{}t. Значи за някои i<ji\lt{}j имамеsisj≥1−t.\frac{s_i}{s_j}\ge1-t.Следователно∣si−sj∣=sj−si≤tsj,|s_i-s_j|=s_j-s_i\le t s_j,което е забраненият случай с x=six=s_i, y=sjy=s_j и m=1m=1. Това противоречие доказва (a). За (b) отговорът е да. Ще построим такова множество с жаден алгоритъм. Избираме голямо цяло число NN, за коетоt<12−1N.t\lt{}\frac12-\frac1N.Ще дефинирамеS={s1<s2<… }S=\{s_1\lt{}s_2\lt{}\dots\}индуктивно. Първо нека s1s_1 е произволно просто число, по-голямо от NN. След като вече са избрани s1,…,sks_1,\dots,s_k, избираме sk+1s_{k+1} да бъде просто число, по-голямо от 2sk2s_k, и такова чеsk+1≡si−12(modsi)(i=1,2,…,k).s_{k+1}\equiv\frac{s_i-1}{2}\pmod {s_i}\qquad (i=1,2,\dots,k).Това е възможно по китайската теорема за остатъците и теоремата на Дирихле за прости числа в аритметични прогресии. Проверяваме свойството. Ако i<ji\lt{}j, тогава si/sj<1/2s_i/s_j\lt{}1/2. Затова при x=six=s_i, y=sjy=s_j и всяко положително mm имаме∣si−msj∣>tsj,|s_i-ms_j|\gt{}t s_j,понеже най-близкият случай е m=1m=1, а тогава sj−si>sj/2>tsjs_j-s_i\gt{}s_j/2\gt{}t s_j. В обратната посока разглеждаме x=sjx=s_j, y=siy=s_i. По конструкция дробната част на sj/sis_j/s_i еsi−12si=12−12si.\frac{s_i-1}{2s_i}=\frac12-\frac1{2s_i}.Тя е на разстояние повече от tt от всяко цяло число, защото si>Ns_i\gt{}N и t<12−1Nt\lt{}\frac12-\frac1N. Следователно за всяко положително цяло mm имаме∣sj−msi∣>tsi.|s_j-ms_i|\gt{}t s_i.Това доказва, че построеното безкрайно множество SS има исканото свойство.
Отвори задачатаEvan Chen VONVON EGMO 2018/6Условие — източник