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

Evan Chen / EGMO Twitch Solution

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

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

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

2013

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

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

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

11-12

3 задачи

Задача 3

Пълен запис
Условие
Нека nn е положително цяло число. (a) Докажете, че съществува множество SS от 6n6n положителни цели числа, такова че най-малкото общо кратно на всеки два негови елемента е най-много 32n232n^2. (b) Докажете, че всяко множество TT от 6n6n положителни цели числа съдържа два елемента с най-малко общо кратно, по-голямо от 9n29n^2.
РешениеЗа (a) вземамеS={1,2,…,4n}∪{4n+2,4n+4,…,8n}.S=\{1,2,\dots,4n\}\cup\{4n+2,4n+4,\dots,8n\}.В това множество има 4n+2n=6n4n+2n=6n числа. Ако два елемента са най-много 4n4n, тяхното НОК е най-много произведението им, тоест най-много 16n216n^2. Ако единият елемент е от първия блок, а другият от втория, произведението им е най-много (4n)(8n)=32n2(4n)(8n)=32n^2, следователно и НОК е най-много 32n232n^2. Ако и двата са от втория блок, общият множител 22 дава горна граница (8n)(8n)/2=32n2(8n)(8n)/2=32n^2. Следователно този избор работи. За (b) нека елементите на множеството TT са подредени катоx0<x1<⋯<xm,x_0\lt{}x_1\lt{}\dots\lt{}x_m,където m=6n−1m=6n-1. Да допуснем противното: всяко НОК на две числа е най-много LL, където L=9n2L=9n^2. За всеки съседен чифт имамеL≥[xi,xi+1]=xixi+1gcd⁡(xi,xi+1)≥L\ge [x_i,x_{i+1}]=\frac{x_ix_{i+1}}{\gcd(x_i,x_{i+1})}\gexixi+1xi+1−xi,\frac{x_ix_{i+1}}{x_{i+1}-x_i},защото общият делител на xix_i и xi+1x_{i+1} дели разликата им. Значи1L≤xi+1−xixixi+1=1xi−1xi+1.\frac1L\le\frac{x_{i+1}-x_i}{x_ix_{i+1}}=\frac1{x_i}-\frac1{x_{i+1}}.Сумираме това за i=k,k+1,…,m−1i=k,k+1,\dots,m-1 и получавамеm−kL≤1xk−1xm<1xk.\frac{m-k}{L}\le\frac1{x_k}-\frac1{x_m}\lt{}\frac1{x_k}.Избираме k=3n−1k=3n-1 и m=6n−1m=6n-1. Тогава m−k=3nm-k=3n, а xk≥k+1=3nx_k\ge k+1=3n, понеже xkx_k е (k+1)(k+1)-вото положително цяло число в подредбата. Следователно3n9n2<1xk≤13n,\frac{3n}{9n^2}\lt{}\frac1{x_k}\le\frac1{3n},което е невъзможно. Полученото противоречие доказва, че някои два елемента имат НОК, по-голямо от 9n29n^2.
Отвори задачатаEvan Chen VONVON EGMO 2013/3Условие — източник

Задача 4

Пълен запис
Условие
Намерете всички положителни цели числа aa и bb, за които съществуват три последователни цели числа, при които полиномът P(n)=1b(n5+a)P(n)=\frac1b(n^5+a) приема цели стойности.
РешениеОтговорът е: или b=1b=1, или b=11b=11 и a≡±1(mod11)a\equiv\pm1\pmod{11}. Случаят b=1b=1 е очевиден. Нека сега b>1b\gt{}1 и нека PP е произволна степен на просто число, която дели bb. Ако трите последователни цели числа са n−1,n,n+1n-1,n,n+1, то(n−1)5+a≡n5+a≡(n+1)5+a≡0(modP).(n-1)^5+a\equiv n^5+a\equiv(n+1)^5+a\equiv0\pmod P.Първо PP не е четно, защото две последователни числа имат различна четност, а значи и петите им степени имат различна четност. Също така простият делител на PP не е 55, понеже от (n+1)5−(n−1)5≡0(mod5)(n+1)^5-(n-1)^5\equiv0\pmod5 бихме получили 2≡0(mod5)2\equiv0\pmod5. В частност 1010 е обратимо по модул PP. Имаме(n+1)5+(n−1)5−2n5≡0(modP),(n+1)^5+(n-1)^5-2n^5\equiv0\pmod P,а лявата страна е 20n3+10n20n^3+10n. Числото nn е взаимно просто с PP, защото иначе от n5+a≡0n^5+a\equiv0 и (n+1)5+a≡0(n+1)^5+a\equiv0 би следвало 1≡01\equiv0 по простия делител на PP. Следователно2n2+1≡0(modP).2n^2+1\equiv0\pmod P.Също така от разликата на крайните пети степени получаваме2((n+1)5−(n−1)5)≡0(modP),2\bigl((n+1)^5-(n-1)^5\bigr)\equiv0\pmod P,тоест20n4+40n2+4≡0(modP).20n^4+40n^2+4\equiv0\pmod P.Използвайки n2≡−12(modP)n^2\equiv-\frac12\pmod P, получаваме0≡20⋅14+40⋅(−12)+4=−11(modP).0\equiv20\cdot\frac14+40\cdot\left(-\frac12\right)+4=-11\pmod P.Значи P∣11P\mid11, откъдето P=11P=11. Понеже PP беше произволна проста степен, деляща bb, следва b=11b=11. Остава да намерим кога модул 1111 има три последователни числа с една и съща пета степен. Проверка на остатъците дава35≡45≡55≡1(mod11),3^5\equiv4^5\equiv5^5\equiv1\pmod{11},както и(−3)5≡(−4)5≡(−5)5≡−1(mod11).(-3)^5\equiv(-4)^5\equiv(-5)^5\equiv-1\pmod{11}.Това са единствените такива тройки от последователни остатъци. Значи трябва и е достатъчно да имаме a≡−1a\equiv-1 или a≡1(mod11)a\equiv1\pmod{11}, съответно. Така получаваме точно посочените решения.
Отвори задачатаEvan Chen VONVON EGMO 2013/4Условие — източник

