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

Evan Chen / EGMO Twitch Solution

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

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

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

2025

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

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

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

11-12

3 задачи

Задача 1

Пълен запис
Условие
За положително цяло число NN некаc1<c2<⋯<cmc_1\lt{}c_2\lt{}\dots\lt{}c_mса всички положителни цели числа, по-малки от NN и взаимнопрости с NN. Да се намерят всички N≥3N\ge3, за коитоgcd⁡(N,ci+ci+1)≠1\gcd(N,c_i+c_{i+1})\ne1за всяко 1≤i≤m−11\le i\le m-1.
РешениеОтговорът е: всички четни NN и всички степени на 33. Първо правим две прости наблюдения. Ако NN е четно, тогава всички числа cic_i са нечетни, така че всеки сбор ci+ci+1c_i+c_{i+1} е четен. Следователно gcd⁡(N,ci+ci+1)≠1\gcd(N,c_i+c_{i+1})\ne1. Ако NN е нечетно и не се дели на 33, тогава c1=1c_1=1 и c2=2c_2=2, понеже и двете числа са взаимнопрости с NN. Но тогава c1+c2=3c_1+c_2=3 е взаимнопросто с NN, което е забранено. Значи остава да разгледаме нечетните кратни на 33. Ако NN е степен на 33, тогава редицата (ci)(c_i) е точно редицата на положителните числа, по-малки от NN и неделящи се на 33:1,2,4,5,7,8,… .1,2,4,5,7,8,\dots.Всеки две съседни числа в тази редица имат сбор, делящ се на 33, затова условието е изпълнено. Остава да докажем, че други нечетни кратни на 33 не работят. НекаN=3ed,N=3^e d,където e≥1e\ge1, числото d>1d\gt{}1 е нечетно и не се дели на 33. Тогава d≡1d\equiv1 или 5(mod6)5\pmod6. Ако d≡1(mod6)d\equiv1\pmod6, ще покажем, че d−2d-2 и d+1d+1 са съседни членове на редицата (ci)(c_i), а сборът им е взаимнопрост с NN. Наистина,3∣d−1,d∣d,3\mid d-1,\qquad d\mid d,така че числата d−1d-1 и dd не са взаимнопрости с NN. От друга страна,gcd⁡(d−2,N)=gcd⁡(d−2,3ed)=gcd⁡(d−2,3e⋅2)=1\gcd(d-2,N)=\gcd(d-2,3^ed)=\gcd(d-2,3^e\cdot2)=1иgcd⁡(d+1,N)=gcd⁡(d+1,3ed)=gcd⁡(d+1,−3e)=1.\gcd(d+1,N)=\gcd(d+1,3^ed)=\gcd(d+1,-3^e)=1.Следователно между d−2d-2 и d+1d+1 няма друг член на редицата (ci)(c_i). Освен товаgcd⁡(2d−1,N)=gcd⁡(2d−1,3ed)=\gcd(2d-1,N)=\gcd(2d-1,3^ed)=gcd⁡(2d−1,3e⋅2d)=gcd⁡(2d−1,3e)=1,\gcd(2d-1,3^e\cdot2d)=\gcd(2d-1,3^e)=1,така че сборът им е взаимнопрост с NN. Случаят d≡5(mod6)d\equiv5\pmod6 е аналогичен: тогава d−1d-1 и d+2d+2 са съседни членове на редицата, а сборът им 2d+12d+1 е взаимнопрост с NN. Така нечетно кратно на 33 работи само когато d=1d=1, тоест когато NN е степен на 33.
Отвори задачатаEvan Chen VONVON EGMO 2025/1Условие — източник

Задача 2

