Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4552. feladat (2013. szeptember)

B. 4552. Ebben a mondatban az 1 alkalommal előforduló számok száma a1, a 2 alkalommal előforduló számok száma a2, ..., a 2013 alkalommal előforduló számok száma a2013. Adjuk meg az a1,a2,...,a2013 számokat úgy, hogy igaz állítást kapjunk. Hányféleképpen tehetjük ezt meg?

Javasolta: Kozma László (Saarbrücken, Németország)

(5 pont)

A beküldési határidő 2013. október 10-én LEJÁRT.


Megoldás. A könnyebb megfogalmazhatóság érdekében vezessük be a \(\displaystyle b_i=i\) jelölést (\(\displaystyle 1\leqslant i \leqslant 2013\)), amellyel a feladat úgy szól, hogy a \(\displaystyle b_1\) alkalommal előforduló számok száma \(\displaystyle a_1\), a \(\displaystyle b_2\) alkalommal előforduló számok száma \(\displaystyle a_2\) stb. Ha \(\displaystyle a_n=1\), akkor - mivel minden \(\displaystyle b_i\) különböző - van egy olyan \(\displaystyle k\) szám, amely a mondatban (vagyis az \(\displaystyle a_i\)-k és \(\displaystyle b_i\)-k között összesen) \(\displaystyle n\)-szer fordul elő, így az \(\displaystyle a_i\)-k között pontosan \(\displaystyle n-1\) db \(\displaystyle k\) van - kivéve, ha \(\displaystyle k=0\), akkor pontosan \(\displaystyle n\), mivel a \(\displaystyle b_i\)-k között nincs nulla. Ha \(\displaystyle a_{\ell}=m\), ahol \(\displaystyle m\) pozitív egész, akkor ahhoz, hogy a mondat igaz legyen, léteznie kell \(\displaystyle m\) különböző számnak, amelyek mindegyike legalább \(\displaystyle \ell -1\)-szer fordul elő az \(\displaystyle a_i\)-k között. Tudjuk azt is, hogy a megfelelő \(\displaystyle b_i\) és \(\displaystyle a_i\) számok szorzatainak összege pontosan 4026, hiszen a mondatban összesen ennyi szám szerepel. Bontsuk esetekre a feladatot aszerint, hogy az \(\displaystyle a_i\) számok között pontosan hány nulla van.

