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

IMO Shortlisted Problems

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

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

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

2024

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

11-12

20 задачи

Задача A1

Пълен запис
Условие
Да се намерят всички реални числа α\alpha, за които числото⌊α⌋+⌊2α⌋+⋯+⌊nα⌋\left\lfloor\alpha\right\rfloor+\left\lfloor2\alpha\right\rfloor+\cdots+\left\lfloor n\alpha\right\rfloorсе дели на nn за всяко положително цяло число nn. Тук ⌊z⌋\left\lfloor z\right\rfloor означава най-голямото цяло число, ненадминаващо zz.
РешениеОтговорът е: всички четни цели числа. Първо проверяваме, че те наистина работят. Ако α=2m\alpha=2m, където mm е цяло число, то⌊α⌋+⌊2α⌋+⋯+⌊nα⌋=\left\lfloor\alpha\right\rfloor+\left\lfloor2\alpha\right\rfloor+\cdots+\left\lfloor n\alpha\right\rfloor=2m+4m+⋯+2mn=mn(n+1),2m+4m+\cdots+2mn=mn(n+1),което се дели на nn. Нека сега α=k+ε\alpha=k+\varepsilon, където kk е цяло число и 0≤ε<10\le\varepsilon\lt{}1. Тогава за всяко nn числото⌊α⌋+⌊2α⌋+⋯+⌊nα⌋=kn(n+1)2+⌊ε⌋+⌊2ε⌋+⋯+⌊nε⌋\begin{aligned} \left\lfloor\alpha\right\rfloor+\left\lfloor2\alpha\right\rfloor+\cdots+\left\lfloor n\alpha\right\rfloor &=\frac{kn(n+1)}2+\left\lfloor\varepsilon\right\rfloor+\left\lfloor2\varepsilon\right\rfloor+\cdots+\left\lfloor n\varepsilon\right\rfloor \end{aligned}се дели на nn. Ако kk е четно, то kn(n+1)/2kn(n+1)/2 винаги се дели на nn. Ще докажем със силна индукция, че ⌊nε⌋=0\left\lfloor n\varepsilon\right\rfloor=0 за всяко nn. За n=1n=1 това следва от 0≤ε<10\le\varepsilon\lt{}1. Ако твърдението е вярно за 1,2,…,n−11,2,\ldots,n-1, то⌊ε⌋+⌊2ε⌋+⋯+⌊nε⌋=⌊nε⌋\left\lfloor\varepsilon\right\rfloor+\left\lfloor2\varepsilon\right\rfloor+\cdots+\left\lfloor n\varepsilon\right\rfloor=\left\lfloor n\varepsilon\right\rfloorсе дели на nn. Но 0≤nε<n0\le n\varepsilon\lt{}n, следователно ⌊nε⌋=0\left\lfloor n\varepsilon\right\rfloor=0. Така 0≤ε<1/n0\le\varepsilon\lt{}1/n за всяко nn, откъдето ε=0\varepsilon=0 и α\alpha е четно цяло число. Остава случаят, когато kk е нечетно. Ще докажем със силна индукция, че ⌊nε⌋=n−1\left\lfloor n\varepsilon\right\rfloor=n-1 за всяко nn. Случаят n=1n=1 е ясен. Ако за m<nm\lt{}n имаме ⌊mε⌋=m−1\left\lfloor m\varepsilon\right\rfloor=m-1, то разглежданата сума еkn(n+1)2+0+1+⋯+(n−2)+⌊nε⌋.\frac{kn(n+1)}2+0+1+\cdots+(n-2)+\left\lfloor n\varepsilon\right\rfloor.Понеже kk е нечетно, това число е сравнимо с 1+⌊nε⌋1+\left\lfloor n\varepsilon\right\rfloor по модул nn. За да се дели на nn, трябва 1+⌊nε⌋1+\left\lfloor n\varepsilon\right\rfloor да се дели на nn. От 0≤nε<n0\le n\varepsilon\lt{}n получаваме ⌊nε⌋=n−1\left\lfloor n\varepsilon\right\rfloor=n-1, както твърдим. Тогава 1−1/n≤ε<11-1/n\le\varepsilon\lt{}1 за всяко nn, което е невъзможно. Следователно други решения няма.
Отвори задачатаMathNetISL 2024 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека nn е положително цяло число. Да се намери най-малката възможна стойност наS=20x02+21x12+⋯+2nxn2,S=2^0x_0^2+2^1x_1^2+\cdots+2^nx_n^2,където x0,x1,…,xnx_0,x_1,\ldots,x_n са неотрицателни цели числа и x0+x1+⋯+xn=nx_0+x_1+\cdots+x_n=n.
РешениеМинималната стойност еn(n+1)2.\frac{n(n+1)}2.Разглеждаме таблица, чиито редове и стълбове са номерирани от 00, а елементът в ред ii и стълб jj еai,j=2i(2j+1)(i,j≥0).a_{i,j}=2^i(2j+1)\qquad(i,j\ge0).Всяко положително цяло число се записва по единствен начин като произведение на степен на 22 и нечетно число, следователно всяко положително цяло число се среща точно веднъж в таблицата. Освен това във всеки ред и във всеки стълб числата строго нарастват. Ако вземем първите xix_i числа от ред ii, тяхната сума е2i(1+3+⋯+(2xi−1))=2ixi2.2^i(1+3+\cdots+(2x_i-1))=2^ix_i^2.Затова SS е сумата на общо nn числа от таблицата, като от всеки ред i=0,1,…,ni=0,1,\ldots,n са взети някакъв начален блок от xix_i числа. Всяка такава сума е поне сумата на най-малките nn положителни цели числа, т.е. поне1+2+⋯+n=n(n+1)2.1+2+\cdots+n=\frac{n(n+1)}2.От друга страна числата 1,2,…,n1,2,\ldots,n образуват допустим избор: във всеки ред на таблицата те заемат начален блок, а всички те лежат сред редовете 0,1,…,n0,1,\ldots,n. Следователно долната граница се достига и тя е търсената минимална стойност.
Отвори задачатаMathNetISL 2024 A2Условие — източник

Задача A3

Пълен запис
Условие
Вярно ли е, че за всяка редица (an)(a_n) от положителни реални числа съществува положително цяло число nn, за което3a1+3a2+⋯+3an(2a1+2a2+⋯+2an)2<\frac{3^{a_1}+3^{a_2}+\cdots+3^{a_n}}{\left(2^{a_1}+2^{a_2}+\cdots+2^{a_n}\right)^2}\lt{}12024?\frac1{2024}?
РешениеДа, вярно е. Ще докажем по-силно твърдение: за всяко ε>0\varepsilon\gt{}0 съществува nn, за което3a1+3a2+⋯+3an(2a1+2a2+⋯+2an)2<ε.\frac{3^{a_1}+3^{a_2}+\cdots+3^{a_n}}{\left(2^{a_1}+2^{a_2}+\cdots+2^{a_n}\right)^2}\lt{}\varepsilon.После вземаме ε=1/2024\varepsilon=1/2024. НекаMn=max⁡(a1,a2,…,an).M_n=\max(a_1,a_2,\ldots,a_n).Първо ще докажем оценката3a1+3a2+⋯+3an(2a1+2a2+⋯+2an)2≤\frac{3^{a_1}+3^{a_2}+\cdots+3^{a_n}}{\left(2^{a_1}+2^{a_2}+\cdots+2^{a_n}\right)^2}\le(34)Mn.\left(\frac34\right)^{M_n}.За всяко ii от 11 до nn имаме (3/2)ai≤(3/2)Mn(3/2)^{a_i}\le(3/2)^{M_n}, откъдето3ai≤(34)Mn2Mn2ai.3^{a_i}\le\left(\frac34\right)^{M_n}2^{M_n}2^{a_i}.Сумирайки по ii, получаваме∑i=1n3ai≤(34)Mn2Mn∑i=1n2ai≤\sum_{i=1}^n3^{a_i}\le\left(\frac34\right)^{M_n}2^{M_n}\sum_{i=1}^n2^{a_i}\le(34)Mn(∑i=1n2ai)2,\left(\frac34\right)^{M_n}\left(\sum_{i=1}^n2^{a_i}\right)^2,което е точно исканата оценка. Поставямеμ=log⁡4/31ε,\mu=\log_{4/3}\frac1\varepsilon,така че (3/4)μ=ε(3/4)^\mu=\varepsilon. Ако има индекс nn с an>μa_n\gt{}\mu, то Mn>μM_n\gt{}\mu и горната оценка веднага дава търсеното неравенство. Остава случаят 0<ai≤μ0\lt{}a_i\le\mu за всяко ii. Тогава за всяко nn имаме3a1+3a2+⋯+3an(2a1+2a2+⋯+2an)2≤\frac{3^{a_1}+3^{a_2}+\cdots+3^{a_n}}{\left(2^{a_1}+2^{a_2}+\cdots+2^{a_n}\right)^2}\len⋅3μn2=3μn.\frac{n\cdot3^\mu}{n^2}=\frac{3^\mu}{n}.За достатъчно голямо nn последното е по-малко от ε\varepsilon. Така и в двата случая намираме подходящо nn, а доказателството е завършено.
Отвори задачатаMathNetISL 2024 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека Z>0\mathbb Z_{\gt{}0} е множеството на всички положителни цели числа. Да се определят всички подмножества S\mathcal S на множеството {20,21,22,…}\{2^0,2^1,2^2,\ldots\}, за които съществува функция f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0} такава, чеS={f(a+b)−f(a)−f(b)∣a,b∈Z>0}.\mathcal S=\{f(a+b)-f(a)-f(b)\mid a,b\in\mathbb Z_{\gt{}0}\}.
РешениеОтговорът е: точно непразните подмножества с най-много два елемента. Първо ще построим примери. Ако S={2k}\mathcal S=\{2^k\}, вземамеf(x)=cx−2k,f(x)=cx-2^k,където cc е цяло число с c>2kc\gt{}2^k. Тогава f(x)>0f(x)\gt{}0 за всяко положително цяло xx иf(a+b)−f(a)−f(b)=2k.f(a+b)-f(a)-f(b)=2^k.Нека сега S={2ℓ,2k}\mathcal S=\{2^\ell,2^k\}, където k>ℓk\gt{}\ell. Вземамеf(x)=(2k−2ℓ)⌊5x2⌋−2ℓ.f(x)=(2^k-2^\ell)\left\lfloor\frac{5x}2\right\rfloor-2^\ell.Функцията отново приема положителни цели стойности. За положителни цели a,ba,b имаме⌊5(a+b)2⌋−⌊5a2⌋−⌊5b2⌋=\left\lfloor\frac{5(a+b)}2\right\rfloor-\left\lfloor\frac{5a}2\right\rfloor-\left\lfloor\frac{5b}2\right\rfloor=⌊a+b2⌋−⌊a2⌋−⌊b2⌋,\left\lfloor\frac{a+b}2\right\rfloor-\left\lfloor\frac a2\right\rfloor-\left\lfloor\frac b2\right\rfloor,а последната разлика е 00 или 11 и приема и двете стойности. Следователно стойностите на f(a+b)−f(a)−f(b)f(a+b)-f(a)-f(b) са точно 2ℓ2^\ell и 2k2^k. Остава да докажем, че други множества не са възможни. Ясно е, че S\mathcal S не може да е празно. За всяка двойка положителни цели числа a,ba,b съществува неотрицателно цяло число e(a,b)e(a,b), за коетоf(a+b)=2e(a,b)+f(a)+f(b).f(a+b)=2^{e(a,b)}+f(a)+f(b).По индукция оттук следва, че за всяко n≥1n\ge1f(n)=f(n)=2e(1,1)+2e(2,1)+⋯+2e(n−1,1)+nf(1).(1)2^{e(1,1)}+2^{e(2,1)}+\cdots+2^{e(n-1,1)}+nf(1).\tag{1}Ще използваме включване на мултимножества. Твърдим, че за всякакви положителни цели nn и kk е вярно{e(1,1),e(2,1),…,e(k−1,1)}⊂{e(n,1),e(n+1,1),…,e(n+k−1,1)}.(2)\{e(1,1),e(2,1),\ldots,e(k-1,1)\}\subset\{e(n,1),e(n+1,1),\ldots,e(n+k-1,1)\}.\tag{2}Доказваме това с индукция по kk. За k=1k=1 твърдението е празно. Нека k≥2k\ge2 и приемем, че (2) е доказано за k−1k-1. От (1) получаваме2e(n,k)=2^{e(n,k)}=(2e(n,1)+2e(n+1,1)+⋯+2e(n+k−1,1))\left(2^{e(n,1)}+2^{e(n+1,1)}+\cdots+2^{e(n+k-1,1)}\right)−(2e(1,1)+2e(2,1)+⋯+2e(k−1,1)).-\left(2^{e(1,1)}+2^{e(2,1)}+\cdots+2^{e(k-1,1)}\right).По индукционното предположение първите k−2k-2 члена от вторите скоби се съдържат в {e(n,1),…,e(n+k−2,1)}\{e(n,1),\ldots,e(n+k-2,1)\}. Значи за някое uu имаме2e(n,k)=2u+2e(n+k−1,1)−2e(k−1,1).2^{e(n,k)}=2^u+2^{e(n+k-1,1)}-2^{e(k-1,1)}.От единствеността на двоичния запис следва{e(n,k),e(k−1,1)}={u,e(n+k−1,1)}\{e(n,k),e(k-1,1)\}=\{u,e(n+k-1,1)\}като мултимножества. Следователно и e(k−1,1)e(k-1,1) се съдържа в дясното мултимножество в (2), което завършва индукцията. Сега ще покажем, че редицатаe(1,1),e(2,1),e(3,1),…e(1,1),e(2,1),e(3,1),\ldotsприема най-много две различни стойности. Да допуснем противното. Нека k≥2k\ge2 е най-малкият индекс, за който e(k,1)≠e(1,1)e(k,1)\ne e(1,1), и нека m>km\gt{}k е индекс, за който e(m,1)e(m,1) е различно и от e(1,1)e(1,1), и от e(k,1)e(k,1). От (2) следва, че всеки блок от kk последователни члена на редицата съдържа поне k−1k-1 стойности, равни на e(1,1)e(1,1). Затоваe(m−1,1)=e(m−2,1)=⋯=e(m−k+1,1)=e(1,1)e(m-1,1)=e(m-2,1)=\cdots=e(m-k+1,1)=e(1,1)иe(m+1,1)=e(m+2,1)=e(m+1,1)=e(m+2,1)=⋯=e(m+k−1,1)=e(1,1).\cdots=e(m+k-1,1)=e(1,1).Но тогава блокътe(m−1,1),e(m,1),e(m+1,1),…,e(m+k−1,1)e(m-1,1),e(m,1),e(m+1,1),\ldots,e(m+k-1,1)има дължина k+1k+1 и не съдържа стойността e(k,1)e(k,1), което противоречи на (2), приложено към блок с дължина k+1k+1. Следователно наистина има най-много две възможни стойности на e(t,1)e(t,1). Накрая, за произволни положителни цели a,ba,b, от (1) получавамеf(a+b)−f(a)−f(b)=f(a+b)-f(a)-f(b)=(2e(a,1)+2e(a+1,1)+⋯+2e(a+b−1,1))\left(2^{e(a,1)}+2^{e(a+1,1)}+\cdots+2^{e(a+b-1,1)}\right)−(2e(1,1)+2e(2,1)+⋯+2e(b−1,1)).-\left(2^{e(1,1)}+2^{e(2,1)}+\cdots+2^{e(b-1,1)}\right).По (2) второто мултимножество от показатели се съдържа в първото, затова тази разлика е равна на 2e(i,1)2^{e(i,1)} за някое ii между aa и a+b−1a+b-1. Но редицата e(1,1),e(2,1),…e(1,1),e(2,1),\ldots приема най-много две различни стойности, така че и S\mathcal S има най-много два елемента. Заедно с построените примери това доказва отговора.
Отвори задачатаMathNetISL 2024 A4Условие — източник

