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

Evan Chen / IMO Solution Notes

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

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

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

2019

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
Да се намерят всички функции f:Z→Zf:\mathbb{Z}\to\mathbb{Z}, за коитоf(2a)+2f(b)=f(f(a+b))f(2a)+2f(b)=f(f(a+b))за всички цели числа aa и bb.
РешениеЩе използваме означението P(a,b)P(a,b) за даденото равенство. От P(0,x)P(0,x) и P(x,0)P(x,0) получаваме съответноf(0)+2f(x)=f(f(x))f(0)+2f(x)=f(f(x))иf(2x)+2f(0)=f(f(x)).f(2x)+2f(0)=f(f(x)).Следователно за всяко цяло xx е изпълненоf(2x)=2f(x)−f(0).f(2x)=2f(x)-f(0).Сега сравняваме P(a,b)P(a,b) с P(0,a+b)P(0,a+b). Имамеf(f(a+b))=f(2a)+2f(b)=f(0)+2f(a+b).f(f(a+b))=f(2a)+2f(b)=f(0)+2f(a+b).Замествайки f(2a)=2f(a)−f(0)f(2a)=2f(a)-f(0), получаваме(f(a)−f(0))+(f(b)−f(0))=f(a+b)−f(0).(f(a)-f(0))+(f(b)-f(0))=f(a+b)-f(0).Значи функцията g(x)=f(x)−f(0)g(x)=f(x)-f(0) е адитивна върху целите числа, откъдето g(x)=cxg(x)=cx за някое цяло число cc. Така f(x)=cx+df(x)=cx+d, където d=f(0)d=f(0). Остава да заместим обратно. Получаваме2ca+2cb+3d=c2a+c2b+cd+d.2ca+2cb+3d=c^2a+c^2b+cd+d.Сравняването на коефициентите дава c2=2cc^2=2c, тоест c=0c=0 или c=2c=2. При c=0c=0 от константния член следва d=0d=0, а при c=2c=2 всяко цяло dd работи. Следователно всички решения саf(x)≡0f(x)\equiv0иf(x)=2x+d(d∈Z).f(x)=2x+d\quad(d\in\mathbb{Z}).
Отвори задачатаEvan Chen VONVON IMO 2019/1Условие — източник

Задача 3

Пълен запис
Условие
В една социална мрежа има 20192019 потребители, като някои двойки от тях са приятели и приятелството е симетрично. Ако A,B,CA,B,C са трима потребители, за които AA е приятел с BB и с CC, но BB и CC не са приятели, администраторът може да извърши следната операция: да промени приятелствата така, че BB и CC да станат приятели, а AA вече да не е приятел нито с BB, нито с CC. Първоначално 10091009 потребители имат по 10101010 приятели, а 10101010 потребители имат по 10091009 приятели. Да се докаже, че администраторът може да извърши поредица от операции, след която всеки потребител има най-много един приятел.
РешениеЩе преведем задачата на езика на графите. Върховете са потребителите, а ребрата са приятелствата. Операцията е следната: ако ABAB и ACAC са ребра, а BCBC не е ребро, махаме ABAB и ACAC и добавяме BCBC. Ще използваме следното твърдение. Ако GG е свързан граф, който не е дърво, цикъл или клика, тогава може да се извърши допустима операция, след която графът остава свързан. Наистина, ако GG не е дърво, той има цикъл; вземаме най-къс цикъл CC. Ако CC не е триъгълник, понеже GG е свързан и CC не е целият граф, има връх bb извън CC, съседен на някой връх aa от CC. Нека cc е съсед на aa по цикъла. Поради минималността на CC върховете bb и cc не са съседни, така че операцията върху a,b,ca,b,c е допустима и не разваля свързаността. Остава случаят, когато има триъгълник. Нека KK е максимална клика. Тъй като GG не е клика и е свързан, има ребро abab, където a∈Ka\in K, а b∉Kb\notin K. От максималността на KK следва, че има връх c∈Kc\in K, който не е съседен на bb. Операцията върху a,b,ca,b,c отново е допустима и запазва свързаността. Това доказва твърдението. Сега се връщаме към дадения граф G0G_0. Той е свързан: ако два върха не са съседни, сумата на степените им е поне 1009+1009=20181009+1009=2018, а освен тях има само 20172017 върха, следователно те имат общ съсед. Освен това графът не може да стане цикъл, защото операцията запазва четността на степента на всеки връх, а първоначално има върхове с нечетна степен 10091009. Графът не може да стане и клика, защото броят на ребрата намалява с 11 при всяка операция. Следователно можем да прилагаме горното твърдение, докато свързаният граф стане дърво. След това продължаваме да правим всяка възможна операция. Понеже започваме от дърво, а операцията маха две ребра по път с дължина 22 и добавя едно ребро между краищата му, цикъл не се създава; графът остава гора. Процесът непременно спира, защото броят на ребрата намалява. Когато вече не може да се направи операция в гора, никой връх не може да има две съседни ребра: в гора две различни съседни на един връх точки никога не са свързани с ребро помежду си. Значи всяка степен е най-много 11, което е точно исканото.
Отвори задачатаEvan Chen VONVON IMO 2019/3Условие — източник

Задача 4

