Problem A. 674. (September 2016)
A. 674. Let \(\displaystyle a_1, \ldots, a_n>1\) be integers satisfying the inequality
\(\displaystyle \sum_{i=1}^{n} \frac{1}{a_{i}+1} \le \frac{7}{12}. \)
Every year, the government of Optimistica publishes its Annual Report with \(\displaystyle n\) economic indicators. For each \(\displaystyle i=1,\ldots,n\), the possible values of the \(\displaystyle i\)-th indicator are \(\displaystyle 1, 2, \ldots, a_i\). The Annual Report is said to be optimistic if at least \(\displaystyle n - 1\) indicators have higher values than in the previous report. Prove that the government can publish optimistic Annual Reports in an infinitely long sequence.
Based on the problem of the 1st International Olympiad of Metropolises
(5 pont)
Deadline expired on October 10, 2016.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
5 students sent a solution. 5 points: Williams Kada. 4 points: Matolcsi Dávid. 2 points: 2 students. 0 point: 1 student.
Problems in Mathematics of KöMaL, September 2016