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

Evan Chen / EGMO Twitch Solution

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

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

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

2023

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

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

  • 2023 · 11-12: липсва задача 2

11-12

4 задачи

Задача 1

Пълен запис
Условие
Дадени са n≥3n\ge3 положителни реални числа a1,a2,…,ana_1,a_2,\dots,a_n. За всяко 1≤i≤n1\le i\le n полагамеbi=ai−1+ai+1ai,b_i=\frac{a_{i-1}+a_{i+1}}{a_i},където индексите се разглеждат по модул nn. Да се предположи, че за всички ii и jj от 11 до nn е изпълненоai≤aj⟺bi≤bj.a_i\le a_j\quad\Longleftrightarrow\quad b_i\le b_j.Докажете, че a1=a2=⋯=ana_1=a_2=\dots=a_n.
РешениеПърво ще докажем, че max⁡bi≤2\max b_i\le2. Нека MM е индекс, за който aM=max⁡aia_M=\max a_i. Понеже редът на числата aia_i и bib_i е един и същ, имаме и bM=max⁡bib_M=\max b_i. НоbM=aM−1+aM+1aM≤2,b_M=\frac{a_{M-1}+a_{M+1}}{a_M}\le2,защото aM−1≤aMa_{M-1}\le a_M и aM+1≤aMa_{M+1}\le a_M. По същия начин, ако mm е индекс, за който am=min⁡aia_m=\min a_i, то bm=min⁡bib_m=\min b_i, аbm=am−1+am+1am≥2.b_m=\frac{a_{m-1}+a_{m+1}}{a_m}\ge2.Следователно всички числа bib_i са равни на 22. Значи за всяко ii имамеai−1+ai+1=2ai.a_{i-1}+a_{i+1}=2a_i.Избираме индекс MM с aM=max⁡aia_M=\max a_i. Тогава двете съседни числа на aMa_M са най-много aMa_M, а сборът им е точно 2aM2a_M, следователно и двете са равни на aMa_M. Продължавайки по цикъла, получаваме, че всички aia_i са равни.
Отвори задачатаEvan Chen VONVON EGMO 2023/1Условие — източник

Задача 3

Пълен запис
Условие
Нека kk е фиксирано положително цяло число. Лекси има речник D\mathbb D, състоящ се от някои низове с дължина kk, които съдържат само буквите AA и BB. Лекси иска да запише във всяка клетка на таблица k×kk\times k една от буквите AA и BB така, че всеки стълб, прочетен отгоре надолу, да е низ от D\mathbb D, и всеки ред, прочетен отляво надясно, също да е низ от D\mathbb D. Кое е най-малкото цяло число mm със следното свойство: ако D\mathbb D съдържа поне mm различни низа, тогава Лекси може да попълни таблицата по този начин, независимо кои точно низове са в D\mathbb D?
РешениеОтговорът еm=2k−1.m=2^{k-1}.Първо показваме, че 2k−1−12^{k-1}-1 низа не стигат. Нека D\mathbb D се състои от всички низове, които започват с AA, с изключение на низа AA…AAA\dots A. Тогава ∣D∣=2k−1−1|\mathbb D|=2^{k-1}-1. Ако съществуваше попълване, всеки стълб щеше да започва с AA, затова първият ред на таблицата щеше да бъде AA…AAA\dots A. Но този низ не е в D\mathbb D, противоречие. Остава да докажем, че 2k−12^{k-1} низа винаги стигат. Ако D\mathbb D съдържа низа AA…AAA\dots A или низа BB…BBB\dots B, просто попълваме цялата таблица съответно само с AA или само с BB. Нека сега нито един от тези два константни низа не е в речника. Останалите 2k−22^k-2 възможни низа се разбиват на 2k−1−12^{k-1}-1 двойки противоположни низове: в една двойка поставяме два низа, които на всяка позиция имат различни букви, например ABBAAABBAA и BAABBBAABB. Понеже ∣D∣≥2k−1>2k−1−1|\mathbb D|\ge2^{k-1}\gt{}2^{k-1}-1, по принципа на Дирихле в D\mathbb D има цяла такава двойка противоположни низове. Нека единият от тях е w=w1w2…wkw=w_1w_2\dots w_k, а другият е противоположният му низ. Попълваме клетката в ред ii и стълб jj с буквата wiw_i, ако wj=Aw_j=A, и с противоположната буква на wiw_i, ако wj=Bw_j=B. Тогава всеки стълб е или ww, или противоположният низ, а всеки ред също е един от тези два низа. Следователно всички редове и стълбове принадлежат на D\mathbb D, както се искаше.
Отвори задачатаEvan Chen VONVON EGMO 2023/3Условие — източник

Задача 4