Задача 6

Пълен запис
Условие
Снежанка и седемте джуджета живеят в къщичката си в гората. Във всеки от 1616 последователни дни част от джуджетата работили в диамантената мина, а останалите събирали горски плодове в гората. Никое джудже не вършило и двете работи в един и същи ден. За всеки два различни дни има поне три джуджета, всяко от които през единия ден е вършило единия вид работа, а през другия ден - другия. Освен това в първия ден всичките седем джуджета работили в диамантената мина. Докажете, че в един от тези 1616 дни всичките седем джуджета са събирали горски плодове.
РешениеЩе кодираме всеки ден с вектор от {0,1}7\{0,1\}^7: координатата е 00, ако съответното джудже е работило в мината, и 11, ако е събирало горски плодове. Условието за всеки два различни дни означава, че разстоянието на Хеминг между всеки два от получените 1616 вектора е поне 33. Понеже първият ден е бил изцяло в мината, нулевият вектор принадлежи на множеството. Преномерираме векторите катоV={v1,v2,…,v16}⊂{0,1}7,V=\{v_1,v_2,\dots,v_{16}\}\subset\{0,1\}^7,така че v16=0000000v_{16}=0000000. Трябва да докажем, че 1111111∈V1111111\in V. Първо ще използваме следната лема. За всеки избор на три координати и за всеки от осемте възможни шаблона върху тях точно два от векторите в VV имат този шаблон. Наистина, не може три различни вектора да съвпадат върху някакви три фиксирани координати. Ако това се случи, изтриваме тези три координати. Получаваме три двоични вектора с дължина 44, чиито взаимни разстояния на Хеминг пак са поне 33. След добавяне по модул 22 на един от тях можем да приемем, че единият е 00000000. Тогава другите два трябва да имат тегло поне 33; но два различни вектора с дължина 44 и тегло поне 33 са на разстояние най-много 22 един от друг. Противоречие. Значи за всяка тройка координати и всеки шаблон има най-много два вектора, а понеже шаблоните са 88 и векторите са 1616, броят е точно два. Същото твърдение за една или две координати следва, като сумираме по останалите координати. Игнорираме нулевия вектор v16v_{16}. За i=1,2,…,15i=1,2,\dots,15 нека nin_i е броят на единиците във viv_i. От лемата и двойно броене получаваме∑i=115(ni1)=162(71)=56,∑i=115(ni2)=1622(72)=84,∑i=115(ni3)=1623(73)=70.\begin{align*} \sum_{i=1}^{15}\binom{n_i}{1}&=\frac{16}{2}\binom71=56,\\ \sum_{i=1}^{15}\binom{n_i}{2}&=\frac{16}{2^2}\binom72=84,\\ \sum_{i=1}^{15}\binom{n_i}{3}&=\frac{16}{2^3}\binom73=70. \end{align*}Например третото равенство брои двойките, състоящи се от вектор и тройка координати, върху които този вектор има само единици. Оттук следва∑i=115ni=56,∑i=115ni2=2⋅84+56=224,∑i=115ni3=6⋅70+3⋅224−2⋅56=980.\begin{align*} \sum_{i=1}^{15}n_i&=56,\\ \sum_{i=1}^{15}n_i^2&=2\cdot84+56=224,\\ \sum_{i=1}^{15}n_i^3&=6\cdot70+3\cdot224-2\cdot56=980. \end{align*}Всеки от тези 1515 вектора е ненулев, така че 1≤ni≤71\le n_i\le7. За всяко цяло 1≤ni≤71\le n_i\le7 имаме(ni−3)(ni−4)(ni−7)≤0.(n_i-3)(n_i-4)(n_i-7)\le0.Сумирайки, намираме0≥∑i=115(ni−3)(ni−4)(ni−7)=∑i=115(ni3−14ni2+61ni−84)=980−14⋅224+61⋅56−15⋅84=0.\begin{align*} 0&\ge\sum_{i=1}^{15}(n_i-3)(n_i-4)(n_i-7)\\ &=\sum_{i=1}^{15}(n_i^3-14n_i^2+61n_i-84)\\ &=980-14\cdot224+61\cdot56-15\cdot84=0. \end{align*}Следователно навсякъде има равенство, т.е. всяко nin_i е едно от числата 3,4,73,4,7. Остава да има поне едно ni=7n_i=7. Ако това не беше вярно, всички nin_i щяха да са 33 или 44, а тогава ni2≡2(mod7)n_i^2\equiv2\pmod7 за всяко ii. Това би дало224=∑i=115ni2≡15⋅2≢0(mod7),224=\sum_{i=1}^{15}n_i^2\equiv15\cdot2\not\equiv0\pmod7,противоречие. Значи някой вектор има седем единици, т.е. 1111111∈V1111111\in V. Това е точно денят, в който всички седем джуджета са събирали горски плодове.
Отвори задачатаEvan Chen VONVON EGMO 2013/6Условие — източник