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

Evan Chen / IMO Solution Notes

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

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

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

2016

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

11-12

5 задачи

Задача 2

Пълен запис
Условие
Намерете всички цели числа nn, за които всяка клетка на таблица n×nn\times n може да се запълни с една от буквите I, M и O така, че: - във всеки ред и във всяка колона една трета от записите да са I, една трета да са M и една трета да са O; - във всеки диагонал, чийто брой клетки е кратен на 33, една трета от записите да са I, една трета да са M и една трета да са O. Една таблица n×nn\times n има 4n−24n-2 диагонала.
РешениеОтговорът е: точно тези nn, за които 9∣n9\mid n. Първо построяваме пример за n=9n=9:IIIMMMOOO\crMMMOOOIII\crOOOIIIMMM\crIIIMMMOOO\crMMMOOOIII\crOOOIIIMMM\crIIIMMMOOO\crMMMOOOIII\crOOOIIIMMM\begin{array}{ccccccccc}I&I&I&M&M&M&O&O&O\crM&M&M&O&O&O&I&I&I\crO&O&O&I&I&I&M&M&M\crI&I&I&M&M&M&O&O&O\crM&M&M&O&O&O&I&I&I\crO&O&O&I&I&I&M&M&M\crI&I&I&M&M&M&O&O&O\crM&M&M&O&O&O&I&I&I\crO&O&O&I&I&I&M&M&M\end{array}Повтаряйки този блок по хоризонтала и вертикала, получаваме конструкция за всяко nn, кратно на 99. Сега ще докажем необходимостта. Първо от условието за редовете следва 3∣n3\mid n, така че пишем n=3kn=3k. Разделяме таблицата на k2k^2 блока 3×33\times3. Ще наричаме мултимножество от клетки чисто, ако трите букви се срещат в него поравно; обединение на чисти мултимножества пак е чисто. Чисти са всички колони с номер 2(mod3)2\pmod3, всички редове с номер 2(mod3)2\pmod3 и всички диагонали от условието. Вземаме мултимножественото им обединение. То брои центъра на всеки блок 3×33\times3 четири пъти, а всяка друга клетка точно веднъж. Понеже цялата таблица е чиста, след изваждане на едно копие на цялата таблица получаваме, че множеството от k2k^2 центрове също е чисто. Следователно 3∣k23\mid k^2, тоест 3∣k3\mid k и 9∣n9\mid n.
Отвори задачатаEvan Chen VONVON IMO 2016/2Условие — източник

Задача 3

Пълен запис
Условие
Нека P=A1A2…AkP=A_1A_2\ldots A_k е изпъкнал многоъгълник в равнината. Върховете A1,A2,…,AkA_1,A_2,\ldots,A_k имат цели координати и лежат на една окръжност. Нека SS е лицето на PP. Дадено е нечетно положително цяло число nn, такова че квадратите на дължините на страните на PP са цели числа, делящи се на nn. Докажете, че 2S2S е цяло число, което се дели на nn.
РешениеПо формулата на Гаус за лице 2S2S е цяло число. Достатъчно е да докажем делимостта за n=pen=p^e, където pp е нечетно просто число, а после да приложим резултата към всички прости степени в разлагането на nn. Ще индукцираме по броя върхове. За триъгълник с дължини на страните a,b,ca,b,c формулата на Херон дава16S2=2(a2b2+b2c2+c2a2)−a4−b4−c4.16S^2=2(a^2b^2+b^2c^2+c^2a^2)-a^4-b^4-c^4.Ако pep^e дели a2,b2,c2a^2,b^2,c^2, то p2ep^{2e} дели дясната страна. Понеже pp е нечетно и 2S2S е цяло, оттук следва pe∣2Sp^e\mid 2S. Остава индукционната стъпка. Достатъчно е да намерим диагонал, чийто квадрат на дължината се дели на pep^e: тогава той разрязва многоъгълника на два по-малки вписани многоъгълника с цели координати, към които прилагаме индукционното предположение. Да допуснем противното. Нека O=Ak+1O=A_{k+1} и разгледаме многоъгълника A1A2…AkOA_1A_2\ldots A_kO. Ако никой диагонал няма квадрат на дължината, делящ се на pep^e, прилагаме обобщената теорема на Птолемей след инверсия с център OO. Получаваме равенство от видаx2q1+x2q2+⋯+x2qk−1=q,\sqrt{\vphantom{x^2}q_1}+\sqrt{\vphantom{x^2}q_2}+\cdots+\sqrt{\vphantom{x^2}q_{k-1}}=\sqrt q,където qiq_i и qq са положителни рационални числа, изразени чрез квадратите на съответните страни и диагонали. Известният факт за рационални линейни зависимости между квадратни корени казва, че всички тези корени са рационални кратни на един и същ квадратен корен: съществува положително рационално bb, така че ri=x2qi/br_i=\sqrt{\vphantom{x^2}q_i/b} и r=x2q/br=\sqrt{\vphantom{x^2}q/b} са рационални иr1+r2+⋯+rk−1=r.r_1+r_2+\cdots+r_{k-1}=r.Но условието върху pp-адичните валуации дава νp(ri)>νp(r)\nu_p(r_i)\gt{}\nu_p(r) за всяко ii. Сумирането на рационални числа с такава по-голяма pp-адична валуация не може да даде число с валуация νp(r)\nu_p(r). Противоречие. Следователно желаният диагонал съществува и индукцията завършва доказателството.
Отвори задачатаEvan Chen VONVON IMO 2016/3Условие — източник

