Problem B. 5045. (September 2019)

B. 5045. For which positive integers \(\displaystyle n\) is there an appropriate order \(\displaystyle a_1,a_2,\dots,a_n\) of the first \(\displaystyle n\) positive integers such that the numbers \(\displaystyle a_1+1,a_2+2,\dots,a_n+n\) are all perfect powers? (A number is called a perfect power if it can be represented in the form \(\displaystyle a^b\), where \(\displaystyle a, b\ge 2\) are integers.)

(6 pont)

Deadline expired on October 10, 2019.

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

Megoldás. Megmutatjuk, hogy pontosan akkor létezik megfelelő sorrend, ha \(\displaystyle n\geq 3\).

Ha \(\displaystyle n\in \{1,2\}\), akkor \(\displaystyle a_1+1\leq 3\), és így nem lehet teljes hatvány, hiszen a legkisebb teljes hatvány a 4.

A továbbiakban \(\displaystyle n\)-re vonatkozó teljes indukcióval igazoljuk, hogy \(\displaystyle n\geq 3\) esetén létezik megfelelő sorrend, aminél mind az \(\displaystyle n\) összeg teljes hatvány.

Ha \(\displaystyle n=3\), akkor \(\displaystyle 3+1,2+2,1+3\) megfelelő.

Ha \(\displaystyle n=4\), akkor \(\displaystyle 3+1,2+2,1+3,4+4\) megfelelő.

Ha \(\displaystyle n=5\), akkor \(\displaystyle 3+1,2+2,1+3,5+4,4+5\) megfelelő.

Ha \(\displaystyle n=6\), akkor \(\displaystyle 3+1,6+2,1+3,5+4,4+5,2+6\) megfelelő.

Ha \(\displaystyle n=7\), akkor \(\displaystyle 7+1,6+2,5+3,4+4,3+5,2+6,1+7\) megfelelő.

Most tegyük fel, hogy \(\displaystyle 3, 4,\dots,n-1\) szám esetén már megmutattuk megfelelő sorrend létezését, és célunk \(\displaystyle n\)-re is igazolni az állítást. Ha az \(\displaystyle [n+4,2n]\) intervallum tartalmaz teljes hatványt (amit jelöljünk \(\displaystyle t\)-vel), akkor legyen \(\displaystyle t-n\leq i\leq n\)-re \(\displaystyle a_i=t-i\), ekkor az összes ilyen \(\displaystyle i\)-re \(\displaystyle a_i+i=t\) valóban teljes hatvány. Az indukciós feltevést (\(\displaystyle t-n-1\))-re alkalmazva kapjuk, hogy \(\displaystyle a_1,a_2,\dots,a_{t-n-1}\) is megválasztható megfelelően, hiszen fent éppen a \(\displaystyle (t-n-1)\)-nél nagyobb számokat állítottuk párba a \(\displaystyle (t-n-1)\)-nél nagyobb számokkal, vagyis \(\displaystyle a_1,a_2,\dots,a_{t-n-1}\) éppen az \(\displaystyle 1,2,\dots,t-n-1\) számok egy permutációja kell legyen. (Megjegyezzük, hogy \(\displaystyle 3\leq t-n-1 \leq n-1\), így az indukciós feltevést valóban alkalmazhatjuk.)

Végül belátjuk, hogy ha \(\displaystyle n\geq 8\), akkor az \(\displaystyle [n+4,2n]\) intervallum tartalmaz teljes hatványt. Ha \(\displaystyle n\in\{8,9,10,11,12\}\), akkor a 16, ha pedig \(\displaystyle n\in\{13,14,\dots,21\}\), akkor a 25 az intervallumban található teljes hatvány. Ha \(\displaystyle n\geq 22\), akkor

\(\displaystyle \sqrt{2n}-\sqrt{n+4}\geq \sqrt{2n}-\sqrt{\frac{26}{22}n} \geq \left(\sqrt{2}-\sqrt{\frac{26}{22}} \right)\sqrt{n}\geq \left(\sqrt{2}-\sqrt{\frac{26}{22}} \right)\sqrt{22}=\sqrt{44}-\sqrt{26}>1,\)

ezért a \(\displaystyle [\sqrt{n+4},\sqrt{2n}]\) intervallum tartalmaz egész számot, és így az \(\displaystyle [n+4,2n]\) intervallumban van négyzetszám. Ezzel tehát igazoltuk az indukciós lépést, innen teljes indukcióval következik, hogy valóban minden \(\displaystyle n\geq 3\) esetén van megfelelő sorrend.

Statistics:

61 students sent a solution.
6 points:	Bán-Szabó Áron, Baski Bence, Beke Csongor, Bencsik Ádám, Bognár 171 András Károly, Czett Mátyás, Egyházi Hanna, Fleiner Zsigmond, Flódung Áron , Füredi Erik Benjámin, Geretovszky Anna, Gyetvai Miklós, Győrffy Johanna, Hámori Janka, Hegedűs Dániel, Hervay Bence, Kercsó-Molnár Anita, Kerekes Boldizsár, Koszta Benedek, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Nagy Nándor, Nguyen Bich Diep, Noszály Áron, Seres-Szabó Márton, Szabó 991 Kornél, Terjék András József.
5 points:	Bursics András, Fekete Richárd, Kitschner Bernadett, Kovács 129 Tamás, Németh Márton, Osztényi József, Velich Nóra, Világi Áron.
4 points:	5 students.
3 points:	5 students.
2 points:	2 students.
1 point:	3 students.
0 point:	10 students.

Problems in Mathematics of KöMaL, September 2019