Пълен запис
Условие
Охлювът Турбо стои в точка от окръжност с дължина 11. Дадена е безкрайна редица от положителни реални числа c1,c2,c3,…c_1,c_2,c_3,\dots. Турбо последователно изминава разстояния c1,c2,c3,…c_1,c_2,c_3,\dots по окръжността, като всеки път избира дали да пълзи по часовниковата стрелка или обратно на часовниковата стрелка. Да се определи най-голямата константа C>0C\gt{}0 със следното свойство: за всяка редица от положителни реални числа c1,c2,c3,…c_1,c_2,c_3,\dots с ci<Cc_i\lt{}C за всички ii, Турбо може, след като разгледа редицата, да гарантира, че има точка от окръжността, която никога няма да посети или да препълзи.
РешениеОтговорът еC=12.C=\frac12.Първо нека ci<12c_i\lt{}\frac12 за всяко ii. Избираме произволна точка PP от окръжността, различна от началната точка на Турбо, и ще я пазим непосетена. Преди всеки ход Турбо не се намира в PP. Двете възможни дъги с дължина ci<12c_i\lt{}\frac12 от текущото място, едната по часовниковата стрелка и другата обратно, не могат и двете да съдържат PP. Затова Турбо избира посоката, чиято дъга не съдържа PP. Така PP никога не се посещава и не се препълзява. Сега ще покажем, че всяко C>12C\gt{}\frac12 е невъзможно. Избираме ε>0\varepsilon\gt{}0 така, че 12+ε<C\frac12+\varepsilon\lt{}C, и разглеждаме редицатаci={12,i е нечетно,12+ε,i е четно.c_i=\begin{cases} \frac12, & i \text{ е нечетно},\\ \frac12+\varepsilon, & i \text{ е четно}. \end{cases}Ако два последователни хода са в една и съща посока, техните дължини имат сбор 1+ε1+\varepsilon, така че Турбо ще препълзи цялата окръжност. Следователно, за да избегне това, той е принуден да редува посоките на движение. При такова редуване след края на 2k2k-тия ход Турбо се намира в край на вече препълзяна дъга с дължина 12+kε\frac12+k\varepsilon. За достатъчно голямо kk тази дължина е поне 11, тоест цялата окръжност е препълзяна. Следователно за всяко C>12C\gt{}\frac12 съществува редица с ci<Cc_i\lt{}C, срещу която Турбо не може да запази непосетена точка.
Отвори задачатаEvan Chen VONVON EGMO 2023/4Условие — източник

Задача 5

Пълен запис
Условие
Дадено е положително цяло число s≥2s\ge2. За всяко положително цяло число kk дефинираме неговото преобразуване k′k' така: записваме k=as+bk=as+b, където a,ba,b са неотрицателни цели числа и b<sb\lt{}s, и полагаме k′=bs+ak'=bs+a. За положително цяло число nn разглеждаме безкрайната редица d1,d2,…d_1,d_2,\dots, където d1=nd_1=n и di+1=di′d_{i+1}=d_i' за всяко положително цяло число ii. Докажете, че тази редица съдържа 11 тогава и само тогава, когато остатъкът на nn при деление на s2−1s^2-1 е 11 или ss.
РешениеЗапочваме с две прости наблюдения. Първо, ако 1≤n<s21\le n\lt{}s^2, то n′n' се получава, като разгледаме nn като двуцифрено число в основа ss (с водеща нула, ако n<sn\lt{}s) и разменим двете му цифри. В частност, повторната размяна връща числото обратно. Второ, ако n≥s2n\ge s^2, то n′<nn'\lt{}n. Наистина, при n=as+bn=as+b имаме a≥s>ba\ge s\gt{}b, аn−n′=(as+b)−(bs+a)=(s−1)(a−b)>0.n-n'=(as+b)-(bs+a)=(s-1)(a-b)\gt{}0.Следователно описаната безкрайна редица в крайна сметка се редува между числата xs+yxs+y и ys+xys+x за някакви x,y∈{0,1,…,s−1}x,y\in\{0,1,\dots,s-1\}. Тя съдържа 11 точно когато {x,y}={1,0}\{x,y\}=\{1,0\}, тоест когато накрая се редува между 11 и ss. Остава да свържем това с остатъка по модул s2−1s^2-1. Ще докажем, чеn′′≡n(mods2−1).n''\equiv n\pmod{s^2-1}.Ако n<s2n\lt{}s^2, това вече следва от размяната на двете цифри два пъти. В общия случай некаn=as2+bs+c,n=as^2+bs+c,където b,c∈{0,1,…,s−1}b,c\in\{0,1,\dots,s-1\} са последните две цифри на nn в основа ss. Тогаваn′=(a+c)s+b,n'=(a+c)s+b,и след още едно преобразуване получавамеn′′=bs+(a+c).n''=bs+(a+c).Затоваn−n′′=as2+c−a−c=a(s2−1),n-n''=as^2+c-a-c=a(s^2-1),което доказва твърдението. Следователно членовете с една и съща четност в редицата имат един и същ остатък по модул s2−1s^2-1. Когато редицата вече се редува между xs+yxs+y и ys+xys+x, тези числа са между 11 и s2−1s^2-1. Затова редицата съдържа 11 точно когато съответният краен двуцикъл е 1,s1,s, което е еквивалентно на това първоначалното nn да дава остатък 11 или ss по модул s2−1s^2-1.
Отвори задачатаEvan Chen VONVON EGMO 2023/5Условие — източник