Задача 4

Пълен запис
Условие
Множество от положителни цели числа ще наричаме ароматно, ако съдържа поне два елемента и всеки негов елемент има общ прост делител с поне един от останалите елементи. Нека P(n)=n2+n+1P(n)=n^2+n+1. Коя е най-малката възможна положителна стойност на bb, за която съществува неотрицателно цяло число aa, такова че множеството{P(a+1),P(a+2),…,P(a+b)}\{P(a+1),P(a+2),\ldots,P(a+b)\}е ароматно?
РешениеОтговорът е b=6b=6. Първо ще докажем, че b≥6b\ge6. С алгоритъма на Евклид лесно се получаваgcd⁡(P(n),P(n+1))∣1,\gcd(P(n),P(n+1))\mid1,gcd⁡(P(n),P(n+2))∣7,\quad \gcd(P(n),P(n+2))\mid7,gcd⁡(P(n),P(n+3))∣3,\gcd(P(n),P(n+3))\mid3,gcd⁡(P(n),P(n+4))∣19.\quad \gcd(P(n),P(n+4))\mid19.Да допуснем, че b≤5b\le5. Построяваме граф с върхове a+1,a+2,…,a+ba+1,a+2,\ldots,a+b, като свързваме два върха, ако съответните стойности на PP имат нетривиален общ делител; етикетираме реброто с простия делител. Възможни са само етикетите 3,7,193,7,19, съответно за разстояния 3,2,43,2,4, и за всеки от тези етикети може да има най-много едно ребро. При b≤5b\le5 с такива ребра не може всеки връх да има положителна степен, противоречие с ароматността. За построение с b=6b=6 избираме aa чрез китайската теорема за остатъците така, чеa+1≡7(mod19),a+5≡11(mod19),a+1\equiv7\pmod{19},\quad a+5\equiv11\pmod{19},a+2≡2(mod7),a+4≡4(mod7),a+2\equiv2\pmod7,\quad a+4\equiv4\pmod7,a+3≡1(mod3),a+6≡1(mod3).a+3\equiv1\pmod3,\quad a+6\equiv1\pmod3.Тогава P(a+1)P(a+1) и P(a+5)P(a+5) имат общ делител 1919, P(a+2)P(a+2) и P(a+4)P(a+4) имат общ делител 77, а P(a+3)P(a+3) и P(a+6)P(a+6) имат общ делител 33. Следователно полученото множество с шест елемента е ароматно, и най-малката стойност е 66.
Отвори задачатаEvan Chen VONVON IMO 2016/4Условие — източник

Задача 5

Пълен запис
Условие
На дъската е записано уравнението(x−1)(x−2)⋯(x−2016)=(x-1)(x-2)\cdots(x-2016)=(x−1)(x−2)⋯(x−2016),(x-1)(x-2)\cdots(x-2016),с 20162016 линейни множителя от всяка страна. Коя е най-малката възможна стойност на kk, за която може да се изтрият точно kk от тези 40324032 линейни множителя, така че от двете страни да остане поне по един множител и полученото уравнение да няма реални решения?
РешениеОтговорът е 20162016. Най-напред, за всяко i=1,2,…,2016i=1,2,\ldots,2016 поне един от двата множителя (x−i)(x-i) трябва да бъде изтрит; иначе x=ix=i ще бъде решение. Следователно k≥2016k\ge2016. Ще покажем, че 20162016 изтривания са достатъчни. Оставяме отляво множителите с индекси 11 или 00 по модул 44, а отдясно оставяме множителите с индекси 22 или 33 по модул 44. Така за всеки m=1,2,…,504m=1,2,\ldots,504 сравнявамеLm=(x−(4m−3))(x−4m),L_m=(x-(4m-3))(x-4m),Rm=(x−(4m−2))(x−(4m−1)).\qquad R_m=(x-(4m-2))(x-(4m-1)).Винаги имаме Lm<RmL_m\lt{}R_m, защото Rm−Lm=2R_m-L_m=2. Ако xx не лежи между двата вътрешни корена на някой блок, тези неравенства могат да се умножат директно или пък двете страни имат различни знаци; и в двата случая равенство не се получава. Остава само случаят 4m−2<x<4m−14m-2\lt{}x\lt{}4m-1 за някое mm. Тогава LmL_m и RmR_m са отрицателни и∣LmRm∣≥9.\left|\frac{L_m}{R_m}\right|\ge9.Ще използваме оценката∏t=0N(4t+2)(4t+3)(4t+1)(4t+4)<2<e\prod_{t=0}^{N}\frac{(4t+2)(4t+3)}{(4t+1)(4t+4)}\lt{}2\lt{}\mathrm e\quad(N≥0),(N\ge0),която следва, като сдвоим множителите21(34⋅65)(78⋅109)⋯4N+34N+4<\frac21\left(\frac34\cdot\frac65\right)\left(\frac78\cdot\frac{10}9\right)\cdots\frac{4N+3}{4N+4}\lt{}2.2.При 4m−2<x<4m−14m-2\lt{}x\lt{}4m-1 произведението на всички съответни отношения ∣Rj/Lj∣|R_j/L_j| за блоковете преди mm е по-малко от e\mathrm e, и същото важи за блоковете след mm. Затова общо∣∏jRj∏jLj∣<e29<1.\left|\frac{\prod_j R_j}{\prod_j L_j}\right|\lt{}\frac{\mathrm e^2}{9}\lt{}1.Следователно двете произведения не могат да бъдат равни. При целите стойности x=ix=i също няма равенство, защото съответният множител е оставен само от едната страна. Значи полученото уравнение няма реални решения, а минималното kk е 20162016.
Отвори задачатаEvan Chen VONVON IMO 2016/5Условие — източник

