A B. 5045. feladat (2019. szeptember)

B. 5045. Mely pozitív egész \(\displaystyle n\) számok esetén van az első \(\displaystyle n\) pozitív egész számnak olyan \(\displaystyle a_1,a_2,\dots,a_n\) sorrendje, hogy az \(\displaystyle a_1+1,a_2+2,\dots,a_n+n\) számok mind teljes hatványok? (Egy számot teljes hatványnak nevezünk, ha előáll \(\displaystyle a^b\) alakban, ahol \(\displaystyle a, b\ge 2\) egész számok.)

(6 pont)

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

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.

Statisztika:

61 dolgozat érkezett.
6 pontot kapott:	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 pontot kapott:	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 pontot kapott:	5 versenyző.
3 pontot kapott:	5 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	10 versenyző.

A KöMaL 2019. szeptemberi matematika feladatai