Задача A5

Пълен запис
Условие
Да се намерят всички периодични редици a1,a2,…a_1,a_2,\ldots от реални числа, за които за всяко n≥1n\ge1 са изпълнени условиятаan+2+an2=an+an+12и∣an+1−an∣≤1.a_{n+2}+a_n^2=a_n+a_{n+1}^2\qquad\text{и}\qquad |a_{n+1}-a_n|\le1.
РешениеОтговорът е: точно редицитеc,−c,c,−c,…където ∣c∣≤12,c,-c,c,-c,\ldots\qquad\text{където }|c|\le\frac12,и редицитеd,d,d,d,…където d∈R.d,d,d,d,\ldots\qquad\text{където }d\in\mathbb R.Лесно се проверява, че всички тези редици наистина удовлетворяват условията. При редицата c,−c,c,−c,…c,-c,c,-c,\ldots имаме an+2=ana_{n+2}=a_n и an+12=an2a_{n+1}^2=a_n^2, а второто условие е точно 2∣c∣≤12|c|\le1. При константната редица и двете условия са очевидни. Остава да докажем, че други редици няма. Преписваме първото условие във видаan+2+an+1=(an+1+an)(an+1−an+1).(1)a_{n+2}+a_{n+1}=(a_{n+1}+a_n)(a_{n+1}-a_n+1).\tag{1}Ако за някое положително цяло mm е изпълнено am+1+am=0a_{m+1}+a_m=0, то от (1) следва an+1+an=0a_{n+1}+a_n=0 за всяко n≥mn\ge m. Понеже редицата (an+1+an)(a_{n+1}+a_n) е периодична, това равенство важи за всяко положително цяло nn. Следователно an+1=−ana_{n+1}=-a_n за всяко nn, тоест редицата е от вида c,−c,c,−c,…c,-c,c,-c,\ldots. От ∣an+1−an∣≤1|a_{n+1}-a_n|\le1 получаваме 2∣c∣≤12|c|\le1, както е в отговора. Нека занапред an+1+an≠0a_{n+1}+a_n\ne0 за всяко nn, и нека TT е период на редицата. От (1) получаваме1=∏i=1Tai+2+ai+1ai+1+ai=1=\prod_{i=1}^T\frac{a_{i+2}+a_{i+1}}{a_{i+1}+a_i}=∏i=1T(ai+1−ai+1).\prod_{i=1}^T(a_{i+1}-a_i+1).От условието ∣ai+1−ai∣≤1|a_{i+1}-a_i|\le1 всички множители ai+1−ai+1a_{i+1}-a_i+1 са неотрицателни; тъй като произведението им е 11, те са положителни. Прилагаме неравенството между средно аритметично и средно геометрично:1=∏i=1T(ai+1−ai+1)≤1=\prod_{i=1}^T(a_{i+1}-a_i+1)\le(∑i=1T(ai+1−ai+1)T)T=1.\left(\frac{\sum_{i=1}^T(a_{i+1}-a_i+1)}{T}\right)^T=1.Следователно имаме равенство в това неравенство, така че всички множители са равни. Значиa2−a1=a3−a2=⋯=aT+1−aT.a_2-a_1=a_3-a_2=\cdots=a_{T+1}-a_T.Сумирайки тези равни разлики върху един период, получаваме, че всяка от тях е 00. Следователно редицата е константна, което дава второто семейство от отговора.
Отвори задачатаMathNetISL 2024 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека a0,a1,a2,…a_0,a_1,a_2,\ldots е безкрайна строго растяща редица от положителни цели числа, такава че за всяко n≥1n\ge1 е изпълненоan∈{an−1+an+12,x2an−1an+1}.a_n\in\left\{\frac{a_{n-1}+a_{n+1}}2,\sqrt{\vphantom{x^2}a_{n-1}a_{n+1}}\right\}.Нека b1,b2,…b_1,b_2,\ldots е безкрайна редица от букви, дефинирана чрезbn={A,ако an=12(an−1+an+1),G,иначе.b_n=\begin{cases}A,&\text{ако }a_n=\frac12\left(a_{n-1}+a_{n+1}\right),\\ G,&\text{иначе.}\end{cases}Докажете, че съществуват положителни цели числа n0n_0 и dd, такива че за всяко n≥n0n\ge n_0 е изпълнено bn+d=bnb_{n+d}=b_n.
РешениеЩе докажем малко по-точно твърдение: от някой член нататък периодът на редицата (bn)(b_n) се състои от фиксиран брой букви GG (възможно е този брой да е 00), последвани от една буква AA. Разглеждаме отношенията на два съседни члена на редицата (an)(a_n). Нека CC и DD са взаимно прости положителни цели числа, за коитоa1a0=C+DC.\frac{a_1}{a_0}=\frac{C+D}{C}.Ако bn=Gb_n=G, то ana_n е средно геометрично на an−1a_{n-1} и an+1a_{n+1}, следователноanan−1=an+1an.\frac{a_n}{a_{n-1}}=\frac{a_{n+1}}{a_n}.Ако bn=Ab_n=A и за някое положително цяло kk имамеanan−1=C+kDC+(k−1)D,\frac{a_n}{a_{n-1}}=\frac{C+kD}{C+(k-1)D},то an+1=2an−an−1a_{n+1}=2a_n-a_{n-1} и затоваan+1an=2an−an−1an=C+(k+1)DC+kD.\frac{a_{n+1}}{a_n}=\frac{2a_n-a_{n-1}}{a_n}=\frac{C+(k+1)D}{C+kD}.Следователно по индукция съществува редица от положителни цели числа (kn)(k_n), такава че за всяко n≥1n\ge1anan−1=C+knDC+(kn−1)D.\frac{a_n}{a_{n-1}}=\frac{C+k_nD}{C+(k_n-1)D}.Освен това k1=1k_1=1 иkn+1={kn,ако bn=G,kn+1,ако bn=A.k_{n+1}=\begin{cases}k_n,&\text{ако }b_n=G,\\ k_n+1,&\text{ако }b_n=A.\end{cases}Ако има само краен брой индекси nn с bn=Ab_n=A, твърдението е очевидно: от някой момент нататък всички букви са GG и можем да вземем d=1d=1. Затова занапред предполагаме, че bn=Ab_n=A за безкрайно много nn. Тогава редицата (kn)(k_n) приема всички положителни цели стойности. За всяко q≥1q\ge1 нека mqm_q е последният индекс, за който kmq=qk_{m_q}=q; тогава kmq+1=q+1k_{m_q+1}=q+1. Достатъчно е да докажем, че разликите mq+1−mqm_{q+1}-m_q са константни от някой момент нататък. Първо ще покажем, че тези разлики са ограничени отгоре. Фиксираме положително цяло tt и за q≥1q\ge1 поставямеst(q)=amq(C+qD)t.s_t(q)=\frac{a_{m_q}}{(C+qD)^t}.От формулата за отношенията между съседни членове получавамеst(q+1)=amq+1(C+(q+1)D)t=amq(C+qD)t(C+(q+1)DC+qD)mq+1−mq−t=st(q)(C+(q+1)DC+qD)mq+1−mq−t.\begin{aligned}s_t(q+1)&=\frac{a_{m_{q+1}}}{(C+(q+1)D)^t}\\ &=\frac{a_{m_q}}{(C+qD)^t}\left(\frac{C+(q+1)D}{C+qD}\right)^{m_{q+1}-m_q-t}\\ &=s_t(q)\left(\frac{C+(q+1)D}{C+qD}\right)^{m_{q+1}-m_q-t}. \end{aligned}Понеже дробта в скобите е по-голяма от 11, имаме съответноst(q)>st(q+1),st(q)=st(q+1),s_t(q)\gt{}s_t(q+1),\quad s_t(q)=s_t(q+1),st(q)<st(q+1)\quad s_t(q)\lt{}s_t(q+1)тогава и само тогава, когатоmq+1−mq<t,mq+1−mq=t,mq+1−mq>t.m_{q+1}-m_q\lt{}t,\quad m_{q+1}-m_q=t,\quad m_{q+1}-m_q\gt{}t.Ще използваме и следното наблюдение. Ако mq+1−mq≥tm_{q+1}-m_q\ge t, то st(q)s_t(q) е положително цяло число. Наистина, тогаваkmq+1=kmq+2=⋯=kmq+t=q+1,k_{m_q+1}=k_{m_q+2}=\cdots=k_{m_q+t}=q+1,следователноamq+t=amq(C+(q+1)DC+qD)t.a_{m_q+t}=a_{m_q}\left(\frac{C+(q+1)D}{C+qD}\right)^t.Числата C+(q+1)DC+(q+1)D и C+qDC+qD са взаимно прости, а amq+ta_{m_q+t} е цяло число; затова (C+qD)t(C+qD)^t дели amqa_{m_q} иst(q)=amq(C+qD)ts_t(q)=\frac{a_{m_q}}{(C+qD)^t}е цяло число. Избираме T≥1T\ge1, така че sT(1)<1s_T(1)\lt{}1; такова TT съществува, понеже C+D>1C+D\gt{}1. Ще докажем по индукция, че sT(q)<1s_T(q)\lt{}1 за всяко q≥1q\ge1. Ако sT(q)<1s_T(q)\lt{}1, то sT(q)s_T(q) не е положително цяло число. По предходното наблюдение това означава, че mq+1−mq<Tm_{q+1}-m_q\lt{}T. От сравнението по-горе следва sT(q+1)<sT(q)<1s_T(q+1)\lt{}s_T(q)\lt{}1. Следователно mq+1−mq<Tm_{q+1}-m_q\lt{}T за всяко qq. Нека T′≤TT'\le T е най-голямото цяло число, за което равенството mq+1−mq=T′m_{q+1}-m_q=T' е изпълнено за безкрайно много стойности на qq. От избора на T′T' следва, че за всички достатъчно големи qq имаме mq+1−mq≤T′m_{q+1}-m_q\le T'. Значи редицата sT′(q)s_{T'}(q) е ненарастваща от някой момент нататък. Освен това за безкрайно много qq е изпълнено mq+1−mq=T′m_{q+1}-m_q=T', а тогава по горното наблюдение sT′(q)s_{T'}(q) е положително цяло число. Следователно от някой момент нататък редицата sT′(q)s_{T'}(q) е константна. Наистина, нейните положителни цели стойности образуват ненарастваща редица от положителни цели числа и затова от някое място нататък са равни; между две равни такива стойности цялата ненарастваща редица е принудена да бъде равна на тях. Когато sT′(q)s_{T'}(q) е константна, сравнението по-горе даваmq+1−mq=T′m_{q+1}-m_q=T'за всички достатъчно големи qq. Но bn=Ab_n=A точно за индексите n=mqn=m_q, а всички останали достатъчно големи индекси между два последователни такива индекса дават буква GG. Значи редицата (bn)(b_n) е периодична от някой момент нататък с период T′T', което доказва твърдението.
Отвори задачатаMathNetISL 2024 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека Q\mathbb Q е множеството на рационалните числа. Нека f:Q→Qf:\mathbb Q\to\mathbb Q е функция със следното свойство: за всички x,y∈Qx,y\in\mathbb Q е изпълнено поне едно от равенстватаf(x+f(y))=f(x)+yf(x+f(y))=f(x)+y\qquadилиf(f(x)+y)=x+f(y).\text{или}\qquad f(f(x)+y)=x+f(y).Да се намери максималният възможен брой елементи на множеството{f(x)+f(−x)∣x∈Q}.\{f(x)+f(-x)\mid x\in\mathbb Q\}.
РешениеОтговорът е 22. Ще използваме следните означения. Пишем a→ba\to b, ако f(a)=bf(a)=b, и a∼ba\sim b, ако a→ba\to b или b→ab\to a. С тези означения условието на задачата казва, че за всички рационални x,yx,y е вярноx+f(y)∼f(x)+y.x+f(y)\sim f(x)+y.Поставямеg(x)=f(x)+f(−x).g(x)=f(x)+f(-x).Първо ще покажем, че стойността 22 се достига. Некаf(x)=⌊x⌋−{x},f(x)=\left\lfloor x\right\rfloor-\{x\},където ⌊x⌋\left\lfloor x\right\rfloor е най-голямото цяло число, ненадминаващо xx, а {x}=x−⌊x⌋\{x\}=x-\left\lfloor x\right\rfloor е дробната част на xx. За рационални x,yx,y имамеf(x)+y=⌊x⌋−{x}+⌊y⌋+{y}=(⌊x⌋+⌊y⌋)+({y}−{x}),x+f(y)=⌊x⌋+{x}+⌊y⌋−{y}=(⌊x⌋+⌊y⌋)+({x}−{y}).\begin{aligned} f(x)+y&=\left\lfloor x\right\rfloor-\{x\}+\left\lfloor y\right\rfloor+\{y\}=(\left\lfloor x\right\rfloor+\left\lfloor y\right\rfloor)+(\{y\}-\{x\}),\\ x+f(y)&=\left\lfloor x\right\rfloor+\{x\}+\left\lfloor y\right\rfloor-\{y\}=(\left\lfloor x\right\rfloor+\left\lfloor y\right\rfloor)+(\{x\}-\{y\}). \end{aligned}Ако {x}<{y}\{x\}\lt{}\{y\}, то f(x)+y→x+f(y)f(x)+y\to x+f(y). Ако {x}>{y}\{x\}\gt{}\{y\}, то x+f(y)→f(x)+yx+f(y)\to f(x)+y. Ако {x}={y}\{x\}=\{y\}, двете числа са равни на ⌊x⌋+⌊y⌋\left\lfloor x\right\rfloor+\left\lfloor y\right\rfloor. Следователно условието е изпълнено. Накрая, ако xx е цяло число, то g(x)=0g(x)=0, а ако xx не е цяло число, то g(x)=−2g(x)=-2. Значи са възможни две различни стойности. Остава да докажем, че повече от две стойности не могат да се получат. От условието при y=xy=x следваf(x+f(x))=x+f(x)(1)f(x+f(x))=x+f(x)\tag{1}за всяко рационално xx. Ще докажем лема. Функцията ff е биекция и за всяко рационално xx е изпълненоf(−f(−x))=x.(2)f(-f(-x))=x.\tag{2}Първо доказваме инективност. Нека f(x1)=f(x2)f(x_1)=f(x_2). От условието за двойката (x1,x2)(x_1,x_2) получавамеf(x1)+x2∼f(x2)+x1.f(x_1)+x_2\sim f(x_2)+x_1.Без ограничение на общността нека f(x1)+x2→f(x2)+x1f(x_1)+x_2\to f(x_2)+x_1. Понеже f(x1)=f(x2)f(x_1)=f(x_2), от (1), приложено за x2x_2, следваf(f(x1)+x2)=f(f(x2)+x2)=f(x2)+x2.f(f(x_1)+x_2)=f(f(x_2)+x_2)=f(x_2)+x_2.От друга страна първата стрелка дава f(f(x1)+x2)=f(x2)+x1f(f(x_1)+x_2)=f(x_2)+x_1. Следователно x1=x2x_1=x_2, както искахме. Сега от (1) при x=0x=0 получаваме f(f(0))=f(0)f(f(0))=f(0), а по инективност това дава f(0)=0f(0)=0. Прилагаме условието към двойката (x,−f(x))(x,-f(x)). Тогава0∼x+f(−f(x)).0\sim x+f(-f(x)).Понеже f(0)=0f(0)=0 и ff е инективна, и в двата възможни случая получавамеx+f(−f(x))=0.x+f(-f(x))=0.Значи x=−f(−f(x))x=-f(-f(x)); след замяна на xx с −x-x това е точно (2). От (2) веднага следва, че ff е сюрективна, а вече знаем, че е инективна, следователно е биекция. Нека f−1f^{-1} е обратната функция на ff. От (2) следваf−1(x)=−f(−x),f^{-1}(x)=-f(-x),така чеg(x)=f(x)+f(−x)=f(x)−f−1(x).(3)g(x)=f(x)+f(-x)=f(x)-f^{-1}(x).\tag{3}Да допуснем, че g(x)=ug(x)=u и g(y)=vg(y)=v, където u≠vu\ne v и двете числа u,vu,v са ненулеви. Некаx′=f−1(x),y′=f−1(y).x'=f^{-1}(x),\qquad y'=f^{-1}(y).Тогава по (3) имаме веригитеx′→x→x′+uиy′→y→y′+v.x'\to x\to x'+u\qquad\text{и}\qquad y'\to y\to y'+v.Прилагайки условието към двойките (x′,y)(x',y) и (x,y′)(x,y'), получаваме съответноx+y∼x′+y′+vиx+y∼x′+y′+u.x+y\sim x'+y'+v\qquad\text{и}\qquad x+y\sim x'+y'+u.Двете числа x′+y′+ux'+y'+u и x′+y′+vx'+y'+v са различни. Понеже ff е биекция, от всяко число излиза най-много една стрелка и във всяко число влиза най-много една стрелка. Следователно, след евентуална размяна на двойките (x,u)(x,u) и (y,v)(y,v), можем да приемем, чеx′+y′+u→x+y→x′+y′+v.x'+y'+u\to x+y\to x'+y'+v.От веригата x′→x→x′+ux'\to x\to x'+u и от (2) следва също−x′−u→−x→−x′.-x'-u\to -x\to -x'.Сега прилагаме условието към двойката (x+y,−x′−u)(x+y,-x'-u). Понеже f(−x′−u)=−xf(-x'-u)=-x и f(x+y)=x′+y′+vf(x+y)=x'+y'+v, получавамеy∼y′+v−u.y\sim y'+v-u.Но около yy вече имаме веригата y′→y→y′+vy'\to y\to y'+v, а ff е биекция. Затова числото y′+v−uy'+v-u трябва да е или y′y', или y′+vy'+v. В първия случай u=vu=v, а във втория u=0u=0, и двете противоречат на избора на uu и vv. Следователно gg не може да има две различни ненулеви стойности. От друга страна g(0)=0g(0)=0, така че образът на gg има най-много две стойности. Построеният пример показва, че две стойности наистина са възможни, следователно максималният брой е 22.
Отвори задачатаMathNetISL 2024 A7Условие — източник

Задача A8

Пълен запис
Условие
Нека p≠qp\ne q са взаимно прости положителни цели числа. Да се определят всички безкрайни редици a1,a2,…a_1,a_2,\ldots от положителни цели числа, за които за всяко n≥1n\ge1 и всяко r∈{p,q}r\in\{p,q\} е изпълненоmax⁡0≤t≤ran+t−min⁡0≤t≤ran+t=r.\max_{0\le t\le r}a_{n+t}-\min_{0\le t\le r}a_{n+t}=r.
РешениеОтговорът е: точно редицитеan=n+C,a_n=n+C,където CC е неотрицателно цяло число. Без ограничение нека p<qp\lt{}q. Ще пишем a[r,s]a_{[r,s]} за блока ar,ar+1,…,asa_r,a_{r+1},\ldots,a_s. Некаk=⌈qp⌉.k=\left\lceil\frac qp\right\rceil.Тогава k≥2k\ge2. Първо ще докажем три леми. Лема 1. Ако i,j,mi,j,m са положителни цели числа и ∣i−j∣≤mp|i-j|\le mp, то∣ai−aj∣≤mp.|a_i-a_j|\le mp.Наистина, при ∣i−j∣≤p|i-j|\le p твърдението следва направо от условието за блок с дължина p+1p+1. Общият случай се получава по индукция по mm и неравенството на триъгълника. Лема 2. За фиксирано nn, ако aia_i е минимална сред всички ara_r с r≥nr\ge n, тоi≤n+p−1.i\le n+p-1.Да допуснем противното, т.е. i≥n+pi\ge n+p. Тогава в блока a[i−p,i+q−p]a_{[i-p,i+q-p]} минимумът е aia_i. Понеже q−p≤(k−1)pq-p\le(k-1)p, от Лема 1 всеки член на този блок е най-многоai+(k−1)p<ai+q.a_i+(k-1)p\lt{}a_i+q.Затова разликата между максимума и минимума в този блок е по-малка от qq, което противоречи на условието за блоковете с дължина q+1q+1. Лема 3. За фиксирано n>qn\gt{}q, ако aia_i е максимална сред всички ara_r с r≤nr\le n, тоi≥n−p+1.i\ge n-p+1.Нека aja_j е минимална сред всички ara_r с r≥n−qr\ge n-q. От Лема 2 имаме j≤n−q+p−1j\le n-q+p-1, така че jj лежи в блока [n−q,n][n-q,n]. Следователно aja_j е минимумът в a[n−q,n]a_{[n-q,n]}, а aia_i е поне максимума на същия блок. Значиai≥aj+q.a_i\ge a_j+q.От Лема 2 следва още, че за всеки ss и всеки r≥sr\ge s е вярноar≥min⁡(a[s,s+p]).a_r\ge\min\left(a_{[s,s+p]}\right).Ако i<ji\lt{}j, прилагаме това за s=is=i и r=jr=j и получавамеaj≥min⁡(a[i,i+p])≥ai−p,a_j\ge\min\left(a_{[i,i+p]}\right)\ge a_i-p,което противоречи на ai≥aj+qa_i\ge a_j+q. Следователно i>ji\gt{}j. Освен това ∣ai−aj∣≥q>(k−1)p|a_i-a_j|\ge q\gt{}(k-1)p, така че по Лема 1 имаме ∣i−j∣>(k−1)p|i-j|\gt{}(k-1)p. Понеже i>ji\gt{}j,i>j+(k−1)p≥n−q+(k−1)p≥n−p,i\gt{}j+(k-1)p\ge n-q+(k-1)p\ge n-p,и оттук i≥n−p+1i\ge n-p+1. Некаbn=min⁡r≥nar.b_n=\min_{r\ge n}a_r.От Лема 2 следва, че bn+p>bnb_{n+p}\gt{}b_n за всяко nn, а същоbn=min⁡(a[n,n+p])=min⁡(a[n,n+q]).b_n=\min\left(a_{[n,n+p]}\right)=\min\left(a_{[n,n+q]}\right).Некаcn=max⁡r≤nar.c_n=\max_{r\le n}a_r.От Лема 3 следва, че за n>qn\gt{}q максимумът cnc_n се достига в последните pp позиции преди nn, откъдетоcn=max⁡(a[n−p,n])=max⁡(a[n−q,n]).c_n=\max\left(a_{[n-p,n]}\right)=\max\left(a_{[n-q,n]}\right).Затова за всяко n>qn\gt{}q имамеbn=cn+p−p=cn+q−q.b_n=c_{n+p}-p=c_{n+q}-q.Следователноbn+q−p+p=cn+q=bn+q,b_{n+q-p}+p=c_{n+q}=b_n+q,тоестbn+q−p=bn+q−p.(1)b_{n+q-p}=b_n+q-p.\tag{1}От друга страна an+pa_{n+p} принадлежи на блока a[n,n+p]a_{[n,n+p]}, чийто минимум е bnb_n и чиято ширина е pp. Значиbn+p≤an+p≤bn+p,b_{n+p}\le a_{n+p}\le b_n+p,така чеbn+p−bn≤p.(2)b_{n+p}-b_n\le p.\tag{2}Итерирайки (2) общо q−pq-p пъти, получавамеbn+p(q−p)−bn≤p(q−p).b_{n+p(q-p)}-b_n\le p(q-p).Но от (1), приложено pp пъти, следваbn+p(q−p)−bn=p(q−p).b_{n+p(q-p)}-b_n=p(q-p).Следователно във всички събираеми в тази итерация има равенство, и по-специалноbn+p=bn+p(3)b_{n+p}=b_n+p\tag{3}за всички достатъчно големи nn. От (1) и (3) редицата bn−nb_n-n има периоди pp и q−pq-p от някой момент нататък. Понеже gcd⁡(p,q−p)=1\operatorname{gcd}(p,q-p)=1, тя е константна от някой момент нататък. Значиbn+1=bn+1b_{n+1}=b_n+1за всички достатъчно големи nn. Когато bn+1>bnb_{n+1}\gt{}b_n, минимумът bnb_n не може да се появява след индекса nn, следователно an=bna_n=b_n. Прилагайки същото и за n+1n+1, получавамеan+1=bn+1=bn+1=an+1a_{n+1}=b_{n+1}=b_n+1=a_n+1за всички достатъчно големи nn. Значи съществуват цяло число CC и индекс NN, такива чеan=n+Ca_n=n+Cза всяко n≥Nn\ge N. Остава да върнем това равенство назад. Нека an=n+Ca_n=n+C за всички n≥Nn\ge N. От условието за блока a[N−1,N+p−1]a_{[N-1,N+p-1]} получавамеp=max⁡(aN−1,N+C+p−1)−min⁡(aN−1,N+C).p=\max\left(a_{N-1},N+C+p-1\right)-\min\left(a_{N-1},N+C\right).СледователноaN−1=N+C+pилиaN−1=N+C−1.a_{N-1}=N+C+p\quad\text{или}\quad a_{N-1}=N+C-1.По същия начин, от условието за блока a[N−1,N+q−1]a_{[N-1,N+q-1]} получавамеaN−1=N+C+qилиaN−1=N+C−1.a_{N-1}=N+C+q\quad\text{или}\quad a_{N-1}=N+C-1.Понеже p≠qp\ne q, остава самоaN−1=N+C−1.a_{N-1}=N+C-1.С индукция назад получаваме an=n+Ca_n=n+C за всички положителни цели nn. Накрая a1≥1a_1\ge1, затова C≥0C\ge0. Обратно, всяка редица an=n+Ca_n=n+C с неотрицателно цяло CC очевидно удовлетворява условието.
Отвори задачатаMathNetISL 2024 A8Условие — източник

Задача C1

Пълен запис
Условие
Нека nn е положително цяло число. Клас от nn ученици участва в nn състезания, като във всяко от тях учениците са класирани без равенства. Казваме, че ученик има оценка (a,b)(a,b), където aa и bb са положителни цели числа, ако в поне aa от състезанията той е сред първите bb места. Крайният резултат на ученика е максималната възможна стойност на a−ba-b измежду всички негови оценки. Да се намери максималната възможна сума на крайните резултати на всички nn ученици.
РешениеОтговорът еn(n−1)2.\frac{n(n-1)}2.Първо ще покажем, че тази стойност се достига. Нека във всички nn състезания класирането е едно и също. Тогава ученикът, който винаги е на kk-то място, има оценка (n,k)(n,k) и следователно краен резултат поне n−kn-k. По-добър резултат не може да получи, защото никога не е сред първите k−1k-1 места. Затова сумата на резултатите е∑k=1n(n−k)=n(n−1)2.\sum_{k=1}^n(n-k)=\frac{n(n-1)}2.Остава да докажем, че по-голяма сума е невъзможна. Във всяко състезание даваме на ученика на kk-то място тегло1−kn.1-\frac{k}{n}.Ако даден ученик е сред първите bb места в поне aa състезания, то общата сума на теглата му в тези състезания е понеa(1−bn)=a−abn≥a−b,a\left(1-\frac bn\right)=a-\frac{ab}{n}\ge a-b,понеже a≤na\le n. Следователно общата сума на всички тегла на този ученик е поне крайния му резултат. В едно състезание сумата на теглата е∑k=1n(1−kn)=n−n+12=n−12.\sum_{k=1}^n\left(1-\frac{k}{n}\right)=n-\frac{n+1}{2}=\frac{n-1}{2}.За всички nn състезания общата сума на теглата еn⋅n−12=n(n−1)2.n\cdot\frac{n-1}{2}=\frac{n(n-1)}2.Понеже сумата на крайните резултати на учениците не може да надвишава общата сума на теглата, получаваме търсената горна граница. Конструкцията по-горе я достига, така че максималната възможна сума е n(n−1)2\frac{n(n-1)}2.
Отвори задачатаMathNetISL 2024 C1Условие — източник

Задача C2

Пълен запис
Условие
Нека nn е положително цяло число. Числата 1,2,3,…,n21,2,3,\ldots,n^2 трябва да се запишат в клетките на дъска n×nn\times n така, че всяко число да е записано в точно една клетка и всяка клетка да съдържа точно едно число. За всеки делител dd на nn наричаме dd-деление на дъската разделянето ѝ на (n/d)2(n/d)^2 непресичащи се поддъски с размер d×dd\times d, така че всяка клетка да принадлежи на точно една поддъска. Ще казваме, че nn е хубаво число, ако числата могат да се запишат върху дъската n×nn\times n така, че за всеки делител dd на nn с 1<d<n1\lt{}d\lt{}n, във dd-делението на дъската сумата на числата във всяка поддъска d×dd\times d да не е кратна на dd. Да се намерят всички четни хубави числа.
РешениеОтговорът е: точно числатаn=2k,n=2^k,където kk е положително цяло число. Първо ще докажем с индукция, че всяко n=2kn=2^k е хубаво число. При n=2n=2 няма делител dd с 1<d<n1\lt{}d\lt{}n, така че базата е тривиална. Нека 2k2^k вече е хубаво число. Ще построим подходящо запълване на дъска 2k+1×2k+12^{k+1}\times2^{k+1}. Разделяме я на четири поддъски 2k×2k2^k\times2^k и във всяка от тях записваме едно и също добро запълване PP на дъска 2k×2k2^k\times2^k. После към всички числа във втората поддъска прибавяме 22k2^{2k}, към всички числа в третата прибавяме 2⋅22k2\cdot2^{2k}, а към всички числа в четвъртата прибавяме 3⋅22k3\cdot2^{2k}. Така получаваме всички числа от 11 до 22(k+1)2^{2(k+1)}. Сега разменяме числото 22k2^{2k} от първата поддъска с числото 22k+2k−12^{2k}+2^{k-1} от втората поддъска. Също така разменяме числото 3⋅22k3\cdot2^{2k} от третата поддъска с числото 3⋅22k+2k−13\cdot2^{2k}+2^{k-1} от четвъртата поддъска. Ще проверим, че полученото запълване работи. Ако d=2id=2^i и i<ki\lt{}k, то при всяка поддъска 2i×2i2^i\times2^i прибавените константи и извършените размени не променят сумата по модул 2i2^i. Затова тази сума е същата по модул 2i2^i като сумата на съответната поддъска в PP, а тя не е 00. Остава случаят d=2kd=2^k. Нека четирите големи поддъски са номерирани с b+1b+1, където b∈{0,1,2,3}b\in\{0,1,2,3\}. Сумата в (b+1)(b+1)-вата поддъска е22k−1(1+22k)+b24k+(−1)b2k−1≡2k−1(mod2k).2^{2k-1}(1+2^{2k})+b2^{4k}+(-1)^b2^{k-1}\equiv2^{k-1}\pmod{2^k}.Следователно тя не е кратна на 2k2^k. Индукцията е завършена. Остава да докажем, че други четни хубави числа няма. Некаn=2sm,n=2^s m,където s≥1s\ge1, а m>1m\gt{}1 е нечетно. Да допуснем, че nn е хубаво число. Твърдение. За всяко ii с 1≤i≤s1\le i\le s във 2i2^i-делението сумата във всяка поддъска 2i×2i2^i\times2^i е сравнима с 2i−12^{i-1} по модул 2i2^i. Доказателство на твърдението. При i=1i=1 сумата във всяка поддъска 2×22\times2 не е кратна на 22, т.е. е нечетна. Нека твърдението е вярно за ii. Всяка поддъска 2i+1×2i+12^{i+1}\times2^{i+1} е обединение на четири поддъски 2i×2i2^i\times2^i, всяка със сума, сравнима с 2i−12^{i-1} по модул 2i2^i. Следователно сумата на голямата поддъска е кратна на 2i2^i. Тя обаче не е кратна на 2i+12^{i+1} по условие, значи е сравнима с 2i2^i по модул 2i+12^{i+1}. Това доказва твърдението. Сега сумираме сумите на всички m2m^2 поддъски 2s×2s2^s\times2^s. От твърдението получаваме, че общата сума на всички числа на дъската е сравнима сm2⋅2s−1≡2s−1(mod2s),m^2\cdot2^{s-1}\equiv2^{s-1}\pmod{2^s},защото mm е нечетно. От друга страна тази обща сума е1+2+⋯+n2=n2(n2+1)2=22s−1m2(22sm2+1)≡1+2+\cdots+n^2=\frac{n^2(n^2+1)}2=2^{2s-1}m^2(2^{2s}m^2+1)\equiv0(mod2s),0\pmod{2^s},което е противоречие. Следователно четните хубави числа са точно степените на 22.
Отвори задачатаMathNetISL 2024 C2Условие — източник

Задача C4

Пълен запис
Условие
Нека NN е положително цяло число. Джеф и Кери играят следната игра. В началото на дъската са записани числата 1,2,…,N1,2,\ldots,N. След това играчите се редуват да правят ходове, като Джеф започва. Един ход се състои в избиране на двойка цели числа (k,n)(k,n), където k⩾0k\geqslant 0, а nn е едно от числата на дъската; след това се изтрива всяко число ss на дъската, за което 2k∣n−s2^k\mid n-s. Играта продължава, докато дъската стане празна. Играчът, който изтрие последното число на дъската, губи. Да се намерят всички стойности на NN, за които Джеф може да си осигури победа независимо от играта на Кери.
РешениеЩе наричаме дадено крайно множество от положителни цели числа печеливша позиция, ако играчът на ход може да си осигури победа, и губеща позиция в противния случай. За две множества S\mathcal S и T\mathcal T полагамеJ(S,T)={2s−1:s∈S}∪{2t:t∈T}.J(\mathcal S,\mathcal T)=\{2s-1:s\in\mathcal S\}\cup\{2t:t\in\mathcal T\}.Първо, S\mathcal S е печеливша точно когато J(S,∅)J(\mathcal S,\varnothing) е печеливша, и също точно когато J(∅,S)J(\varnothing,\mathcal S) е печеливша. Наистина, ходът (k,m)(k,m) в S\mathcal S съответства на хода (k+1,2m−1)(k+1,2m-1) в J(S,∅)J(\mathcal S,\varnothing). Обратно, всеки ход върху J(S,∅)J(\mathcal S,\varnothing) е съответният ход върху нечетното копие на S\mathcal S: при k=0k=0 се изтрива всичко, а при k≥1k\ge1 ход с избрано число 2m−12m-1 съответства на (k−1,m)(k-1,m) в S\mathcal S. Същото важи и за четното копие. Второ, ако S\mathcal S и T\mathcal T са непразни и поне едно от тях е губещо, то J(S,T)J(\mathcal S,\mathcal T) е печеливша позиция. Ако например S\mathcal S е губеща, играчът изтрива цялото четно копие J(∅,T)J(\varnothing,\mathcal T) с ход (1,t)(1,t) за някое четно tt от него и оставя губещата позиция J(S,∅)J(\mathcal S,\varnothing). Другият случай е аналогичен. Трето, ако S\mathcal S е непразна печеливша позиция, то J(S,S)J(\mathcal S,\mathcal S) е губеща позиция. Поради симетрията между четното и нечетното копие е достатъчно да разглеждаме първи ход, избрал нечетно число. Ход с k=0k=0 изтрива всичко и веднага губи. При k>0k\gt{}0 след хода остава позиция от вида J(U,S)J(\mathcal U,\mathcal S) за някое U⊆S\mathcal U\subseteq\mathcal S. Ако U=∅\mathcal U=\varnothing, противникът получава печелившото копие J(∅,S)J(\varnothing,\mathcal S). Ако U\mathcal U е губеща, противникът изтрива четното копие и оставя J(U,∅)J(\mathcal U,\varnothing), което е губещо. Ако U\mathcal U е непразна печеливша, противникът прави симетричния ход в четното копие и оставя J(U,U)J(\mathcal U,\mathcal U), което по индукция по ∣S∣|\mathcal S| е губещо. От второто и третото твърдение следва, че за всяко n≥1n\ge1 позицията [2n]={1,2,…,2n}=J([n],[n])[2n]=\{1,2,\ldots,2n\}=J([n],[n]) е печеливша точно когато [n][n] е губеща. Освен това [2n+1][2n+1] е печеливша за всяко n≥1n\ge1. Ако [n][n] е губеща, то[2n+1]=J([n+1],[n])[2n+1]=J([n+1],[n])е печеливша по второто твърдение. Ако [n][n] е печеливша, тогава [2n][2n] е губеща; играчът изтрива само числото 2n+12n+1, като избере достатъчно голямо kk, и оставя губещата позиция [2n][2n]. Нека сега N=t2aN=t2^a, където tt е нечетно. Ако t=1t=1, то NN е степен на 22. Позицията [1][1] е губеща, защото всеки ход изтрива последното число. От връзката между [2n][2n] и [n][n] получаваме по индукция, че [2a][2^a] е печеливша точно когато aa е нечетно. Ако t>1t\gt{}1, то tt е нечетно и t≥3t\ge3, така че [t][t] е печеливша по доказаното за нечетните дължини. При всяко умножаване по 22 статусът се обръща, следователно [t2a][t2^a] е печеливша точно когато aa е четно. Значи Джеф печели точно за следните NN: ако N=2aN=2^a, трябва aa да е нечетно; ако N=t2aN=t2^a с нечетно t>1t\gt{}1, трябва aa да е четно.
Отвори задачатаMathNetISL 2024 C4Условие — източник

Задача C5

Пълен запис
Условие
Нека nn и TT са положителни цели числа. Джеймс има 4n4n топчета с тегла 1,2,…,4n1,2,\ldots,4n. Той ги поставя върху везна така, че двете блюда да имат равни общи тегла. Андрю може да премества топче от едното блюдо на другото, стига абсолютната разлика между общите тегла на двете блюда да остава най-много TT. Да се намери, като функция на nn, най-малкото положително цяло число TT, за което Андрю може да направи редица от ходове, след която всяко топче е на противоположното блюдо, независимо от първоначалното разположение на Джеймс.
РешениеОтговорът е 4n4n. Първо, T≥4nT\ge4n е необходимо. Ако топче с тегло ww се премести от едното блюдо на другото, разликата между теглата на блюдата се променя с 2w2w. За да бъде абсолютната разлика най-много TT и преди, и след хода, трябва w≤Tw\le T. Понеже топчето с тегло 4n4n трябва да бъде преместено, получаваме T≥4nT\ge4n. Ще докажем, че T=4nT=4n винаги е достатъчно. Общото тегло на едно блюдо в началото еA=n(4n+1).A=n(4n+1).Ще казваме, че разположение е допустимо, ако разликата между теглата на блюдата е най-много 4n4n. Случаят n=1n=1 е отделен. Тогава първоначално едното блюдо съдържа топчетата 1,41,4, а другото 2,32,3. Преместванията на топчетата с тегла 2,4,3,12,4,3,1 в този ред са допустими и накрая всяко топче е сменило блюдото. Нека оттук нататък n≥2n\ge2. Наричаме топчетата с тегло най-много 2n2n малки. Лема 1. Ако две допустими разположения се различават само по местата на малките топчета, то от едното може да се стигне до другото чрез допустими ходове. Доказателство. Първо местим само малки топчета, които са на грешното блюдо и не са на по-лекото блюдо. Такъв ход е допустим и намалява броя на грешно поставените топчета. Когато това вече не е възможно, всички останали грешни малки топчета са на по-лекото блюдо. Ако ги местим едно по едно, абсолютната разлика нараства към крайното допустимо разположение, затова никой междинен ход не нарушава границата 4n4n. Лема 2. Всяко положително цяло число, ненадвишаващо k(k+1)/2k(k+1)/2, може да се представи като сума на различни числа от 1,2,…,k1,2,\ldots,k. Това следва по индукция по kk: числата до k−1k-1 се покриват от индукционното предположение, а по-големите се получават, като се добави kk към подходяща сума от числа до k−1k-1. Също така за n≥2n\ge2 имаме n(2n+1)≥4nn(2n+1)\ge4n. Ще покажем как последователно да преместим всички немалки топчета на противоположното блюдо. Нека 2n<m≤4n2n\lt{}m\le4n. Наричаме топчетата с тегло по-голямо от mm големи, а топчетата с тегла от 2n+12n+1 до mm средни. Да допуснем, че всички големи топчета вече са на правилното блюдо, топчето mm още е на грешното блюдо и текущото разположение е допустимо. Ще преместим mm правилно, без да местим големите топчета. Да приемем, че mm е на лявото блюдо. Ако общото тегло на средните и големите топчета на дясното блюдо е повече отn(4n+1)+2n−m,n(4n+1)+2n-m,тогава, понеже големите топчета вдясно тежат най-много n(4n+1)−mn(4n+1)-m, вдясно има средно топче m′<mm'\lt{}m. Първо чрез Лема 1 пренареждаме малките топчета така, че всички да са вляво; това е допустимо. После по Лема 2 връщаме някои малки топчета вдясно така, че дясното блюдо да има тегло точно n(4n+1)+2nn(4n+1)+2n. Тогава преместването на m′m' наляво е допустимо. Повтаряме тази операция, докато теглото на средните и големите топчета вдясно стане най-много n(4n+1)+2n−mn(4n+1)+2n-m. След това нека теглото на дясното блюдо еn(4n+1)+2n−m+x,n(4n+1)+2n-m+x,а общото тегло на малките топчета вдясно е yy. От предишната стъпка имаме y≥xy\ge x. Ако x≤0x\le0, преместването на mm надясно е допустимо. Ако x>0x\gt{}0, по Лема 2 избираме малки топчета с общо тегло y−xy-x и чрез Лема 1 ги пренареждаме така, че теглото на дясното блюдо да стане точно n(4n+1)+2n−mn(4n+1)+2n-m. Тогава преместването на mm надясно е допустимо. Прилагаме описаната процедура за m=4n,4n−1,…,2n+1m=4n,4n-1,\ldots,2n+1. Така всички немалки топчета се оказват на противоположните блюда. Накрая само малките топчета може да са разместени неправилно, а Лема 1 позволява да довършим преместването им. Следователно T=4nT=4n е достатъчно и минималната стойност е 4n4n.
Отвори задачатаMathNetISL 2024 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека NN е положително цяло число и нека a1,a2,…a_1,a_2,\ldots е безкрайна редица от положителни цели числа. Да предположим, че за всяко n>Nn\gt{}N числото ana_n е равно на броя на срещанията на an−1a_{n-1} в списъка a1,a2,…,an−1a_1,a_2,\ldots,a_{n-1}. Докажете, че поне една от редиците a1,a3,a5,…a_1,a_3,a_5,\ldots и a2,a4,a6,…a_2,a_4,a_6,\ldots е периодична от някое място нататък.
РешениеИзбираме M>max⁡(a1,…,aN)M\gt{}\max(a_1,\ldots,a_N). Първо ще докажем, че някое цяло число се среща безкрайно много пъти. Ако това не беше така, в редицата щяха да се срещат произволно големи стойности. При първата поява на всяко число, по-голямо от MM, следващият член е 11, защото това число още се е срещнало точно веднъж. Така 11 би се срещало безкрайно много пъти, противоречие. Сега ще докажем, че всяко число x≥Mx\ge M се среща най-много M−1M-1 пъти. Нека, напротив, за първи път някое x≥Mx\ge M се среща за MM-ти път. Всяко срещане на xx е непосредствено след число, което дотогава вече се е срещнало x≥Mx\ge M пъти. Едно и също число не може два пъти да бъде непосредствен предшественик на xx точно при своето xx-то срещане, затова преди този момент има поне MM различни числа, срещнали се поне MM пъти. Това противоречи на избора на първия такъв момент. Следователно само краен брой числа се срещат безкрайно много пъти. Нека най-голямото от тях е kk. Понеже kk се среща безкрайно много пъти, безкрайно много числа, по-големи от MM, трябва да се срещат поне kk пъти; оттук всяко от числата 1,2,…,k−11,2,\ldots,k-1 също се среща безкрайно много пъти. От друга страна k+1k+1 не се среща безкрайно много пъти, затова има само краен брой числа, които се срещат повече от kk пъти. Нека l≥kl\ge k е най-голямото такова число. Наричаме число малко, ако е най-много kk, средно, ако е по-голямо от kk и най-много ll, и голямо, ако е по-голямо от ll. Тогава всяко малко число се среща безкрайно много пъти, а всяко голямо число се среща най-много kk пъти. Избираме достатъчно голям индекс N′>NN'\gt{}N, за който aN′a_{N'} е малко и в началния отрязък a1,…,aN′a_1,\ldots,a_{N'} са изпълнени две условия: всяко средно число вече е направило всичките си срещания, а всяко малко число се е срещнало повече от max⁡(k,N)\max(k,N) пъти. След този момент всяко малко число е последвано от голямо, защото броят на досегашните му срещания е по-голям от kk, а средни числа вече не се появяват. Всяко голямо число пък е последвано от малко, защото то се среща най-много kk пъти. Значи след aN′a_{N'} редицата се редува между малки и големи числа. Лема. Нека голямо число gg се среща след aN′a_{N'} и след него стои малкото число hh. Тогава hh е броят на малките числа, които преди този момент вече са се срещнали поне gg пъти. Доказателство. Непосредствено преди gg стои малко число, което вече се е срещнало повече от max⁡(k,N)\max(k,N) пъти, следователно g>max⁡(k,N)g\gt{}\max(k,N). За всяко малко число неговото gg-то срещане е след aNa_N и затова е последвано от gg. Понеже има точно kk малки числа, а gg се среща най-много kk пъти, числото gg се среща точно kk пъти и винаги следва след малко число. Следователно при hh-тото срещане на gg точно hh малки числа вече са достигнали поне gg срещания. За n>N′n\gt{}N' ще следим само малките числа. Нека bi(n)b_i(n) е броят на срещанията на малкото число ii сред a1,…,ana_1,\ldots,a_n, за 1≤i≤k1\le i\le k, и нека jj е последното малко число, което се е появило до момента. Когато следващото малко число се появи и е равно на jj, увеличаваме bjb_j с 11. Следващото голямо число е именно новата стойност на bjb_j. По лемата следващото малко число се определя еднозначно от относителния ред на числата b1,…,bkb_1,\ldots,b_k и е∣{i:1≤i≤k,bi≥bj}∣.\left|\{i:1\le i\le k, b_i\ge b_j\}\right|.Съществува константа CC, такава че bi+1(n)−bi(n)≤Cb_{i+1}(n)-b_i(n)\le C за всички i=1,2,…,k−1i=1,2,\ldots,k-1 и всички достатъчно големи nn. Причината е, че всяко достатъчно голямо число, което се е срещнало i+1i+1 пъти, преди това се е срещнало и ii пъти, а началният краен отрязък може да внесе само ограничена разлика. Ще видим, че разликите bi+1(n)−bi(n)b_{i+1}(n)-b_i(n) са ограничени и отдолу. Ако за някое rr разликата br+1−brb_{r+1}-b_r ставаше произволно отрицателна, в момент, в който тя току-що намалява и е по-малка от −(k−1)C-(k-1)C, щяхме да имамеmin⁡(b1,…,br)>max⁡(br+1,…,bk).\min(b_1,\ldots,b_r)\gt{}\max(b_{r+1},\ldots,b_k).Току-що увеличената стойност тогава е brb_r. От формулата за следващото малко число следва, че занапред активното малко число винаги ще е най-много rr, така че bkb_k повече няма да се увеличава. Това е невъзможно, понеже kk се среща безкрайно много пъти. Значи всички разлики bi+1−bib_{i+1}-b_i са ограничени. Следователно има само краен брой възможности за състоянието(b1−b1,b2−b1,…,bk−b1;j).(b_1-b_1,b_2-b_1,\ldots,b_k-b_1;j).Преходът към следващото такова състояние е детерминиран, защото зависи само от относителните стойности на b1,…,bkb_1,\ldots,b_k и от активното малко число jj. Затова последователността от активни малки числа е периодична от някое място нататък. След aN′a_{N'} малките и големите числа се редуват, така че малките числа стоят само на една от двете четности на индексите. Получихме, че подпоредицата на тази четност е периодична от някое място нататък. Следователно поне една от редиците a1,a3,a5,…a_1,a_3,a_5,\ldots и a2,a4,a6,…a_2,a_4,a_6,\ldots е периодична от някое място нататък.
Отвори задачатаMathNetISL 2024 C6Условие — източник

Задача N1

Пълен запис
Условие
Да се намерят всички положителни цели числа nn със следното свойство: за всеки положителен делител dd на nn е вярно, че d+1∣nd+1\mid n или d+1d+1 е просто число.
РешениеОтговорът еn∈{1,2,4,12}.n\in\{1,2,4,12\}.Лесно се проверява, че 1,2,4,121,2,4,12 удовлетворяват условието. Ще докажем, че други възможности няма. Некаn=2km,n=2^k m,където k≥0k\ge0, а mm е нечетно положително цяло число. Понеже m∣nm\mid n, от условието следва, че m+1m+1 е просто число или m+1∣nm+1\mid n. Ако m+1m+1 е просто, то това просто число е четно, следователно m+1=2m+1=2 и m=1m=1. Тогава n=2kn=2^k. Ако k≥3k\ge3, делителят 88 на nn дава 9∤n9\nmid n, а 99 не е просто число - противоречие. Значи k≤2k\le2 и получаваме n∈{1,2,4}n\in\{1,2,4\}. Остава случаят m+1∣nm+1\mid n. Тъй като gcd⁡(m,m+1)=1\gcd(m,m+1)=1, имаме m+1∣2km+1\mid 2^k, т.е.m+1=2jm+1=2^jза някое jj с 2≤j≤k2\le j\le k; случаят j=1j=1 би дал m=1m=1, вече разгледан по-горе. Значиn=2k(2j−1),2≤j≤k.n=2^k(2^j-1),\qquad 2\le j\le k.Имаме 2k∣n2^k\mid n, но 2k+1∤n2^k+1\nmid n: числото 2k+12^k+1 е нечетно, така че ако делеше nn, щеше да дели 2j−12^j-1, което е невъзможно, понеже 2k+1>2j−12^k+1\gt{}2^j-1. Следователно 2k+12^k+1 е просто число. Ако k=2k=2, то непременно j=2j=2 и получаваме n=12n=12. Нека вече k>2k\gt{}2. Тогава и 2k−1∣n2^{k-1}\mid n. Освен това 2k−1+1∤n2^{k-1}+1\nmid n: понеже е нечетно, би трябвало да дели 2j−12^j-1, но при j<kj\lt{}k това е невъзможно по големина, а при j=kj=k имаме2k−1=2(2k−1+1)−3,2^k-1=2(2^{k-1}+1)-3,така че делимост би имало само ако 2k−1+1∣32^{k-1}+1\mid3, което не става за k>2k\gt{}2. Следователно 2k−1+12^{k-1}+1 също е просто число. Но едно от числата kk и k−1k-1 е нечетно. Ако aa е нечетно, то 2a+12^a+1 се дели на 33. Затова съответното просто число 2a+12^a+1 трябва да е равно на 33, което дава a=1a=1. При k>2k\gt{}2 това е невъзможно за a=ka=k или a=k−1a=k-1. Получаваме противоречие. Следователно единствените решения са 1,2,4,121,2,4,12.
Отвори задачатаMathNetISL 2024 N1Условие — източник

Задача N2

Пълен запис
Условие
Да се определят всички крайни непразни множества SS от положителни цели числа, за които за всеки a,b∈Sa,b\in S съществува c∈Sc\in S такова, чеa∣b+2c.a\mid b+2c.
РешениеОтговорът е: точно множестватаS={t}иS={t,3t},S=\{t\}\qquad\text{и}\qquad S=\{t,3t\},където tt е произволно положително цяло число. Първо ще сведем задачата до случая, в който всички елементи са нечетни. Можем да разделим всички елементи на SS на общия им най-голям общ делител; свойството се запазва. След това не всички елементи са четни. Ако в SS имаше четен елемент aa и нечетен елемент bb, то числото b+2cb+2c щеше да е нечетно за всяко c∈Sc\in S, следователно не би могло да се дели на четното aa. Значи след това свеждане всички елементи на SS са нечетни. Едноелементните множества очевидно работят. Нека сега ∣S∣≥2|S|\ge2 и нека dd е най-големият елемент на SS. За всеки елемент e∈Se\in S, e≠de\ne d, съществува f∈Sf\in S такова, чеd∣e+2f.d\mid e+2f.Понеже dd е нечетно, това е еквивалентно наf≡d−e2(modd).f\equiv\frac{d-e}{2}\pmod d.От 0<(d−e)/2<d0\lt{}(d-e)/2\lt{}d и 0<f≤d0\lt{}f\le d получавамеf=d−e2.f=\frac{d-e}{2}.Следователно за всеки e∈S∖{d}e\in S\setminus\{d\} числото (d−e)/2(d-e)/2 също принадлежи на S∖{d}S\setminus\{d\}. Нека елементите на S∖{d}S\setminus\{d\} саe1<e2<⋯<ek.e_1\lt{}e_2\lt{}\cdots\lt{}e_k.Тогава числатаd−e12>d−e22>⋯>d−ek2\frac{d-e_1}{2}\gt{}\frac{d-e_2}{2}\gt{}\cdots\gt{}\frac{d-e_k}{2}са същите тези kk елемента, само подредени в обратен ред. Значиe1=d−ek2иek=d−e12.e_1=\frac{d-e_k}{2}\qquad\text{и}\qquad e_k=\frac{d-e_1}{2}.Оттук 2e1+ek=d=2ek+e12e_1+e_k=d=2e_k+e_1, следователно e1=eke_1=e_k. Значи k=1k=1 и d=3e1d=3e_1. В несъкратения вид това дава точно множествата {t}\{t\} и {t,3t}\{t,3t\}. Те наистина удовлетворяват условието: за {t}\{t\} е ясно, а за {t,3t}\{t,3t\} проверката на четирите двойки (a,b)(a,b) е непосредствена.
Отвори задачатаMathNetISL 2024 N2Условие — източник

Задача N3

Пълен запис
Условие
Да се определят всички редици a1,a2,…a_1,a_2,\ldots от положителни цели числа, за които за всяка двойка положителни цели числа m≤nm\le n числатаam+am+1+⋯+ann−m+1\frac{a_m+a_{m+1}+\cdots+a_n}{n-m+1}и(amam+1⋯an)1/(n−m+1)(a_m a_{m+1}\cdots a_n)^{1/(n-m+1)}са цели.
РешениеОтговорът е: точно константните редици, които очевидно работят. Ще използваме две прости наблюдения. Наричаме целочислена редица b1,b2,…b_1,b_2,\ldots добра, ако за всеки интервал средното аритметичноbm+bm+1+⋯+bnn−m+1\frac{b_m+b_{m+1}+\cdots+b_n}{n-m+1}е цяло число. Първо, ако (bi)(b_i) е добра редица, тоn−m∣bn−bmn-m\mid b_n-b_mза всички m<nm\lt{}n. Наистина, средните аритметични върху интервалите m,m+1,…,n−1m,m+1,\ldots,n-1 и m+1,m+2,…,nm+1,m+2,\ldots,n са цели, така че и двете съответни суми се делят на n−mn-m; изваждането им дава твърдението. Второ, ако добра редица приема някоя стойност bb безкрайно много пъти, то редицата е константна. Ако bn1=bn2=⋯=bb_{n_1}=b_{n_2}=\cdots=b, то за фиксирано mm числото b−bm=bnj−bmb-b_m=b_{n_j}-b_m се дели на безкрайно много различни положителни числа nj−mn_j-m, следователно е равно на 00. Условието от задачата означава, че редицата (ai)(a_i) е добра и че за всяко просто число pp редицатаνp(a1),νp(a2),…\nu_p(a_1),\nu_p(a_2),\ldotsсъщо е добра. Последното следва от това, че геометричното средно върху всеки интервал е цяло число, т.е. сумата на pp-адичните показатели върху този интервал се дели на дължината на интервала. Фиксираме просто число pp и полагаме k=νp(a1)k=\nu_p(a_1). От първото наблюдение, приложено към добрата редица (ai)(a_i), получавамеaNpk+1+1≡a1(modpk+1)a_{Np^{k+1}+1}\equiv a_1\pmod{p^{k+1}}за всяко положително цяло число NN. Следователноνp(aNpk+1+1)=k\nu_p(a_{Np^{k+1}+1})=kза безкрайно много индекси. Но редицата (νp(ai))(\nu_p(a_i)) е добра, така че по второто наблюдение тя е константна. Това е вярно за всяко просто число pp. Значи всички прости делители участват във всички членове aia_i с едни и същи показатели, т.е. редицата (ai)(a_i) е константна.
Отвори задачатаMathNetISL 2024 N3Условие — източник

Задача N4

Пълен запис
Условие
Да се определят всички положителни цели числа aa и bb, за които съществува положително цяло число gg такова, чеgcd⁡(an+b,bn+a)=g\gcd(a^n+b,b^n+a)=gза всички достатъчно големи nn.
РешениеОтговорът е единствено(a,b)=(1,1).(a,b)=(1,1).Тогава можем да вземем g=2g=2. Нека (a,b)(a,b) удовлетворява условието и нека NN е такова, чеgcd⁡(an+b,bn+a)=g(n≥N).\gcd(a^n+b,b^n+a)=g\qquad(n\ge N).Ще докажем лема: непременноg=gcd⁡(a,b)илиg=2gcd⁡(a,b).g=\gcd(a,b)\qquad\text{или}\qquad g=2\gcd(a,b).Наистина, числата aN+ba^N+b и aN+1+ba^{N+1}+b се делят на gg, затоваa(aN+b)−(aN+1+b)=b(a−1)a(a^N+b)-(a^{N+1}+b)=b(a-1)се дели на gg. Аналогично a(b−1)a(b-1) се дели на gg. Разликата им е a−ba-b, така че g∣a−bg\mid a-b. Оттук gg дели иa(b−1)+a(a−b)=a2−a.a(b-1)+a(a-b)=a^2-a.Следователно всички степени на aa са сравними с aa по модул gg, и понеже aN+b≡0(modg)a^N+b\equiv0\pmod g, получавамеa+b≡0(modg).a+b\equiv0\pmod g.Заедно с a−b≡0(modg)a-b\equiv0\pmod g това дава g∣2ag\mid2a и g∣2bg\mid2b, т.е. g∣2gcd⁡(a,b)g\mid2\gcd(a,b). Обратната делимост gcd⁡(a,b)∣g\gcd(a,b)\mid g е очевидна, понеже gcd⁡(a,b)\gcd(a,b) дели и an+ba^n+b, и bn+ab^n+a. Лемата е доказана. Нека pp е прост делител на ab+1ab+1. Тогава pp е взаимнопросто с aa и bb. Избираме n≥Nn\ge N така, чеn≡−1(modp−1).n\equiv -1\pmod{p-1}.По малката теорема на Ферма имамеan+b≡a−1+b=a−1(1+ab)≡0(modp),a^n+b\equiv a^{-1}+b=a^{-1}(1+ab)\equiv0\pmod p,и аналогично bn+a≡0(modp)b^n+a\equiv0\pmod p. Следователно p∣gp\mid g. По лемата p∣2gcd⁡(a,b)p\mid2\gcd(a,b), но pp не дели gcd⁡(a,b)\gcd(a,b); значи p=2p=2. Така всички прости делители на ab+1ab+1 са равни на 22, т.е. ab+1ab+1 е степен на 22. Оттук aa и bb са нечетни. Ако (a,b)≠(1,1)(a,b)\ne(1,1), то ab+1ab+1 се дели на 44, следователно ab≡−1(mod4)ab\equiv -1\pmod4 и a,ba,b са с различни остатъци по модул 44: единият е 11, а другият е −1-1. За всяко достатъчно голямо нечетно nn тогава имамеan+b≡bn+a≡0(mod4),a^n+b\equiv b^n+a\equiv0\pmod4,така че 4∣g4\mid g. Това противоречи на лемата, защото gcd⁡(a,b)\gcd(a,b) е нечетно и следователно 2gcd⁡(a,b)2\gcd(a,b) не се дели на 44. Остава само (a,b)=(1,1)(a,b)=(1,1), както твърдяхме.
Отвори задачатаMathNetISL 2024 N4Условие — източник

Задача N5

Пълен запис
Условие
Нека SS е крайно непразно множество от прости числа. Нека1=b1<b2<⋯1=b_1\lt{}b_2\lt{}\cdotsе редицата от всички положителни цели числа, чиито прости делители принадлежат на SS. Докажете, че за всички освен краен брой положителни цели числа nn съществуват положителни цели числа a1,a2,…,ana_1,a_2,\ldots,a_n, за коитоa1b1+a2b2+⋯+anbn=\frac{a_1}{b_1}+\frac{a_2}{b_2}+\cdots+\frac{a_n}{b_n}=⌈1b1+1b2+⋯+1bn⌉.\left\lceil\frac1{b_1}+\frac1{b_2}+\cdots+\frac1{b_n}\right\rceil.
РешениеАко SS има само един елемент, да кажем S={p}S=\{p\}, тогава bi=pi−1b_i=p^{i-1}. За всяко достатъчно голямо nn имаме⌈∑i=1n1bi⌉=2.\left\lceil\sum_{i=1}^n\frac1{b_i}\right\rceil=2.Избираме a1=a2=⋯=an−1=1a_1=a_2=\cdots=a_{n-1}=1 иan=pn−1−(p+p2+⋯+pn−2),a_n=p^{n-1}-(p+p^2+\cdots+p^{n-2}),което е положително за достатъчно голямо nn. Тогава сумата е точно 22. Занапред нека ∣S∣≥2|S|\ge2. Пълната сума на реципрочните стойности е∑i=1∞1bi=\sum_{i=1}^{\infty}\frac1{b_i}=∏p∈S(1+1p+1p2+⋯ )=∏p∈Spp−1.\prod_{p\in S}\left(1+\frac1p+\frac1{p^2}+\cdots\right)=\prod_{p\in S}\frac p{p-1}.Следователно за достатъчно голямо nn таванът на частичната сума е равен на⌈∏p∈Spp−1⌉.\left\lceil\prod_{p\in S}\frac p{p-1}\right\rceil.Първо разглеждаме специалния случай S={2,3}S=\{2,3\}. Тогава горното произведение е 33. Некаai={1,2bi≤bn,2,2bi>bn.a_i=\begin{cases}1,&2b_i\le b_n,\\2,&2b_i\gt{}b_n. \end{cases}Ако фиксираме t≥0t\ge0 и съберем членовете с ν3(bi)=t\nu_3(b_i)=t, получаваме принос 2/3t2/3^t, когато 3t≤bn3^t\le b_n, и принос 00 иначе. Следователно∑i=1naibi=\sum_{i=1}^n\frac{a_i}{b_i}=∑t≥03t≤bn23t=3−13T,\begin{aligned}\sum_{\substack{t\ge0\\3^t\le b_n}}\frac2{3^t}=3-\frac1{3^T},\end{aligned}където TT е най-голямото цяло число с 3T≤bn3^T\le b_n. Ако увеличим с 11 коефициента aja_j при онзи индекс jj, за който bj=3Tb_j=3^T, сумата нараства с 1/3T1/3^T и става равна на 33. Остава случаят, в който S≠{2,3}S\ne\{2,3\}. Тогава числотоP=∏p∈Spp−1P=\prod_{p\in S}\frac p{p-1}не е цяло: ако ∣S∣>2|S|\gt{}2, в знаменателя остава поне един множител 22 след всички съкращения; ако ∣S∣=2|S|=2 и 2∉S2\notin S, в знаменателя остава множител 22; а ако S={2,p}S=\{2,p\}, то P=2p/(p−1)P=2p/(p-1) не е цяло за p>3p\gt{}3. Затоваα=⌈P⌉−P>0.\alpha=\lceil P\rceil-P\gt{}0.За всяко достатъчно голямо nn имаме⌈∑i=1n1bi⌉−∑i=1n1bi>α.\left\lceil\sum_{i=1}^n\frac1{b_i}\right\rceil-\sum_{i=1}^n\frac1{b_i}\gt{}\alpha.Ще използваме следното твърдение. Нека nn е достатъчно голямо, а за всяко p∈Sp\in S нека epe_p е най-голямото неотрицателно цяло число с pep≤bnp^{e_p}\le b_n. НекаM=∏p∈Spep.M=\prod_{p\in S}p^{e_p}.Ако uu е положително цяло число и u/M>αu/M\gt{}\alpha, то съществуват неотрицателни цели числа xix_i, за които∑i=1nxibi=uM.\sum_{i=1}^n\frac{x_i}{b_i}=\frac uM.Това твърдение завършва доказателството: прилагаме го заuM=⌈∑i=1n1bi⌉−∑i=1n1bi,\frac uM=\left\lceil\sum_{i=1}^n\frac1{b_i}\right\rceil-\sum_{i=1}^n\frac1{b_i},след което полагаме ai=xi+1a_i=x_i+1. Остава да докажем твърдението. Избираме цяло число c>0c\gt{}0, за което∑p∈Sp−c<α,\sum_{p\in S}p^{-c}\lt{}\alpha,и вземаме nn толкова голямо, че pc≤bnp^c\le b_n за всяко p∈Sp\in S; тогава pc∣Mp^c\mid M. За всяко p∈Sp\in S нека ipi_p е индексът с bip=pepb_{i_p}=p^{e_p}. Избираме най-малкото неотрицателно цяло число xipx_{i_p}, за коетоpep−c∣xipMpep−u.p^{e_p-c}\mid x_{i_p}\frac{M}{p^{e_p}}-u.Такова число съществува и може да се избере по-малко от pep−cp^{e_p-c}, понеже M/pepM/p^{e_p} е взаимнопросто с pp. Приносът на всички тези избрани членове е по-малък от∑p∈Spep−cpep=∑p∈Sp−c<α.\sum_{p\in S}\frac{p^{e_p-c}}{p^{e_p}}=\sum_{p\in S}p^{-c}\lt{}\alpha.Затова разликатаuM−∑p∈Sxippep\frac uM-\sum_{p\in S}\frac{x_{i_p}}{p^{e_p}}е неотрицателна. Освен това по избора на xipx_{i_p} тя има видаr∏p∈Spc\frac r{\prod_{p\in S}p^c}за някое неотрицателно цяло число rr. Накрая избираме индекс jj сbj=∏p∈Spcb_j=\prod_{p\in S}p^cи полагаме xj=rx_j=r; всички останали неизбрани xix_i са 00. Това доказва твърдението и задачата.
Отвори задачатаMathNetISL 2024 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека nn е положително цяло число. Ще казваме, че полином PP с цели коефициенти е nn-добър, ако съществува полином QQ от степен 22 с цели коефициенти такъв, чеQ(k)(P(k)+Q(k))Q(k)(P(k)+Q(k))никога не се дели на nn за никое цяло число kk. Да се определят всички положителни цели числа nn, за които всеки полином с цели коефициенти е nn-добър.
РешениеОтговорът е: точно всичкиn>2.n\gt{}2.За n=1n=1 никой полином не е 11-добър. За n=2n=2 полиномът P(X)=1P(X)=1 не е 22-добър, защото Q(X)(Q(X)+1)Q(X)(Q(X)+1) винаги е четно число. Ще докажем обратното за всички n>2n\gt{}2. Ако един полином PP е dd-добър и d∣nd\mid n, то същият избор на QQ показва, че PP е nn-добър: число, което не се дели на dd, не може да се дели на nn. Затова е достатъчно да докажем твърдението за d=4d=4 и за нечетно просто d=pd=p, понеже всяко n>2n\gt{}2 има такъв делител. Първо нека d=4d=4. По модул 22 всяка полиномна функция е от видаP(X)≡aX+b(mod2),P(X)\equiv aX+b\pmod2,където a,b∈{0,1}a,b\in\{0,1\}. Ако a=0a=0, вземамеQ(X)=4X2+b+1,Q(X)=4X^2+b+1,а ако a=1a=1, вземамеQ(X)=X2+b+1.Q(X)=X^2+b+1.И в двата случая Q(X)Q(X) никога не се дели на 44, а Q(X)+P(X)Q(X)+P(X) винаги е нечетно. Следователно PP е 44-добър. Остава случаят, в който pp е нечетно просто число. Достатъчно е да докажем следното твърдение: за всяка функция ff върху остатъците по модул pp съществува квадратичен полином QQ, който няма корени по модул pp и за койтоQ(x)≠f(x)(modp)Q(x)\ne f(x)\pmod pза всеки остатък xx. Тогава прилагаме твърдението към f=−Pf=-P. Да допуснем противното и да изберем функция ff, за която всеки квадратичен полином без корени по модул pp съвпада с ff поне в една точка. Можем да предполагаме, че ff никъде не е 00: ако f(u)=0f(u)=0, заменяме само тази стойност с 11; понеже разглежданите QQ нямат корени, всяко съвпадение с първоначалната ff става в точка, различна от uu. Ако някой ненулев остатък tt не е стойност на ff, полиномътQ(X)=pX2+tQ(X)=pX^2+tняма корени по модул pp и никъде не съвпада с ff, противоречие. Значи ff приема всички ненулеви остатъци. Понеже има pp аргумента и само p−1p-1 такива стойности, съществуват различни x1,x2x_1,x_2 с f(x1)=f(x2)f(x_1)=f(x_2). Чрез обратима линейна смяна на променливата можем да предполагаме, чеf(1)=f(−1).f(1)=f(-1).Нека r1r_1 е квадратичен неостатък по модул pp. Избираме y≠0y\ne0 така, чеf(y)=(1−r1)f(0),f(y)=(1-r_1)f(0),което е възможно, защото дясната страна е ненулев остатък. Полагамеr=y2r1;r=\frac{y^2}{r_1};тогава rr също е квадратичен неостатък. Разглеждаме функциятаφ(X)=f(X)X2−r\varphi(X)=\frac{f(X)}{X^2-r}по модул pp. Знаменателят никога не е 00. Имаме φ(1)=φ(−1)\varphi(1)=\varphi(-1) и, от избора на rr и yy, също φ(0)=φ(y)\varphi(0)=\varphi(y). Следователно образът на φ\varphi има най-много p−2p-2 стойности. Избираме ненулев остатък AA, който не е стойност на φ\varphi. ТогаваQ(X)=A(X2−r)Q(X)=A(X^2-r)няма корени по модул pp, защото rr е квадратичен неостатък, и никъде не е сравним с f(X)f(X) по модул pp, защото A≠φ(X)A\ne\varphi(X) за всеки XX. Това е противоречие. Следователно всеки полином е pp-добър за всяко нечетно просто pp, а заедно със случая 44 получаваме точно всички n>2n\gt{}2.
Отвори задачатаMathNetISL 2024 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа. Нека f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0} е функция със следното свойство: за m,n∈Z>0m,n\in\mathbb Z_{\gt{}0} равенствотоf(mn)2=f(m2)f(f(n))f(mf(n))f(mn)^2=f\left(m^2\right)f(f(n))f(mf(n))е изпълнено тогава и само тогава, когато mm и nn са взаимно прости. За всяко положително цяло число nn определете всички възможни стойности на f(n)f(n).
РешениеОтговорът е: възможните стойности на f(n)f(n) са точно положителните цели числа, които имат същите прости делители като nn. Еквивалентно, ако простите делители на nn са p1,…,pkp_1,\ldots,p_k, то f(n)f(n) може да бъде всяко число от видаp1e1p2e2⋯pkek,e1,…,ek≥1.p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},\qquad e_1,\ldots,e_k\ge1.Нека P(m,n)P(m,n) означава условието от задачата за двойката (m,n)(m,n). От P(1,1)P(1,1) имамеf(1)2=f(1)f(f(1))2,f(1)^2=f(1)f(f(1))^2,следователно f(1)=f(f(1))2f(1)=f(f(1))^2. От P(1,f(1))P(1,f(1)) получавамеf(f(1))2=f(1)f(f(f(1)))2,f(f(1))^2=f(1)f(f(f(1)))^2,така че f(f(f(1)))=1f(f(f(1)))=1. Накрая P(1,f(f(1)))P(1,f(f(1))) дава 1=f(1)31=f(1)^3, откъдето f(1)=1f(1)=1. От P(1,n)P(1,n) следваf(n)2=f(f(n))2,f(n)^2=f(f(n))^2,тоестf(n)=f(f(n))(1)f(n)=f(f(n))\tag{1}за всяко nn. От P(m,1)P(m,1) следваf(m)2=f(m2)f(m),f(m)^2=f(m^2)f(m),тоестf(m)=f(m2)(2)f(m)=f(m^2)\tag{2}за всяко mm. С помощта на (1) и (2) условието от задачата се свежда до следното твърдение:f(mn)2=f(m)f(n)f(mf(n))(Q(m,n))f(mn)^2=f(m)f(n)f(mf(n))\tag{Q(m,n)}тогава и само тогава, когато mm и nn са взаимно прости. От Q(m,f(n))Q(m,f(n)) получаваме ощеf(mf(n))=f(m)f(n)(R(m,n))f(mf(n))=f(m)f(n)\tag{R(m,n)}тогава и само тогава, когато mm и f(n)f(n) са взаимно прости. Твърдение 1. Ако f(a)=1f(a)=1, то a=1a=1. Наистина, ако a≠1a\ne1, то aa и aa не са взаимно прости, така че равенството Q(a,a)Q(a,a) не трябва да е вярно. Но при f(a)=1f(a)=1 и (2) двете му страни са равни на 11, противоречие. Твърдение 2. Ако n≠1n\ne1, то gcd⁡(n,f(n))≠1\gcd(n,f(n))\ne1. Да допуснем противното. От Q(f(n),n)Q(f(n),n) имамеf(nf(n))2=f(n)3,f(nf(n))^2=f(n)^3,а от Q(n,f(n))Q(n,f(n)) имамеf(nf(n))2=f(n)2f(nf(n)).f(nf(n))^2=f(n)^2f(nf(n)).Тези две равенства дават f(n)=1f(n)=1, което противоречи на твърдение 1. Твърдение 3. За всяко nn е изпълнено rad⁡(n)∣f(n)\operatorname{rad}(n)\mid f(n), където rad⁡(n)\operatorname{rad}(n) е произведението на различните прости делители на nn. Нека p∣np\mid n и нека n=pvn′n=p^v n', където p∤n′p\nmid n'. От Q(pv,n′)Q(p^v,n') получавамеf(n)2=f(pv)f(n′)f(pvf(n′)).f(n)^2=f(p^v)f(n')f(p^v f(n')).По твърдение 2 числата pvp^v и f(pv)f(p^v) не са взаимно прости, следователно p∣f(pv)p\mid f(p^v). Затова p∣f(n)p\mid f(n). Твърдение 4. Ако nn е взаимно просто с f(k)f(k), то f(n)f(n) също е взаимно просто с f(k)f(k). От Q(f(k),n)Q(f(k),n) и от R(n,k)R(n,k) получавамеf(k)f(n)=f(f(k)f(n)).f(k)f(n)=f(f(k)f(n)).Тогава равенството R(f(n),k)R(f(n),k) показва, че f(n)f(n) и f(k)f(k) са взаимно прости. Твърдение 5. Ако pp е просто число, то f(p)f(p) е степен на pp. По твърдение 3 имаме p∣f(p)p\mid f(p). Да допуснем, че друго просто число q≠pq\ne p също дели f(p)f(p). Ако за някое положително цяло число NN имаме p∤f(N)p\nmid f(N), тогава f(p)f(p) е взаимно просто с f(N)f(N); в частност q∤f(N)q\nmid f(N), а от твърдение 3 следва q∤Nq\nmid N. Значи от q∣Nq\mid N следва p∣f(N)p\mid f(N); в частност p∣f(q)p\mid f(q). Аналогично от p∣Np\mid N следва q∣f(N)q\mid f(N). Заедно с твърдение 3 получаваме: ако NN не е взаимно просто с pqpq, то pq∣f(N)pq\mid f(N). Некаs=min⁡{vp(f(x)):gcd⁡(x,pq)>1},s=\min\{v_p(f(x)):\gcd(x,pq)\gt{}1\},и изберем XX с gcd⁡(X,pq)>1\gcd(X,pq)\gt{}1 и vp(f(X))=sv_p(f(X))=s. По горното s≥1s\ge1. Записвамеf(X)=psqtX′,f(X)=p^s q^t X',където t≥1t\ge1 и p∤X′p\nmid X', q∤X′q\nmid X'. От (1) имамеf(psqtX′)=psqtX′.f(p^s q^t X')=p^s q^t X'.Прилагаме Q(ps,qtX′)Q(p^s,q^tX'). Лявата страна има pp-адична оценка 2s2s, а дясната страна се дели на p3sp^{3s} по минималността на ss. Това е невъзможно. Следователно f(p)f(p) няма прост делител, различен от pp, и твърдението е доказано. Твърдение 6. За всяко nn имамеrad⁡(f(n))=rad⁡(n).\operatorname{rad}(f(n))=\operatorname{rad}(n).Вече знаем, че rad⁡(n)∣f(n)\operatorname{rad}(n)\mid f(n). Нека pp е просто число и p∤np\nmid n. По твърдение 5 числото f(p)f(p) е степен на pp, така че nn е взаимно просто с f(p)f(p). От твърдение 4 следва, че f(n)f(n) е взаимно просто с f(p)f(p), т.е. p∤f(n)p\nmid f(n). Значи f(n)f(n) има точно същите прости делители като nn. Остава да покажем, че всички такива стойности наистина могат да се получат. Нека за всяко просто число pp е избран положителен показател e(p)≥1e(p)\ge1 и дефинирамеf(n)=∏p∣npe(p),f(n)=\prod_{p\mid n}p^{e(p)},като празното произведение за n=1n=1 е 11. Тогава f(n)f(n) има точно същите прости делители като nn. Освен това f(m2)=f(m)f(m^2)=f(m) и f(f(n))=f(n)f(f(n))=f(n), а проверката по прости делители показва, чеf(mn)2=f(m)f(n)f(mf(n))f(mn)^2=f(m)f(n)f(mf(n))е вярно точно когато mm и nn нямат общ прост делител. Следователно тези функции удовлетворяват условието, което завършва доказателството.
Отвори задачатаMathNetISL 2024 N7Условие — източник