1. eset: Pontosan 2008 darab nulla van. Ekkor \(\displaystyle a_{2008}\) értéke legalább 1. Van ezen felül négy olyan \(\displaystyle a_i\) szám, amelyek értéke nem nulla, legyenek ezek \(\displaystyle a_c\), \(\displaystyle a_d\), \(\displaystyle a_e\) és \(\displaystyle a_f\), értékeik \(\displaystyle p\), \(\displaystyle q\), \(\displaystyle r\) és \(\displaystyle s\) -- ahol \(\displaystyle p,q,r,s \ge 1\). Van tehát az \(\displaystyle a_i\)-k között legalább \(\displaystyle p(c-1)+q(d-1)+r(e-1)+s(f-1)\) olyan szám, ami nem nulla. Ez legalább \(\displaystyle 1\cdot (1-1)+1\cdot(2-1)+1\cdot(3-1)+1\cdot(4-1)=6\) darab szám, mivel \(\displaystyle c\), \(\displaystyle d\), \(\displaystyle e\), \(\displaystyle 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 \(\displaystyle a_j\) számhoz egy hatodikat -- legyen ez \(\displaystyle a_g\); így az öt legkisebb \(\displaystyle i\) közül, amire az \(\displaystyle 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 \(\displaystyle a_i\) számok száma több, mint 1-gyel növekedett, legalább \(\displaystyle (5-1)\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 \(\displaystyle 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 \(\displaystyle a_i\) nulla, azaz nincs olyan szám, ami \(\displaystyle 1, 2, \ldots, 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 \(\displaystyle a_i\ne 0\) érték az \(\displaystyle a_{2012}= k\ge 1\), vagyis az összesen \(\displaystyle k\)-féle előforduló szám mindegyikének pontosan 2012-szer kellene szerepelnie, ezért \(\displaystyle 2012\cdot k=4026\), ami ellentmondás.

5. eset: Pontosan 2011 nulla van. Ekkor \(\displaystyle 1\le a_{2011}=k\le 2\), és egyetlen \(\displaystyle {i \ne 2011}\) indexre \(\displaystyle a_i\ne 0\); ez nyilván az \(\displaystyle a_1\), sőt \(\displaystyle a_1\ge 2010\). Így \(\displaystyle 4026=2011\cdot k+1\cdot a_1\) miatt \(\displaystyle {k=1}\). Eszerint azonban az 1 éppen kétszer fordul elő, tehát \(\displaystyle a_2\ne 0\), ami ellentmondás.

6. eset: Pontosan 2010 nulla van. Az előbbi esethez hasonlóan \(\displaystyle a_{2010}=1\) és \(\displaystyle a_1 \ne 0\). Nem létezhet további olyan \(\displaystyle a_t\), \(\displaystyle t\ge 5\) szám, ami nem 0, hiszen akkor van legalább \(\displaystyle 5-1\) olyan \(\displaystyle a_i\), ami nem 0. Ha \(\displaystyle a_3\) és \(\displaystyle a_4\) egyike sem 0, vagy az egyik 0, a másik viszont 1-nél több, akkor legalább \(\displaystyle 2\cdot(3-1)\) olyan \(\displaystyle a_i\) van, ami nem 0. Ha \(\displaystyle a_4=1\), akkor \(\displaystyle a_1=1\), ami nem lehet, mivel legalább 2010 olyan szám van, ami pontosan 1-szer szerepel, hiszen van 2010 db egyenlő \(\displaystyle a_i\). Ha \(\displaystyle a_3=1\), akkor \(\displaystyle a_1=u\), ahol \(\displaystyle 2013\ge u\ge 2010\), így \(\displaystyle u\) éppen kétszer szerepel, tehát \(\displaystyle a_2\) nem 0. Itt már csak az az eset maradt, ha \(\displaystyle a_1\), \(\displaystyle a_2\) és \(\displaystyle a_{2010}\) nem nulla, ekkor \(\displaystyle 1\cdot a_1+2\cdot a_2+a_{2010}\cdot 1=4026\). Tehát \(\displaystyle a_1\cdot 1+a_2\cdot 2=2016\). Itt \(\displaystyle a_2=1\) nem lehet, ekkor \(\displaystyle a_1=2014\), \(\displaystyle a_2=2\) esetén \(\displaystyle a_1=2012\), ez nem lehet, mivel 2-es és 1-es számból is több van, mint 1. Viszont \(\displaystyle a_2=3\) és \(\displaystyle 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 \(\displaystyle a_{2009}=1\). Az előbbi megfontolást követve a második legnagyobb \(\displaystyle a_i\) nem lehet 5-nél több. Pontosan öt sem lehet, mert ekkor -- mivel \(\displaystyle a_1\ge 2009\) -- az \(\displaystyle a_ib_i\) szorzatösszeg legalább

\(\displaystyle 1\cdot 2009 +2\cdot 1+3\cdot 1+5\cdot 1+2009\cdot 1 \)

lesz, ami túl sok. Ha a második legnagyobb \(\displaystyle a_i=4\), akkor a szorzatösszeg legalább \(\displaystyle 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 \(\displaystyle a_1=2009\), \(\displaystyle a_2=1\), \(\displaystyle a_4=1\) és \(\displaystyle 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 \(\displaystyle a_i\) a 3, akkor a szorzatösszeg \(\displaystyle a_1=2009\), \(\displaystyle a_2=1\), \(\displaystyle {a_3=2}\) és \(\displaystyle a_{2009}=1\), illetve \(\displaystyle a_1=2010\), \(\displaystyle a_2=2\), \(\displaystyle a_3=1\) és \(\displaystyle a_{2009}=1\)-gyel tehető igazzá. Ebből csak az utóbbi helyes megoldás. Ha \(\displaystyle a_1=2011\), akkor \(\displaystyle a_2=1\), \(\displaystyle a_3=1\), ami ellentmondás, mivel túl sok az 1-es. Nyilván 2011-nél több sem lehet az \(\displaystyle a_1\).

Ezzel végignéztük az összes esetet, tehát az állítást háromféleképpen tehetjük igazzá.

Leipold Péter (Budapest, Jedlik Ányos Gimnázium, 12. évf.)


Statisztika:

50 dolgozat érkezett.
5 pontot kapott:Asztalos Bogdán, Balogh Tamás, Bereczki Zoltán, Csépai András, Fekete Panna, Khayouti Sára, Kovács 972 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 Loránd Ottó, Williams Kada.
3 pontot kapott:8 versenyző.
2 pontot kapott:5 versenyző.
1 pontot kapott:11 versenyző.
0 pontot kapott:8 versenyző.

A KöMaL 2013. szeptemberi matematika feladatai