Пълен запис
Условие
Безкрайна строго растяща редица a1<a2<a3<…a_1\lt{}a_2\lt{}a_3\lt{}\dots от положителни цели числа се нарича централна, ако за всяко положително цяло число nn средното аритметично на първите ana_n члена на редицата е равно на ana_n. Докажете, че съществува безкрайна редица b1,b2,b3,…b_1,b_2,b_3,\dots от положителни цели числа, такава че за всяка централна редица (an)(a_n) има безбройно много положителни цели числа nn, за които an=bna_n=b_n.
РешениеЩе докажем, че може да се вземеbn=2n−1.b_n=2n-1.Фиксираме произволна централна редица (an)(a_n). Ще казваме, че положително цяло число NN се появява, ако ai=Na_i=N за някое ii. Тогава от дефиницията на централна редица следваa1+a2+⋯+aN=N2.a_1+a_2+\dots+a_N=N^2.Ще използваме свободно и факта, че се появяват произволно големи числа, понеже редицата е безкрайна и строго растяща. Разглеждаме пролукитеai+1−ai(i≥1).a_{i+1}-a_i\qquad (i\ge1).Ще разделим доказателството според това дали пролуката 11 се среща безбройно много пъти. Първи случай: има безбройно много пролуки, равни на 11. Тогава има безбройно много числа NN, за които и N−1N-1, и NN се появяват. За всяко такова NN имамеa1+⋯+aN=N2a_1+\dots+a_N=N^2иa1+⋯+aN−1=(N−1)2.a_1+\dots+a_{N-1}=(N-1)^2.Като извадим, получавамеaN=N2−(N−1)2=2N−1.a_N=N^2-(N-1)^2=2N-1.Следователно aN=bNa_N=b_N за безбройно много NN. Втори случай: има само краен брой пролуки, равни на 11. Нека този брой е LL. Твърдение. Има най-много LL пролуки, по-големи от 22. В частност съществуват цяло число kk и индекс n0n_0, такива чеan=2n+ka_n=2n+kза всяко n>n0n\gt{}n_0. Доказателство на твърдението. Нека NN е достатъчно голямо появяващо се число, така че всички пролуки, равни на 11, да са преди индекс NN. Избираме друго появяващо се число от вида N+CN+C, където C>0C\gt{}0. Тогава(N+C)2=a1+⋯+aN+C.(N+C)^2=a_1+\dots+a_{N+C}.Понеже след индекс NN няма пролуки 11, имамеaN+j≥aN+2j(1≤j≤C).a_{N+j}\ge a_N+2j\qquad (1\le j\le C).Следователно(N+C)2≥N2+(aN+2)+(aN+4)+⋯+(aN+2C).(N+C)^2\ge N^2+(a_N+2)+(a_N+4)+\dots+(a_N+2C).Дясната страна еN2+CaN+C(C+1).N^2+C a_N+C(C+1).Сравнявайки с (N+C)2=N2+2NC+C2(N+C)^2=N^2+2NC+C^2, получаваме aN≤2N−1a_N\le2N-1. Ако преди индекс NN има повече от LL пролуки, по-големи от 22, тогава, като използваме a1≥1a_1\ge1, всички останали пролуки поне 22 и най-много LL пролуки, равни на 11, получаваме aN>2N−1a_N\gt{}2N-1. Това противоречи на току-що доказаното. Значи пролуките, по-големи от 22, са най-много LL. Тъй като и пролуките, равни на 11, са краен брой, от някой момент нататък всички пролуки са точно 22, което доказва твърдението. Остава да определим kk. Вземаме достатъчно голямо nn и поставяме M=2n+kM=2n+k. Тогава M=anM=a_n и M+2=an+1M+2=a_{n+1} се появяват, а индексите M+1M+1 и M+2M+2 са след n0n_0. Затова(M+2)2−M2=aM+1+aM+2.(M+2)^2-M^2=a_{M+1}+a_{M+2}.От формулата aj=2j+ka_j=2j+k за големи jj получаваме4M+4=(2(M+1)+k)+(2(M+2)+k)=4M+6+2k.4M+4=(2(M+1)+k)+(2(M+2)+k)=4M+6+2k.Следователно k=−1k=-1. Значи във втория случай също имамеan=2n−1a_n=2n-1за всички достатъчно големи nn, и в частност за безбройно много nn. Това завършва доказателството.
Отвори задачатаEvan Chen VONVON EGMO 2025/2Условие — източник

