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

Evan Chen / EGMO Twitch Solution

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

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

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

2024

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

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

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

11-12

3 задачи

Задача 1

Пълен запис
Условие
На дъската са написани две различни цели числа uu и vv. Извършваме последователност от ходове. На всеки ход можем да направим една от следните две операции: 1. Ако aa и bb са различни цели числа на дъската, можем да напишем a+ba+b, ако то още не е написано. 2. Ако a,b,ca,b,c са три различни цели числа на дъската и цяло число xx удовлетворява ax2+bx+c=0ax^2+bx+c=0, можем да напишем xx, ако то още не е написано. Да се намерят всички начални двойки (u,v)(u,v), от които всяко цяло число може в крайна сметка да бъде написано на дъската след краен брой ходове.
РешениеОтговорът е: всички двойки различни цели числа (u,v)(u,v), с изключение на случаите, в които някое от числата е 00, случаят {u,v}={−1,1}\{u,v\}=\{-1,1\} и случаите, в които и двете числа са отрицателни. Първо виждаме защо тези изключения наистина са невъзможни. Ако едно от u,vu,v е 00, операцията със събиране не може да произведе ново число, а за квадратно уравнение са нужни три различни числа, така че не можем да започнем. Ако {u,v}={−1,1}\{u,v\}=\{-1,1\}, операцията със събиране дава само 00, а след това нито една от двете операции не може да добави ново число. Накрая, ако u<0u\lt{}0 и v<0v\lt{}0, тогава всички получени числа остават отрицателни: сборът на две отрицателни числа е отрицателен, а ако a,b,c<0a,b,c\lt{}0, то за x>0x\gt{}0 имаме ax2+bx+c<0ax^2+bx+c\lt{}0, така че положителен корен не може да се появи. Следователно в този случай не можем да получим всички цели числа. Ще докажем, че във всички останали случаи задачата е възможна. Най-напред можем да напишем −1-1. Наистина, можем да напишем u+vu+v, а числата uu, vv и u+vu+v са различни, понеже нито uu, нито vv е 00. Квадратното уравнениеux2+(u+v)x+v=0ux^2+(u+v)x+v=0има корен x=−1x=-1, затова −1-1 може да бъде добавено. След това ще получим положително число m≥2m\ge2. Понеже не сме в случая с две отрицателни числа и нито едно число не е 00, поне едно от u,vu,v е положително. Нека u=max⁡(u,v)>0u=\max(u,v)\gt{}0. Ако u≥2u\ge2, сме готови. Ако u=1u=1, тогава другото число е отрицателно и, понеже случаят {−1,1}\{-1,1\} е изключен, то е най-много −2-2. Вече имаме −1-1, така че можем да напишем 0=(−1)+10=(-1)+1. После уравнението0x2+x+v=00x^2+x+v=0има корен −v≥2-v\ge2, както искаме. Нека вече сме написали такова m≥2m\ge2. Понеже имаме −1-1, можем последователно да напишем m−1,m−2,…,0m-1,m-2,\dots,0. Оттам можем да получим всички неотрицателни цели числа, като първо получим m−1m-1 и после чрез събиране с mm получаваме 2m−1,3m−1,…2m-1,3m-1,\dots, а с многократно добавяне на −1-1 слизаме до всяко число в съответния интервал. Накрая, ако n>0n\gt{}0 вече е написано, то −n-n е корен на0x2+x+n=0,0x^2+x+n=0,затова можем да напишем и всички отрицателни цели числа. Това доказва достатъчността.
Отвори задачатаEvan Chen VONVON EGMO 2024/1Условие — източник

Задача 3

