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

Evan Chen / EGMO Twitch Solution

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

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

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

2026

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

11-12

1 задача

Задача 6

Пълен запис
Условие
Нека pp е просто число и нека nn е положително цяло число, което не се дели на pp. Нека kk е броят на положителните делители на nn, а1=d1<d2<⋯<dk=n1=d_1\lt{}d_2\lt{}\dots\lt{}d_k=nса положителните делители на nn. За i=1,2,…,ki=1,2,\dots,k нека cic_i е броят на положителните делители ℓ\ell на di2d_i^2, за които di−ℓd_i-\ell се дели на pp. Докажете, че(p−1)(c1+c2+⋯+ck)≥k2.(p-1)(c_1+c_2+\dots+c_k)\ge k^2.
РешениеНекаn=q1e1q2e2⋯qmem,n=q_1^{e_1}q_2^{e_2}\cdots q_m^{e_m},където qiq_i са прости числа. Фиксираме примитивен корен gg по модул pp и пишемqi≡gλi(modp).q_i\equiv g^{\lambda_i}\pmod p.По-нататък индексът ii ще пробягва простите множители q1,…,qmq_1,\dots,q_m, а не делителите от условието. Първо ще преформулираме числата cjc_j. Некаdj=q1y1q2y2⋯qmym.d_j=q_1^{y_1}q_2^{y_2}\cdots q_m^{y_m}.Всеки делител ℓ\ell на dj2d_j^2 може да се запише еднозначно във видаℓ=dj∏i=1mqixi,\ell=d_j\prod_{i=1}^m q_i^{x_i},където −yi≤xi≤yi-y_i\le x_i\le y_i за всички ii. Условието dj−ℓd_j-\ell да се дели на pp е равносилно на ℓ≡dj(modp)\ell\equiv d_j\pmod p, тоест∏i=1mqixi≡1(modp).\prod_{i=1}^m q_i^{x_i}\equiv1\pmod p.С избрания примитивен корен това е същото като∑i=1mλixi≡0(modp−1).\sum_{i=1}^m \lambda_i x_i\equiv0\pmod{p-1}.Следователно cjc_j брои точно тези цели mm-торки (x1,…,xm)(x_1,\dots,x_m), за които ∣xi∣≤yi|x_i|\le y_i и горното сравнение е изпълнено. Сега сумираме по всички делители djd_j, или еквивалентно по всички mm-торки (y1,…,ym)(y_1,\dots,y_m) с 0≤yi≤ei0\le y_i\le e_i. Ако фиксираме (x1,…,xm)(x_1,\dots,x_m), броят на възможните yiy_i е ei+1−∣xi∣e_i+1-|x_i|. Получаваме∑j=1kcj=\sum_{j=1}^k c_j=∑−ei≤xi≤ei∑λixi≡0(modp−1)∏i=1m(ei+1−∣xi∣).\begin{aligned} \sum_{\substack{-e_i\le x_i\le e_i\\ \sum \lambda_i x_i\equiv0\pmod{p-1}}} \prod_{i=1}^m (e_i+1-|x_i|).\end{aligned}Ще използваме филтър с корени на единицата. За всяко цяло ss имаме1p−1∑ωp−1=1ωs={1,s≡0(modp−1),0,s≢0(modp−1).\frac1{p-1}\sum_{\omega^{p-1}=1}\omega^s= \begin{cases} 1, & s\equiv0\pmod{p-1},\\ 0, & s\not\equiv0\pmod{p-1}. \end{cases}Затова∑j=1kcj=\sum_{j=1}^k c_j=1p−1∑ωp−1=1∏i=1m(∑xi=−eieiωλixi(ei+1−∣xi∣)). \frac1{p-1}\sum_{\omega^{p-1}=1} \prod_{i=1}^m\left(\sum_{x_i=-e_i}^{e_i}\omega^{\lambda_i x_i}(e_i+1-|x_i|)\right).Остава да оценим вътрешните суми. Ако zz е комплексно число с ∣z∣=1|z|=1, тогава∑x=−eezx(e+1−∣x∣)=∣1+z+⋯+ze∣2.\sum_{x=-e}^{e}z^x(e+1-|x|)=|1+z+\dots+z^e|^2.Наистина, лявата страна се факторизира като(1+z+⋯+ze)(1+z−1+⋯+z−e),(1+z+\dots+z^e)(1+z^{-1}+\dots+z^{-e}),а вторият множител е комплексно спрегнат на първия. Прилагайки това с z=ωλiz=\omega^{\lambda_i}, получаваме∑j=1kcj=\sum_{j=1}^k c_j=1p−1∑ωp−1=1∏i=1m∣1+ωλi+⋯+ωλiei∣2. \frac1{p-1}\sum_{\omega^{p-1}=1} \prod_{i=1}^m\left|1+\omega^{\lambda_i}+\dots+\omega^{\lambda_i e_i}\right|^2.Всички членове в тази сума са неотрицателни. Ако вземем само приноса на ω=1\omega=1, получаваме∑j=1kcj≥\sum_{j=1}^k c_j\ge1p−1(e1+1)2(e2+1)2⋯(em+1)2.\frac1{p-1}(e_1+1)^2(e_2+1)^2\cdots(e_m+1)^2.Ноk=(e1+1)(e2+1)⋯(em+1),k=(e_1+1)(e_2+1)\cdots(e_m+1),така че(p−1)∑j=1kcj≥k2,(p-1)\sum_{j=1}^k c_j\ge k^2,както трябваше да се докаже.
Отвори задачатаEvan Chen VONVON EGMO 2026/6Условие — източник