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