Пълен запис
Условие
Ще наричаме положително цяло число nn особено, ако за всеки положителен делител dd на nn числото d(d+1)d(d+1) дели n(n+1)n(n+1). Докажете, че за всеки четири различни особени положителни цели числа A,B,C,DA,B,C,D е изпълненоgcd⁡(A,B,C,D)=1.\gcd(A,B,C,D)=1.
РешениеПърво отбелязваме, че 11 и всяко просто число са особени. Ще класифицираме съставните особени числа. Твърдение 1. Едно особено число nn има най-много два прости делителя, броени с кратност. Нека pp е най-малкият прост делител на nn и нека c=npc=\frac np. Понеже cc е делител на nn, условието даваc(c+1)∣n(n+1)=cp(cp+1).c(c+1)\mid n(n+1)=cp(cp+1).Следователноc+1∣cp(cp+1).c+1\mid cp(cp+1).Но по модул c+1c+1 имаме c≡−1c\equiv-1, откъдетоcp(cp+1)≡(−p)(1−p)=p(p−1)(modc+1).cp(cp+1)\equiv (-p)(1-p)=p(p-1)\pmod{c+1}.Понеже p(p−1)≠0p(p-1)\ne0 и c+1c+1 дели това число, получаваме c+1≤p(p−1)c+1\le p(p-1), тоестn=cp≤p3−p2<p3.n=cp\le p^3-p^2\lt{}p^3.Тъй като всички прости делители на nn са поне pp, числото nn не може да има три прости делителя с кратност. Твърдение 2. Квадрат на просто число никога не е особен. Ако n=p2n=p^2, от делителя pp трябва да имамеp(p+1)∣p2(p2+1),p(p+1)\mid p^2(p^2+1),тоест p+1∣p2+1p+1\mid p^2+1. Това е невъзможно, защото p2+1≡2(modp+1)p^2+1\equiv2\pmod{p+1}. Твърдение 3. Ако n=pqn=pq е особено, където p>qp\gt{}q са прости числа, тогаваp=(q+1)(q−2)+1.p=(q+1)(q-2)+1.Числото 66 не е особено, така че можем да считаме n>6n\gt{}6. От условията за делителите pp и qq получавамеp(p+1)∣pq(pq+1)⟺p(p+1)\mid pq(pq+1)\quad\Longleftrightarrow\quadp+1∣q(pq+1)⟺p+1∣q(q−1), p+1\mid q(pq+1)\quad\Longleftrightarrow\quad p+1\mid q(q-1),иq(q+1)∣pq(pq+1)⟺q(q+1)\mid pq(pq+1)\quad\Longleftrightarrow\quadq+1∣p(pq+1)⟺q+1∣p(p−1). q+1\mid p(pq+1)\quad\Longleftrightarrow\quad q+1\mid p(p-1).Във второто деление имаме gcd⁡(q+1,p)=1\gcd(q+1,p)=1, понеже p>q+1p\gt{}q+1, следователноp≡1(modq+1).p\equiv1\pmod{q+1}.Пишем p=1+k(q+1)p=1+k(q+1). От друга страна, от p+1∣q(q−1)p+1\mid q(q-1) следва2+k(q+1)=p+1≤q(q−1),2+k(q+1)=p+1\le q(q-1),затова k<q−1k\lt{}q-1 и k∈{1,2,…,q−2}k\in\{1,2,\dots,q-2\}. Ако p+1p+1 се дели на qq, тогава 2+k(q+1)≡0(modq)2+k(q+1)\equiv0\pmod q, тоест k≡−2(modq)k\equiv-2\pmod q, и с горните граници получаваме k=q−2k=q-2. Ако пък p+1p+1 не се дели на qq, тогава от p+1∣q(q−1)p+1\mid q(q-1) и gcd⁡(p+1,q)=1\gcd(p+1,q)=1 би следвало p+1∣q−1p+1\mid q-1, което е невъзможно. Значи непременно k=q−2k=q-2, както твърдяхме. Сега фиксираме просто число ℓ\ell. Особените числа, които се делят на ℓ\ell, са най-много три: самото ℓ\ell; числотоℓ((ℓ+1)(ℓ−2)+1),\ell\big((\ell+1)(\ell-2)+1\big),ако вторият множител е прост; и евентуално число ℓr\ell r, ако съществува просто rr, за коетоℓ=(r+1)(r−2)+1.\ell=(r+1)(r-2)+1.Следователно няма четири различни особени числа с общ прост делител. Това точно означава, че за всеки четири различни особени числа A,B,C,DA,B,C,D имаме gcd⁡(A,B,C,D)=1\gcd(A,B,C,D)=1.
Отвори задачатаEvan Chen VONVON EGMO 2024/3Условие — източник