Пълен запис
Условие
Да се реши в положителни цели числа уравнениетоk≠∏i=0n−1(2n−2i)=k\neq{}\prod_{i=0}^{n-1}(2^n-2^i)=(2n−1)(2n−2)(2n−4)…(2n−2n−1).(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}).
РешениеОтговорът е(n,k)=(1,1)и(n,k)=(2,3),(n,k)=(1,1)\quad\text{и}\quad(n,k)=(2,3),които непосредствено се проверяват. НекаA=∏i=0n−1(2n−2i),A=\prod_{i=0}^{n-1}(2^n-2^i),и да допуснем, че A=k!A=k! за някое k≥3k\ge3. Ще използваме означението νp(N)\nu_p(N) за степента на простото число pp в разлагането на NN. От2n−2i=2i(2n−i−1)2^n-2^i=2^i(2^{n-i}-1)получавамеν2(A)=0+1+⋯+(n−1)=n(n−1)2.\nu_2(A)=0+1+\dots+(n-1)=\frac{n(n-1)}2.От формулата на Лежандр ν2(k!)=k−s2(k)<k\nu_2(k!)=k-s_2(k)\lt{}k, следователноk>n(n−1)2.k\gt{}\frac{n(n-1)}2.Сега оценяваме степента на 33. По стандартното повдигане на експонентатаν3(2t−1)={0,t е нечетно, 1+ν3(t/2),t е четно.\nu_3(2^t-1)= \begin{cases} 0,&t\text{ е нечетно},\ 1+\nu_3(t/2),&t\text{ е четно}. \end{cases}Затоваν3(A)=⌊n2⌋+⌊n6⌋+⌊n18⌋+⋯<3n4.\nu_3(A)=\left\lfloor\frac n2\right\rfloor+\left\lfloor\frac n6\right\rfloor+\left\lfloor\frac n{18}\right\rfloor+\dots\lt{}\frac{3n}{4}.От друга страна⌊k3⌋≤ν3(k!)=ν3(A)<3n4,\left\lfloor\frac k3\right\rfloor\le\nu_3(k!)=\nu_3(A)\lt{}\frac{3n}{4},следователно k<9n4+3k\lt{}\frac{9n}{4}+3. Комбинирайки с предишната оценка, получавамеn(n−1)2<k<9n4+3,\frac{n(n-1)}2\lt{}k\lt{}\frac{9n}{4}+3,което принуждава n≤6n\le6. Остава краен преглед. При n=1n=1 получаваме A=1=1!A=1=1!, а при n=2n=2 получаваме A=(4−1)(4−2)=6=3!A=(4-1)(4-2)=6=3!. За n=3,4,5,6n=3,4,5,6 стойностите на AA лежат съответно между две съседни факториелни стойности и не са факториели. Следователно единствените решения са (1,1)(1,1) и (2,3)(2,3).
Отвори задачатаEvan Chen VONVON IMO 2019/4Условие — източник

Задача 5

Пълен запис
Условие
Нека nn е положително цяло число. Хари има nn монети, подредени в редица на бюрото му; всяка от тях показва ези или тура. Той извършва следната операция: ако точно kk монети показват ези и k>0k\gt{}0, обръща kk-тата монета; ако няма монети, които показват ези, процесът спира. Например, ако пишем HH за ези и TT за тура, процесътTHT→HHT→HTT→TTTTHT\to HHT\to HTT\to TTTотнема три стъпки. Да се докаже, че процесът винаги завършва, и да се намери средният брой стъпки по всички 2n2^n начални конфигурации.
РешениеОтговорът еEn=12(1+2+⋯+n)=n(n+1)4.E_n=\frac12(1+2+\dots+n)=\frac{n(n+1)}4.Ще докажем това едновременно със завършването на процеса. Представяме конфигурациите като двоични низове с дължина nn, където 11 означава ези, а 00 означава тура. Нека GnG_n е ориентираният граф върху върховете {0,1}n\{0,1\}^n, в който всяка конфигурация сочи към следващата конфигурация след една операция. Ще опишем GnG_n чрез Gn−1G_{n-1}. Вземаме две копия XX и YY на Gn−1G_{n-1}. В копието XX към всеки низ просто добавяме 00 накрая:s1s2…sn−1↦s1s2…sn−10.s_1s_2\dots s_{n-1}\mapsto s_1s_2\dots s_{n-1}0.В копието YY първо сменяме всеки бит, после обръщаме реда и добавяме 11 накрая:s1s2…sn−1↦sˉn−1sˉn−2…sˉ11.s_1s_2\dots s_{n-1}\mapsto \bar{s}_{n-1}\bar{s}_{n-2}\dots\bar{s}_1 1.Накрая добавяме едно допълнително ребро11…1→11…110.11\dots1\to 11\dots110.Да проверим, че това описание е правилно. В XX добавената нула не променя броя на единиците, така че стрелките са същите като в Gn−1G_{n-1}. За YY, ако низът s1…sn−1s_1\dots s_{n-1} има kk единици, преобразуваният низ има (n−1−k)+1=n−k(n-1-k)+1=n-k единици; обръщането на (n−k)(n-k)-тия бит в новия низ точно съответства на обръщането на kk-тия бит в стария низ. Допълнителното ребро от 11…111\dots1 към 11…11011\dots110 е очевидно вярно. От това описание по индукция следва, че процесът винаги завършва. Нека EnE_n е търсеният среден брой стъпки. Половината конфигурации са в копието XX и дават средно En−1E_{n-1} стъпки. Другата половина са в YY; те първо следват копие на пътя в Gn−1G_{n-1}, а след това минават през конфигурацията 11…111\dots1, от която са нужни още nn стъпки до 00…000\dots0. СледователноEn=12(En−1+En−1+n)=En−1+n2.E_n=\frac12\left(E_{n-1}+E_{n-1}+n\right)=E_{n-1}+\frac n2.С начална стойност E0=0E_0=0 получавамеEn=12(1+2+⋯+n)=n(n+1)4,E_n=\frac12(1+2+\dots+n)=\frac{n(n+1)}4,както трябваше да се докаже.
Отвори задачатаEvan Chen VONVON IMO 2019/5Условие — източник