Feladat:	B.4552	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Asztalos Bogdán ,  Balogh Tamás ,  Bereczki Zoltán ,  Csépai András ,  Fekete Panna ,  Khayouti Sára ,  Kovács Márton ,  Leipold Péter ,  Leitereg Miklós ,  Maga Balázs ,  Mócsy Miklós ,  Nagy Kartal ,  Nagy-György Pál ,  Simkó Irén ,  Szécsi Adél Lilla ,  Talyigás Gergely ,  Viharos Lóránd Ottó ,  Williams Kada
Füzet:	2014/április, 208 - 209. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Logikai feladatok, Esetvizsgálat, Indirekt bizonyítási mód
Hivatkozás(ok):	Feladatok: 2013/szeptember: B.4552

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.   Megoldás. A könnyebb megfogalmazhatóság érdekében vezessük be a $b_i=i$ jelölést ($1⩽i⩽2013$), amellyel a feladat úgy szól, hogy a $b_1$ alkalommal előforduló számok száma $a_1$, a $b_2$ alkalommal előforduló számok száma $a_2$ stb. Ha $a_n=1$, akkor ‐ mivel minden $b_i$ különböző ‐ van egy olyan $k$ szám, amely a mondatban (vagyis az $a_i$-k és $b_i$-k között összesen) $n$-szer fordul elő, így az $a_i$-k között pontosan $n-1$ db $k$ van ‐ kivéve, ha $k=0$, akkor pontosan $n$, mivel a $b_i$-k között nincs nulla. Ha $a_{\ell }=m$, ahol $m$ pozitív egész, akkor ahhoz, hogy a mondat igaz legyen, léteznie kell $m$ különböző számnak, amelyek mindegyike legalább $\ell -1$-szer fordul elő az $a_i$-k között. Tudjuk azt is, hogy a megfelelő $b_i$ és $a_i$ számok szorzatainak összege pontosan 4026, hiszen a mondatban összesen ennyi szám szerepel. Bontsuk esetekre a feladatot aszerint, hogy az $a_i$ számok között pontosan hány nulla van. 1. eset: Pontosan 2008 darab nulla van. Ekkor $a_{2008}$ értéke legalább 1. Van ezen felül négy olyan $a_i$ szám, amelyek értéke nem nulla, legyenek ezek $a_c$, $a_d$, $a_e$ és $a_f$, értékeik $p$, $q$, $r$ és $s$ ‐ ahol $p\mathrm{,}q\mathrm{,}r\mathrm{,}s\ge 1$. Van tehát az $a_i$-k között legalább $p\left(c-1\right)+q\left(d-1\right)+r\left(e-1\right)+s\left(f-1\right)$ olyan szám, ami nem nulla. Ez legalább $1\cdot \left(1-1\right)+1\cdot \left(2-1\right)+1\cdot \left(3-1\right)+1\cdot \left(4-1\right)=6$ darab szám, mivel $c$, $d$, $e$, $f$ különbözők. Ellentmondásra jutottunk, nem lehet ilyen megoldás. 2. eset: Kevesebb, mint 2008 darab nulla van. Ekkor hozzávehetünk az előbbi öt nem nulla $a_j$ számhoz egy hatodikat ‐ legyen ez $a_g$; így az öt legkisebb $i$ közül, amire az $a_i$-k nem nullák, a legnagyobb legalább 5 lesz, mivel különböznek egymástól. Tehát a nem nulla $a_i$ számok száma több, mint 1-gyel növekedett, legalább $\left(5-1\right)\cdot 1$-gyel. Ezt a gondolatmenetet követve kiderül, hogy ha egyesével csökkentjük a nullák számát, akkor a nem nulla $a_i$-k száma több, mint egyesével nő, azaz a feladatnak nincs ilyen megoldása sem. 3. eset: Pontosan 2013 nulla van. Ez nyilvánvalóan nem lehet, hiszen ez azt jelentené, hogy minden $a_i$ nulla, azaz nincs olyan szám, ami $\mathrm{1,2,}\text{...}\mathrm{,2013}$ alkalommal fordulna elő; ekkor a mondatban minden előforduló számnak legalább 2014-szer kellene szerepelnie. A nullára viszont ez nem teljesülne. 4. eset: Pontosan 2012 nulla van. Ekkor az egyetlen $a_i\ne 0$ érték az $a_{2012}=k\ge 1$, vagyis az összesen $k$-féle előforduló szám mindegyikének pontosan 2012-szer kellene szerepelnie, ezért $2012\cdot k=4026$, ami ellentmondás. 5. eset: Pontosan 2011 nulla van. Ekkor $1\le a_{2011}=k\le 2$, és egyetlen $i\ne 2011$ indexre $a_i\ne 0$; ez nyilván az $a_1$, sőt $a_1\ge 2010$. Így $4026=2011\cdot k+1\cdot a_1$ miatt $k=1$. Eszerint azonban az 1 éppen kétszer fordul elő, tehát $a_2\ne 0$, ami ellentmondás. 6. eset: Pontosan 2010 nulla van. Az előbbi esethez hasonlóan $a_{2010}=1$ és $a_1\ne 0$. Nem létezhet további olyan $a_t$, $t\ge 5$ szám, ami nem 0, hiszen akkor van legalább $5-1$ olyan $a_i$, ami nem 0. Ha $a_3$ és $a_4$ egyike sem 0, vagy az egyik 0, a másik viszont 1-nél több, akkor legalább $2\cdot \left(3-1\right)$ olyan $a_i$ van, ami nem 0. Ha $a_4=1$, akkor $a_1=1$, ami nem lehet, mivel legalább 2010 olyan szám van, ami pontosan 1-szer szerepel, hiszen van 2010 db egyenlő $a_i$. Ha $a_3=1$, akkor $a_1=u$, ahol $2013\ge u\ge 2010$, így $u$ éppen kétszer szerepel, tehát $a_2$ nem 0. Itt már csak az az eset maradt, ha $a_1$, $a_2$ és $a_{2010}$ nem nulla, ekkor $1\cdot a_1+2\cdot a_2+a_{2010}\cdot 1=4026$. Tehát $a_1\cdot 1+a_2\cdot 2=2016$. Itt $a_2=1$ nem lehet, ekkor $a_1=2014$, $a_2=2$ esetén $a_1=2012$, ez nem lehet, mivel 2-es és 1-es számból is több van, mint 1. Viszont $a_2=3$ és $a_1=2010$ jó megoldás. Ekkor a 0 van 2010-szer, a 2010, az 1 és a 3 kétszer, a többi (2010 db) szám pedig egyszer. 7. eset: Pontosan 2009 nulla van. Ezúttal $a_{2009}=1$. Az előbbi megfontolást követve a második legnagyobb $a_i$ nem lehet 5-nél több. Pontosan öt sem lehet, mert ekkor ‐ mivel $a_1\ge 2009$ ‐ az $a_i{b}_i$ szorzatösszeg legalább $\begin{array}{c}{\displaystyle 1\cdot 2009+2\cdot 1+3\cdot 1+5\cdot 1+2009\cdot 1}\end{array}$ lesz, ami túl sok. Ha a második legnagyobb $a_i=4$, akkor a szorzatösszeg legalább $1\cdot 2009+2\cdot 1+4\cdot 1+2009\cdot 1=4026$ lesz, ez éppen jó, és ez a minimum csak akkor érhető el, ha $a_1=2009$, $a_2=1$, $a_4=1$ és $a_{2009}=1$. Ekkor az 1 négyszer, a 2009 kétszer, a 0 2009-szer, a többi szám pedig egyszer fordul elő, ez jó megoldás. Ha a második legnagyobb $a_i$ a 3, akkor a szorzatösszeg $a_1=2009$, $a_2=1$, $a_3=2$ és $a_{2009}=1$, illetve $a_1=2010$, $a_2=2$, $a_3=1$ és $a_{2009}=1$-gyel tehető igazzá. Ebből csak az utóbbi helyes megoldás. Ha $a_1=2011$, akkor $a_2=1$, $a_3=1$, ami ellentmondás, mivel túl sok az 1-es. Nyilván 2011-nél több sem lehet az $a_1$. Ezzel végignéztük az összes esetet, tehát az állítást háromféleképpen tehetjük igazzá.