Задача 5

Пълен запис
Условие
Да се намерят всички функции f:N→Nf:\mathbb N\to\mathbb N, такива че за всички x,y∈Nx,y\in\mathbb N са изпълнени: 1. xx и f(x)f(x) имат еднакъв брой положителни делители; 2. ако x∤yx\nmid y и y∤xy\nmid x, тоgcd⁡(f(x),f(y))>f(gcd⁡(x,y)).\gcd(f(x),f(y))\gt{}f(\gcd(x,y)).
РешениеОтговорът еf(x)=ℓd(x)−1,f(x)=\ell^{d(x)-1},където ℓ\ell е фиксирано просто число, а d(x)d(x) означава броя на положителните делители на xx. Първо проверяваме, че тези функции работят. Ясно е, че ℓd(x)−1\ell^{d(x)-1} има точно d(x)d(x) положителни делители. Ако x∤yx\nmid y и y∤xy\nmid x, тогава в разлагането на gcd⁡(x,y)\gcd(x,y) поне един показател е строго по-малък от съответния показател в xx, а поне един е строго по-малък от съответния показател в yy. Следователноd(gcd⁡(x,y))<min⁡(d(x),d(y)),d(\gcd(x,y))\lt{}\min(d(x),d(y)),и оттукgcd⁡(f(x),f(y))=ℓmin⁡(d(x),d(y))−1>\gcd(f(x),f(y))=\ell^{\min(d(x),d(y))-1}\gt{}ℓd(gcd⁡(x,y))−1=f(gcd⁡(x,y)).\ell^{d(\gcd(x,y))-1}=f(\gcd(x,y)).Сега доказваме, че други решения няма. Имаме f(1)=1f(1)=1. Ако pp е просто число, тогава f(p)f(p) трябва да има точно два делителя, тоест също е просто число. Ако pp и qq са различни прости числа, то p∤qp\nmid q и q∤pq\nmid p, затоваgcd⁡(f(p),f(q))>f(1)=1.\gcd(f(p),f(q))\gt{}f(1)=1.Лявата страна е най-голям общ делител на две прости числа, следователно тези две прости числа трябва да са равни. Значи f(p)f(p) е едно и също просто число за всички прости pp; означаваме го с ℓ\ell. Твърдение 1. За всяко x>1x\gt{}1 числото f(x)f(x) се дели на ℓ\ell. Избираме просто число yy, което не дели xx и е различно от xx в случая, когато xx е просто. Тогава x∤yx\nmid y и y∤xy\nmid x, така чеgcd⁡(f(x),f(y))=gcd⁡(f(x),ℓ)>1.\gcd(f(x),f(y))=\gcd(f(x),\ell)\gt{}1.Значи ℓ∣f(x)\ell\mid f(x). Твърдение 2. Ако p1,…,pkp_1,\dots,p_k са различни прости числа, а q1,…,qkq_1,\dots,q_k също са прости числа, тоf(p1q1−1⋯pkqk−1)=ℓq1q2⋯qk−1.f\left(p_1^{q_1-1}\cdots p_k^{q_k-1}\right)=\ell^{q_1q_2\cdots q_k-1}.Доказваме това с индукция по kk. При k=1k=1 числото pq−1p^{q-1} има qq делители. Тъй като qq е просто и f(pq−1)f(p^{q-1}) се дели на ℓ\ell, единствената възможност е f(pq−1)=ℓq−1f(p^{q-1})=\ell^{q-1}. Нека k≥2k\ge2 и без ограничение q1≥q2≥⋯≥qkq_1\ge q_2\ge\dots\ge q_k. Вземаме ново просто число pp, различно от всички pip_i, и прилагаме условието къмX=p1q1−1⋯pkqk−1X=p_1^{q_1-1}\cdots p_k^{q_k-1}иY=p1q1−1⋯pk−1qk−1−1p.Y=p_1^{q_1-1}\cdots p_{k-1}^{q_{k-1}-1}p.Тези две числа не се делят едно друго, а техният НОД е p1q1−1⋯pk−1qk−1−1p_1^{q_1-1}\cdots p_{k-1}^{q_{k-1}-1}. По индукционното предположениеf(gcd⁡(X,Y))=ℓq1q2⋯qk−1−1.f(\gcd(X,Y))=\ell^{q_1q_2\cdots q_{k-1}-1}.Следователно gcd⁡(f(X),f(Y))\gcd(f(X),f(Y)) е строго по-голям от това число, а понеже f(Y)f(Y) е степен на ℓ\ell, заключаваме, че f(X)f(X) се дели на ℓq1q2⋯qk−1\ell^{q_1q_2\cdots q_{k-1}}. Броят на делителите на f(X)f(X) е q1q2⋯qkq_1q_2\cdots q_k. Но никой собствен делител на произведението q1q2⋯qkq_1q_2\cdots q_k не е по-голям от q1q2⋯qk−1q_1q_2\cdots q_{k-1}, затова единствената възможност еf(X)=ℓq1q2⋯qk−1.f(X)=\ell^{q_1q_2\cdots q_k-1}.Остава да преминем от прости стойности на показателите към произволни. Некаx=p1q1−1⋯pkqk−1r1e1−1⋯rmem−1,x=p_1^{q_1-1}\cdots p_k^{q_k-1}r_1^{e_1-1}\cdots r_m^{e_m-1},където всички основи са различни прости числа, числата qiq_i са прости, а ei≥2e_i\ge2 са произволни цели числа. Пишемn=d(x)=q1⋯qke1⋯em.n=d(x)=q_1\cdots q_k e_1\cdots e_m.Ще докажем с индукция по броя mm на непростите фактори eie_i, че f(x)=ℓn−1f(x)=\ell^{n-1}. Случаят m=0m=0 вече е доказан. Нека m>0m\gt{}0. Ако eme_m е просто, прехвърляме го към списъка с qiq_i и сме готови. Иначе em≥4e_m\ge4 е съставно. По постулата на Бертран избираме просто число qq сem2<q<em.\frac{e_m}{2}\lt{}q\lt{}e_m.Нека zz е ново просто число и разгледамеy=y=p1q1−1⋯pkqk−1r1e1−1⋯rm−1em−1−1rmq−1z.p_1^{q_1-1}\cdots p_k^{q_k-1}r_1^{e_1-1}\cdots r_{m-1}^{e_{m-1}-1}r_m^{q-1}z.Тогава x∤yx\nmid y и y∤xy\nmid x, аgcd⁡(x,y)=\gcd(x,y)=p1q1−1⋯pkqk−1r1e1−1⋯rm−1em−1−1rmq−1.p_1^{q_1-1}\cdots p_k^{q_k-1}r_1^{e_1-1}\cdots r_{m-1}^{e_{m-1}-1}r_m^{q-1}.По индукционното предположениеf(y)=ℓ2q1⋯qke1⋯em−1q−1f(y)=\ell^{2q_1\cdots q_k e_1\cdots e_{m-1}q-1}иf(gcd⁡(x,y))=ℓq1⋯qke1⋯em−1q−1>f(\gcd(x,y))=\ell^{q_1\cdots q_k e_1\cdots e_{m-1}q-1}\gt{}ℓn/2−1.\ell^{n/2-1}.От условието следва, че gcd⁡(f(x),f(y))>f(gcd⁡(x,y))\gcd(f(x),f(y))\gt{}f(\gcd(x,y)), следователноνℓ(f(x))+1>n2.\nu_{\ell}(f(x))+1\gt{}\frac n2.От друга страна,n=d(f(x))=∏s(νs(f(x))+1).n=d(f(x))=\prod_s\big(\nu_s(f(x))+1\big).Ако в това произведение се появи множител, по-голям от n/2n/2, то той трябва да е самото nn. Значи νℓ(f(x))+1=n\nu_{\ell}(f(x))+1=n и няма други прости множители във f(x)f(x). Получаваме f(x)=ℓn−1f(x)=\ell^{n-1}, което завършва доказателството.
Отвори задачатаEvan Chen VONVON EGMO 2024/5Условие — източник