Задача 5

Пълен запис
Условие
Фиксирано е цяло число n>1n\gt{}1. В една конфигурация на дъска n×nn\times n всяка от n2n^2 клетки съдържа стрелка, сочеща нагоре, надолу, наляво или надясно. При дадена начална конфигурация охлювът Турбо започва от една от клетките и се движи от клетка в клетка. На всеки ход Турбо се премества с една клетка в посоката, указана от стрелката в текущата клетка, като е възможно да излезе извън дъската. След всеки ход стрелките във всички клетки се завъртат на 90∘90^{\circ} обратно на часовниковата стрелка. Наричаме една клетка добра, ако при старт от тази клетка Турбо посещава всяка клетка на дъската точно веднъж, не излиза извън дъската и в края се връща в началната си клетка. Да се определи, в зависимост от nn, максималният възможен брой добри клетки измежду всички начални конфигурации.
РешениеАко nn е нечетно и n>1n\gt{}1, няма как да се обходи цялата дъска в цикъл, който посещава всяка клетка точно веднъж: такъв цикъл би имал нечетна дължина, а решетъчната дъска е двуделен граф и всеки цикъл в нея има четна дължина. Следователно при нечетно nn добри клетки няма и отговорът е 00. Нека сега nn е четно. Ще докажем, че отговорът е n24\frac{n^2}{4}. Всъщност ще покажем малко по-силно твърдение: ако съществува поне една добра клетка, тогава добрите клетки са точно n24\frac{n^2}{4}. Да фиксираме валиден цикъл, започващ от добра клетка. Той има n2n^2 хода, а това число се дели на 44. Ако започнем от всяка четвърта клетка по същия цикъл, стрелките ще бъдат в същото състояние спрямо момента на пристигане, така че Турбо ще проследи същия цикъл. Това дава поне n24\frac{n^2}{4} добри клетки. Остава да докажем, че повече не може. Достатъчно е да разгледаме северозападния ъгъл на дъската. Има само четири възможни начина Турбо да мине през този ъгъл; индексите показват реда на посещаване на съответните клетки една спрямо друга:[↓2↑3↑1][↓2←3↑1][←2←1←3][←2←1↑3].\begin{bmatrix} \downarrow_2 & \uparrow_3 \\ \uparrow_1 & \end{bmatrix} \qquad \begin{bmatrix} \downarrow_2 & \leftarrow_3 \\ \uparrow_1 & \end{bmatrix} \qquad \begin{bmatrix} \leftarrow_2 & \leftarrow_1 \\ \leftarrow_3 & \end{bmatrix} \qquad \begin{bmatrix} \leftarrow_2 & \leftarrow_1 \\ \uparrow_3 & \end{bmatrix}.Това се проверява директно от факта, че Турбо не може да излезе през горната или лявата страна на дъската, а след всяка стъпка всички стрелки се завъртат с едно и също количество. Ще казваме, че две конфигурации са ротации една на друга, ако едната се получава от другата чрез завъртане на всички стрелки с един и същ брой пъти по 90∘90^{\circ}. В четирите локални начина по-горе никои две конфигурации не са ротации една на друга. Следователно за дадена начална конфигурация и даден хамилтонов цикъл моментът по модул 44, в който Турбо минава през северозападния ъгъл, е еднозначно определен. След като този момент е известен, целият насочен хамилтонов цикъл също е еднозначно определен: за всяка клетка знаем в кой момент по модул 44 е посетена и към коя съседна клетка трябва да води стрелката в този момент. Затова различните добри начални клетки могат да бъдат само онези, които се намират през четири стъпки по един и същ цикъл. Следователно броят им е най-много n24\frac{n^2}{4}. За четно nn такива цикли наистина съществуват, например чрез стандартно серпентинно обхождане на дъската, затворено по края. Значи максималният брой добри клетки е n24\frac{n^2}{4}.
Отвори задачатаEvan Chen VONVON EGMO 2025/5Условие — източник