Problem B. 4552. (September 2013)

B. 4552. In this sentence, the number of numbers occurring once is a₁, the number of numbers occurring twice is a₂, ..., and the number of numbers occurring 2013 times is a₂₀₁₃. Determine the values of $a_1, a_2, \ldots, a_{2013}$ such that the resulting statement is true. In how many different ways can that be done?

Suggested by L. Kozma, Saarbrücken, Germany

(5 pont)

Deadline expired on October 10, 2013.

Sorry, the solution is available only in Hungarian. Google translation

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.)

Statistics:

50 students sent a solution.

5 points: 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 points: 8 students.

2 points: 5 students.

1 point: 11 students.

0 point: 8 students.

Problems in Mathematics of KöMaL, September 2013

50 students sent a solution.
5 points:	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 points:	8 students.
2 points:	5 students.
1 point:	11 students.
0 point:	8 students.

Already signed up?
New to KöMaL?