Задача 6

Пълен запис
Условие
В равнината са дадени n≥2n\ge2 отсечки, като всеки две от тях се пресичат и никои три не минават през една точка. Джеф трябва да избере по един край на всяка отсечка и да постави там жаба, обърната към другия край. След това той пляска с ръце n−1n-1 пъти. При всяко пляскане всяка жаба веднага скача напред до следващата пресечна точка върху своята отсечка. Жабите никога не сменят посоката на скоковете си. Джеф иска да постави жабите така, че никои две от тях никога да не се окажат в една и съща пресечна точка по едно и също време. (a) Докажете, че Джеф винаги може да изпълни желанието си, ако nn е нечетно. (b) Докажете, че Джеф никога не може да го изпълни, ако nn е четно.
РешениеВземаме достатъчно голяма окръжност ω\omega, която съдържа всички (n2)\binom n2 пресечни точки във вътрешността си. Продължаваме дадените отсечки до прави и отбелязваме техните 2n2n пресечни точки с ω\omega катоP1,P2,…,P2nP_1,P_2,\ldots,P_{2n}в посока на часовниковата стрелка. За всяка отсечка изборът на един от двата й края е еквивалентен на избор на съответния край PiP_i върху тази голяма окръжност, защото редът на пресечните точки по правата не се променя. Ключовото наблюдение е, че всяка дадена отсечка има краища от вида PiP_i и Pi+nP_{i+n}, с индекси по модул 2n2n. Наистина, ако една отсечка има краища PiP_i и PjP_j, то за да я пресече всяка друга отсечка, другата отсечка трябва да има по един край на всяка от двете дъги между PiP_i и PjP_j. Следователно двете дъги съдържат по точно n−1n-1 от останалите точки, откъдето j=i+nj=i+n.12345678Нека първо nn е нечетно. Поставяме жабите в точкитеP1,P3,…,P2n−1.P_1,P_3,\ldots,P_{2n-1}.Понеже nn е нечетно, точките PiP_i и Pi+nP_{i+n} са с различна четност, така че от всяка отсечка е избран точно един край. Да разгледаме две жаби, започващи от PiP_i и PjP_j, където ii и jj са нечетни. След евентуална размяна на имената можем да пишем j=i+dj=i+d, където 1≤d≤n−11\le d\le n-1. Понеже ii и jj са с една и съща четност, числото dd е четно. Жабата от PiP_i достига пресечната точка на двете отсечки след dd пляскания, а жабата от PjP_j достига същата пресечна точка след n−dn-d пляскания. Тези две числа имат различен паритет, защото nn е нечетно. Значи те не са равни и двете жаби не се срещат едновременно в тази пресечна точка. Това важи за всяка двойка жаби, следователно Джеф може да изпълни желанието си. Нека сега nn е четно. Ако Джеф избере две съседни точки PiP_i и Pi+1P_{i+1}, тогава съответните две жаби ще скочат още при първото пляскане в общата пресечна точка на своите две отсечки. Следователно избраните nn точки върху цикъла P1,P2,…,P2nP_1,P_2,\ldots,P_{2n} не могат да съдържат съседни точки. Но избор на nn точки от цикъл с 2n2n точки без две съседни точки е принудително редуващ се: всички избрани точки са или с нечетни, или с четни индекси. Когато nn е четно, точките PiP_i и Pi+nP_{i+n} имат една и съща четност. Затова редуващият се избор или взема и двата края на някоя отсечка, или не взема нито един от тях, което е невъзможно, понеже трябва да се избере точно един край на всяка отсечка. Получаваме противоречие, така че при четно nn Джеф не може да изпълни желанието си.
Отвори задачатаEvan Chen VONVON IMO 2016/6Условие — източник