 |
Az A. 674. feladat (2016. szeptember) |
A. 674. Legyenek \(\displaystyle a_1, \ldots, a_n>1\) olyan egészek, amelyekre teljesül a
\(\displaystyle \sum_{i=1}^{n} \frac{1}{a_{i}+1} \le \frac{7}{12} \)
egyenlőtlenség. Optimisztika kormánya minden évben kiad egy Éves jelentést \(\displaystyle n\) gazdasági mutatóval. Minden egyes \(\displaystyle i=1,\ldots,n\)-re az \(\displaystyle i\)-edik mutató lehetséges értékei \(\displaystyle 1, 2, \ldots, a_i\). Azt mondjuk, hogy az Éves jelentés optimista, ha legalább \(\displaystyle n-1\) mutatónak az értéke magasabb, mint a megelőző jelentésben. Bizonyítsuk be, hogy a kormány ki tudja adni az optimista Éves jelentések egy végtelen sorozatát.
Az 1. International Olympiad of Metropolises feladata nyomán
(5 pont)
A beküldési határidő 2016. október 10-én LEJÁRT.
Megoldás. A feladat állítása következik a következő két tényből:
1. állítás: Léteznek olyan \(\displaystyle d_1,\ldots,d_n\) pozitív egészek, amelyekre \(\displaystyle d_i\le a_i\) minden \(\displaystyle i\)-re, bármelyik \(\displaystyle d_i\) és \(\displaystyle d_j\) közül az egyik osztója a másiknak, és \(\displaystyle \sum_{i=1}^n\frac1{d_i}\le1\).
2. állítás: Ha \(\displaystyle d_1,\ldots,d_n\) pozitív egészek, bármelyik \(\displaystyle d_i\) és \(\displaystyle d_j\) közül az egyik osztója a másiknak, és \(\displaystyle \sum_{i=1}^n\frac1{d_i}\le1\), akkor léteznek páronként diszjunkt, mindkét irányban végtelen \(\displaystyle S_1,\ldots,S_n\) számtani sorozatok úgy, hogy \(\displaystyle S_i\) differenciája \(\displaystyle d_i\) mindegyik \(\displaystyle 1\le i\le n\) indexre.
A optimisztikai kormány egy lehetséges stratégiája: Vegyünk az 1–2. állításoknak megfelelő \(\displaystyle S_1,\ldots,S_n\) számtani sorozatokat.
– Legyen kezdetben mindegyik mutató (indikátor) értéke \(\displaystyle 1\).
– Minden egyes év végén, ha az aktuális évszám eleme az \(\displaystyle S_i\) sorozatnak, akkor az \(\displaystyle i\)-edik indikátor értéke álljon vissza \(\displaystyle 1\)-re.
– A többi indikátor értéke nőjön \(\displaystyle 1\)-gyel.
Mivel az \(\displaystyle S_1,\ldots,S_n\) sorozatok diszjunktak, az aktuális évszám mindig csak legfeljebb egyetlen \(\displaystyle S_i\) sorozatnak lehet eleme, így legfeljebb az az egy indikátor nem nő. Továbbá, minden \(\displaystyle 1\le i\le n\)-re, az \(\displaystyle i\)-edik indikátor értéke egymás után legfeljebb \(\displaystyle (d_i-1)\)-szer nő, majd visszaáll \(\displaystyle 1\)-re, így soha nem lép \(\displaystyle d_i\le a_i\) fölé.
A 2. állítás bizonyítása: Ki kell választanunk egy-egy, rendre modulo \(\displaystyle d_1,\ldots,d_n\) maradékosztályt úgy, hogy ezek diszjunktak legyenek. Ezt egyesével, a differenciák szerint növekvő sorrendben tesszük meg. Az általánosság csorbulása nélkül feltehetjük, hogy \(\displaystyle d_1\le d_2\le\ldots\le d_n\).
Az első, modulo \(\displaystyle d_1\) maradékosztályt, azaz \(\displaystyle S_1\)-et tetszőlegesen kijelölhetjük. Tegyük fel, hogy már kiválaszottuk az \(\displaystyle S_1,\ldots,S_{k-1}\) osztályokat, és ezekhez szeretnénk találni egy alkalmas \(\displaystyle S_k\) osztályt. Mivel \(\displaystyle d_1,\ldots,d_{k-1}\) mind osztója \(\displaystyle d_k\)-nak, a korábban már kijelölt osztályokat szétbonthatjuk modulo \(\displaystyle d_k\) maradékosztályokra; a már felhasznált modulo \(\displaystyle d_k\) maradkosztáyok száma összesen \(\displaystyle \frac{d_k}{d_1}+\ldots+\frac{d_k}{d_{k-1}}\). Mivel \(\displaystyle \frac{d_k}{d_1}+\ldots+\frac{d_k}{d_{k-1}}<d_k\sum_{i=1}^n\frac1{d_i}\le d_k\), az összesen \(\displaystyle d_k\) darab modulo \(\displaystyle d_k\) osztály között léteznie kell legalább egy olyannak, amit még nem használtunk fel; az egyik ilyet választhatkjuk \(\displaystyle S_k\)-nak. Ezt minden \(\displaystyle k=2,\ldots,n\)-re megismételve, kijelölhetjük a kívánt \(\displaystyle S_1,\ldots,S_n\) osztályokat.
Az 1. állítás bizonyítása: Kétféle stratégiával fogunk próbálkozni: vagy az összes \(\displaystyle a_i\)-t kicseréljük egy nála nem nagyobb \(\displaystyle 2\)-hatványra, vagy pedig az összes \(\displaystyle a_i\)-t kicseréljük egy-egy \(\displaystyle 2\)-hatvány \(\displaystyle 3\)-szorosára. Utóbbi nem lehetséges akkor, ha \(\displaystyle a_1=2\), ezért ezt az esetet külön megvizsgáljuk.
1. eset: \(\displaystyle a_1=2\). A feltétel szerint \(\displaystyle \sum_{i=2}^{n} \frac{1}{a_{i}+1} \le \frac{7}{12} - \frac1{a_1+1} = \frac{7}{12} - \frac13 = \frac14\).
Legyen mindegyik \(\displaystyle 1\le i\le n\) indexre \(\displaystyle K_i\) az utolsó, \(\displaystyle a_i\)-nél nem nagyobb \(\displaystyle 2\)-hatvány. Az \(\displaystyle i=1\) esetben \(\displaystyle K_1=2\). A következő kettőhatvány, \(\displaystyle 2K_i\) már nagyobb, mint \(\displaystyle a_i\), tehát \(\displaystyle 2K_i\ge a_i+1\). Ezt a becslést csak \(\displaystyle i\ge2\)-re alkalmazzuk, mert tudjuk, hogy \(\displaystyle K_1=2\):
\(\displaystyle \sum_{i=1}^n \frac1{K_1} = \frac1{K_1} + 2\sum_{i=2}^n \frac1{2K_i} \le \frac12 + 2\sum_{i=2}^n \frac1{a_i+1} \le \frac12 + 2\cdot \frac14 = 1. \)
Az 1. állítás szerint a \(\displaystyle d_i=K_i\) választás megfelelő.
2. eset: \(\displaystyle a_1\ge3\).
Legyen ismét mindegyik \(\displaystyle i\) indexre \(\displaystyle K_i\) az utolsó, \(\displaystyle a_i\)-nél nem nagyobb \(\displaystyle 2\)-hatvány, és legyen \(\displaystyle H_i\) az utolsó, \(\displaystyle a_i\)-nél nem nagyobb, \(\displaystyle 3\cdot2^k\) alakú szám. Elég azt igazolni, hogy \(\displaystyle \sum_{i=1}^n\frac1{K_i}\le1\) és \(\displaystyle \sum_{i=1}^n\frac1{H_i}\le1\) közül legalábbis az egyik igaz; az 1. állítás miatt az előbbi esetben \(\displaystyle d_i=K_i\), az utóbbi esetben \(\displaystyle d_i=H_i\) jó választás.
Ha \(\displaystyle H_i<K_i\), akkor \(\displaystyle H_i<K_i\le a_i<2H_i\). Ebből láthatjuk, hogy \(\displaystyle a_i+1 \le 2H_i = \frac32 K_i\). A becslés reciprokát írjuk fel kétféleképpen:
\(\displaystyle \frac1{a_i+1} \ge \frac{2/3}{K_i} \tag{1.1} \)
\(\displaystyle \frac1{a_i+1} \ge \frac{1/2}{H_i} \tag{1.2} \)
Ha \(\displaystyle K_i<H_i\), akkor \(\displaystyle K_i<H_i\le a_i<2K_i\); ebből \(\displaystyle a_i+1 \le 2K_i = \frac43 H_i\). A becslés reciproka kétféleképpen:
\(\displaystyle \frac1{a_i+1} \ge \frac{1/2}{K_i} \tag{2.1} \)
\(\displaystyle \frac1{a_i+1} \ge \frac{3/4}{H_i} \tag{2.2} \)
A következő lépésben az (1.1) és (1.2) becsléseknek, illetve a (2.1) és (2.2) becsléseknek is felírjuk egy-egy konvex kombinációját úgy, hogy a két esetben ugyanazt a becslést kapjuk. Ha valamilyen \(\displaystyle 0\le p,q\le1\) számokkal az (1.1) egyenlőtlenség \(\displaystyle p\)-szereséhez hozzáadjuk a (1.2) \(\displaystyle (1-p)\)-szeresét, illetve ha a (2.1) \(\displaystyle q\)-szorosához hozzáadjuk a (2.2) \(\displaystyle (1-q)\)-szorosát, a következőket kapjuk:
\(\displaystyle \frac1{a_i+1} \ge p \cdot \frac{2/3}{K_i} + (1-p) \cdot \frac{1/2}{H_i}, \quad\text{illetve}\quad \frac1{a_i+1} \ge q \cdot \frac{1/2}{K_i} + (1-q) \cdot \frac{3/4}{H_i}. \)
Ha \(\displaystyle H_i<K_i\), akkor az első becslés érvényes, ha pedig \(\displaystyle H_i>K_i\), akkor a második. A két egyenlőtlenség akkor egyezik meg, ha \(\displaystyle \frac23p=\frac12q\) és \(\displaystyle \frac12(1-p)=\frac34(1-q)\). Ez egy lineáris egyenletrendszer, amelynek megoldása \(\displaystyle p=\frac12\), \(\displaystyle q=\frac23\). Belyettesítve,
\(\displaystyle \frac1{a_i+1} \ge \frac{1/3}{K_i} + \frac{1/4}{H_i}, \tag3 \)
és ez most már független attól, hogy \(\displaystyle K_i\) és \(\displaystyle H_i\) közül melyik a nagyobb.
Az \(\displaystyle i\) szerint összegezve (3)-at,
\(\displaystyle \frac13+\frac14 = \frac7{12} \ge \sum_{i=1}^{n} \frac{1}{a_{i}+1} \ge \sum_{i=1}^{n} \left(\frac{1/3}{K_i} + \frac{1/4}{H_i}\right) = \frac13\sum_{i=1}^{n} \frac1{K_i} + \frac14\sum_{i=1}^{n} \frac1{H_i}, \)
\(\displaystyle \frac13\left( 1 - \sum_{i=1}^{n} \frac1{K_i} \right) + \frac14\left( 1 - \sum_{i=1}^{n} \frac1{H_i} \right) \ge 0, \)
ami csak úgy lehetséges, ha \(\displaystyle \sum_{i=1}^{n} \frac1{K_i}\le1\) vagy \(\displaystyle \sum_{i=1}^{n} \frac1{H_i}\le1\).
Ezzel az 1. állítást is igazoltuk.
Megjegyzés. Könnyű meggondolni, hogy ha \(\displaystyle a_1=2\) és \(\displaystyle a_2=3\), akkor mindegyik évben csökennie kell az első két indikátor valamelyikének. Emiatt nem lehetséges további indikátor hozzáadása.
Statisztika:
5 dolgozat érkezett. 5 pontot kapott: Williams Kada. 4 pontot kapott: Matolcsi Dávid. 2 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2016. szeptemberi matematika feladatai