Feladat:	2015. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Fehér Zsombor
Füzet:	2015/október, 393 - 395. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Egyenlőtlenségek, Számhalmazok
Hivatkozás(ok):	Feladatok: 2015/szeptember: 2015. évi Nemzetközi Matematika Diákolimpia 23. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Fehér Zsombor megoldása. Legyen $c_j=a_j+j$. Ekkor az $\left(i\right)$ feltétel azt mondja ki, hogy $j+1\le c_j\le j+2015$, a $\left(ii\right)$ feltétel pedig azt, hogy a $c_j$ számok mind különbözőek. Megmutatjuk, hogy a $c_1\mathrm{,}{c}_2\mathrm{,}\text{...}$ sorozat véges sok kivétellel minden pozitív egész számot felvesz. Tegyük fel ugyanis, hogy legalább 2016-ot nem vesz fel, és legyen $t$ egy olyan pozitív egész, ami nagyobb ennél a 2016 számnál. Ekkor az $\left(i\right)$ feltétel alapján a $\left\{c_1\mathrm{,}{c}_2\mathrm{,}\text{...}\mathrm{,}{c}_t\right\}$ halmaz minden eleme az $\left[\mathrm{1,}t+2015\right]$ intervallumba esik, és mivel $\left(ii\right)$ szerint $t$ különböző elemről van szó, ezért ebből az intervallumból $\left\{c_1\mathrm{,}{c}_2\mathrm{,}\text{...}\mathrm{,}{c}_t\right\}$ éppen 2015 pozitív egész számot nem vesz fel. Azonban feltevésünk szerint az ennél bővebb $\left\{c_1\mathrm{,}{c}_2\mathrm{,}\text{...}\right\}$ halmaz legalább 2016 darab $t$-nél kisebb pozitív egész számot nem vesz fel, ami pedig ellentmondás. A feladatnak megfelelő $b$ számot válasszuk meg annyinak, amennyi a $c_1\mathrm{,}{c}_2\mathrm{,}\text{...}$ sorozat által fel nem vett pozitív egészek száma, $N$ pedig legyen egy olyan szám, ami nagyobb ennél a $b$ darab kimaradó számnál. A fenti gondolatmenetből az is látható, hogy $b\le 2015$. Az $m$, $n$ pozitív egészekre a továbbiakban feltesszük, hogy $N\le m<n$. A feladatunk lényegében az, hogy egy $\sum a_j$ kifejezést megfelelő korlátok közé szorítsunk, ami nyilván ugyanaz, mint $\sum c_j$ megfelelő korlátok közé szorítása. Tudjuk, hogy $\left\{c_{m+1}\mathrm{,}\text{...}\mathrm{,}{c}_n\right\}$ minden eleme az $\left[m+\mathrm{2,}n+2015\right]$ intervallumba esik, és mivel ezen intervallum $n-m+2014$ egész számából $n-m$ van az előző halmazban, ezért 2014 egész szám marad ki. Vizsgáljuk meg közelebbről ezt a 2014 számot: ki fog derülni, hogy közülük $b-1$ darab az $\left[m+\mathrm{2,}n+2015\right]$ intervallum ,,elején'', $2015-b$ pedig a ,,végén'' helyezkedik el. Mivel a $\left\{c_1\mathrm{,}{c}_2\mathrm{,}\text{...}\right\}$ halmaz $b$ darab egész számot nem vesz fel az $\left[\mathrm{1,}\infty \right)$ intervallumból, ezért a $\left\{c_{m+1}\mathrm{,}{c}_{m+2}\mathrm{,}\text{...}\right\}$ halmaz $b+m$ számot nem vesz fel $\left[\mathrm{1,}\infty \right)$-ből. Ez $c_j>j$ alapján azt jelenti, hogy a $\left\{c_{m+1}\mathrm{,}{c}_{m+2}\mathrm{,}\text{...}\right\}$ halmaz $b-1$ számot nem vesz fel $\left[m+\mathrm{2,}\infty \right)$-ből. Mivel azonban $m+2>N$, ezért ezen $b-1$ számot is felveszi valahol a $c_1\mathrm{,}{c}_2\mathrm{,}\text{...}$ sorozat, csak még $c_{m+1}$ előtt. Így ez a $b-1$ szám mindegyike olyan $c_k$, melyre $k\le m$, így $c_k\le k+2015\le m+2015$ alapján ezek a számok mind az $\left[m+\mathrm{2,}m+2015\right]$ intervallumba esnek. Tehát azon 2014 egész közül, melyek az $\left[m+\mathrm{2,}n+2015\right]$ intervallumban benne vannak, de a $\left\{c_{m+1}\mathrm{,}\text{...}\mathrm{,}{c}_n\right\}$ halmazban nem, $b-1$ darab az $\left\{c_1\mathrm{,}\text{...}\mathrm{,}{c}_m\right\}$ halmazban van, a maradék $2015-b$ darab pedig szükségképpen a $\left\{c_{n+1}\mathrm{,}\text{...}\right\}$ halmazban. Ezen $2015-b$ szám mindegyike legalább $n+2$, így ezek az $\left[n+\mathrm{2,}n+2015\right]$ intervallumba esnek. Ezen a ponton álljunk meg egy pillanatra, és vegyük észre, hogy a feladat megoldásával lényegében készen vagyunk. Csak az alapján, hogy a 2014 kimaradó szám valahol az $\left[m+\mathrm{2,}n+2015\right]$ intervallumban van, még nem tudnánk pontos becslést mondani, hiszen $m\mathrm{,}n$-et kicsivel megváltoztatva az egyik kimaradó szám szabadon ,,átugorhatna'' az intervallum elejéről a végére, ezzel nagy ($n-m$ nagyságrendű) változást eredményezve. De azáltal, hogy a 2014 kimaradó szám közül mindig $b-1$ van az intervallum elején, és $2015-b$ a végén (ahol a $b$ egy univerzális paramétere a sorozatnak!), ilyen ugrások nem történhetnek meg, csak az intervallum szélein lévő rövid (2014 hosszú) intervallumok belsejében mozoghatnak a kimaradó számok. Így lehetséges az, hogy $m$, $n$-től független, ${1007}^2$ nagyságrendű becslést fogunk tudni mondani. Nem maradt más hátra, minthogy kiszámoljuk a 2014 kimaradó szám összegének lehetséges legkisebb és legnagyobb értékét, majd ezt visszavezessük a feladatbeli összegre. Tudjuk, hogy a 2014 szám felbontható valahogy egy $b-1$ és egy $2015-b$ elemű csoportra, melyek elemei rendre az $\left[m+\mathrm{2,}m+2015\right]$, illetve az $\left[n+\mathrm{2,}n+2015\right]$ intervallumból valók. (Előfordulhat, hogy ez a két intervallum átfedi egymást, de ez nem okoz gondot.) Mivel a számok különbözőek, ezért a 2014 szám összege legalább ${\displaystyle \begin{array}{c}\hfill {\displaystyle \left(\left(m+2\right)+\left(m+3\right)+\cdots +\left(m+b\right)\right)+}\hfill \\ \hfill {\displaystyle +\left(\left(n+2\right)+\left(n+3\right)+\cdots +\left(n+2016-b\right)\right)=}\hfill \\ \hfill {\displaystyle =\frac{\left(b-1\right)\left(2m+b+2\right)}{2}+\frac{\left(2015-b\right)\left(2n+2018-b\right)}{2}=h_{\underset{}{\overset{}{\text{min}}}}\mathrm{,}}\hfill \end{array}}$ legfeljebb pedig ${\displaystyle \begin{array}{c}\hfill {\displaystyle \left(\left(m+2017-b\right)+\cdots +\left(m+2015\right)\right)+\left(\left(n+b+1\right)+\cdots +\left(n+2015\right)\right)=}\hfill \\ \hfill {\displaystyle =\frac{\left(b-1\right)\left(2m+4032-b\right)}{2}+\frac{\left(2015-b\right)\left(2n+2016+b\right)}{2}=h_{\underset{}{\overset{}{\text{max}}}}\mathrm{.}}\hfill \end{array}}$ Ha $H$ jelöli az előbbi 2014 kimaradó szám összegét, akkor a feladatban szereplő összeg így írható: ${\displaystyle \begin{array}{c}\hfill {\displaystyle {\sum }_{j=m+1}^n\left(a_j-b\right)={\sum }_{j=m+1}^n\left(c_j-j-b\right)={\sum }_{i=m+2}^{n+2015}i-H-{\sum }_{j=m+1}^{n}j-{\sum }_{j=m+1}^{n}b=}\hfill \\ \hfill {\displaystyle =\frac{\left(n+2014-m\right)\left(n+m+2017\right)}{2}-H-\frac{\left(n-m\right)\left(n+m+1\right)}{2}-b\left(n-m\right)\mathrm{.}}\hfill \end{array}}$ A $h_{\underset{}{\overset{}{\text{min}}}}\le H\le h_{\underset{}{\overset{}{\text{max}}}}$ becslést alkalmazva, a kifejezések egyszerűsítése után végül a következőt kapjuk: $\begin{array}{c}{\displaystyle b^2-2016b+2015\le \sum _{j=m+1}^n\left(a_j-b\right)\le -b^2+2016b-2015.}\end{array}$ Így tehát valóban, $\begin{array}{c}{\displaystyle \left|\sum _{j=m+1}^n\left(a_j-b\right)\right|\le -b^2+2016b-2015={1007}^2-{\left(b-1008\right)}^2\le {1007}^2\mathrm{.}}\end{array}$