Problem B. 5332. (September 2023)
B. 5332. What may be the positive integer \(\displaystyle n\) if any sequence of \(\displaystyle 2^n\) consecutive positive integers contains a term that can be represented as a sum of the \(\displaystyle n\)th powers of at most \(\displaystyle n\) non-negative integers?
Proposed by P.\(\displaystyle \,\)P. Pach, Budapest
(6 pont)
Deadline expired on October 10, 2023.
Sorry, the solution is available only in Hungarian. Google translation
1. megoldás. Legyen \(\displaystyle t\) pozitív egész szám, és vizsgáljuk, hogy \(\displaystyle 1\)-től \(\displaystyle t^n\)-ig hány szám állhat elő \(\displaystyle n\) nemnegatív egész szám \(\displaystyle n\)-edik hatványának összegeként. A kérdéses számok \(\displaystyle a_1^n+a_2^n+\dots+a_n^n\) alakban írhatók fel, ahol \(\displaystyle 0\leq a_1,~a_2,~\dots,~a_n\) egész szám mindegyike legfeljebb \(\displaystyle t\), hiszen különben \(\displaystyle t^n\)-nél nagyobb összeget kapnánk. Az \(\displaystyle a_1,a_2,\dots,a_n\) számokat tehát a \(\displaystyle \{0,1,\dots,t\}\) közül választhatjuk, nem kell különbözőknek lenniük, azonban pontosan ugyanazt az \(\displaystyle n\) számot választva (más sorrendben) nem kapunk újabb összeget. Így a kívánt alakban előálló számok számát felülről becsüli, hogy \(\displaystyle t+1\) elem közül hányféleképpen választhatunk \(\displaystyle n\)-et ismétléses kombinációval, vagyis \(\displaystyle \binom{t+n}{n}\).
Ha bármely \(\displaystyle 2^n\) egymást követő pozitív egész szám közül legalább egy felírható, akkor
\(\displaystyle \left \lfloor \frac{t^n}{2^n} \right \rfloor \leq \binom{t+n}{n},\)
hiszen \(\displaystyle \{1,2,\dots,t^n\}\)-en belül kiválasztható \(\displaystyle \left \lfloor \frac{t^n}{2^n} \right \rfloor\) darab \(\displaystyle 2^n\) hosszú blokk. Itt valójában az egész rész elhagyható, hiszen a \(\displaystyle \binom{t+n}{n}\)-féle kiválasztás egyike 0-t ad, amit itt nem számolunk. Tehát
\(\displaystyle \frac{t^n}{2^n}\leq \binom{t+n}{n}=\frac{(t+n)(t+n-1)\dots (t+1)}{n!},\)
és így
\(\displaystyle \frac{n!}{2^n}\leq \left(1+\frac{n}{t}\right)\left(1+\frac{n-1}{t}\right)\dots \left(1+\frac{1}{t}\right)\)
teljesül minden \(\displaystyle t\)-re. Ha \(\displaystyle t\)-t kellően nagynak választjuk (\(\displaystyle n\) függvényében), akkor a jobb oldal tetszőlegesen közel lesz (felülről) az 1-hez (\(\displaystyle t\to \infty\) esetén a jobb oldal 1-hez tart), ami csak olyan \(\displaystyle n\)-ek mellett lehetséges, melyekre \(\displaystyle \frac{n!}{2^n}\leq 1\).
Ha \(\displaystyle n=4\), akkor \(\displaystyle \frac{4!}{2^4}=\frac{24}{16}>1\), nagyobb \(\displaystyle n\)-ekre pedig egyre nagyobb értékeket kapunk, hiszen
\(\displaystyle \frac{(n+1)!}{2^{n+1}}=\frac{n!}{2^{n}}\cdot\frac{n+1}{2}>\frac{n!}{2^{n}},\)
ha \(\displaystyle n>1\).
Az eddigiekből következik, hogy \(\displaystyle n\) értéke csak 1, 2 vagy 3 lehet.
Ha \(\displaystyle n=1\), akkor a feltétel triviálisan teljesül.
Ha \(\displaystyle n=2\), akkor a \(\displaystyle 21\), \(\displaystyle 22\), \(\displaystyle 23\), \(\displaystyle 24\) számok ellenpéldát adnak: egyik sem írható fel két nemnegatív egész szám négyzetének összegeként. Ugyanis csak a \(\displaystyle 0\), \(\displaystyle 1\), \(\displaystyle 4\), \(\displaystyle 9\), \(\displaystyle 16\) használható (25 már túl nagy), \(\displaystyle 9+9\) még túl kicsi, ezért a 16-ot mindenképpen használni kell, azonban \(\displaystyle 16+4=20\) túl kicsi, \(\displaystyle 16+9=25\) pedig már túl nagy.
Ha \(\displaystyle n=3\), akkor a \(\displaystyle 44\), \(\displaystyle 45\), \(\displaystyle \dots\), \(\displaystyle 51\) számok ellenpéldát adnak: egyik sem írható fel három nemnegatív egész szám köbének összegeként. Ugyanis csak a \(\displaystyle 0\), \(\displaystyle 1\), \(\displaystyle 8\), \(\displaystyle 27\) használható (64 már túl nagy), \(\displaystyle 8+8+27=43\) még túl kicsi, ezért a 27-et mindenképpen használni kell, kétszer is, azonban \(\displaystyle 27+27=54\) már túl nagy.
Tehát a feltétel pontosan akkor teljesül, ha \(\displaystyle n=1\).
2. megoldás. Az \(\displaystyle n=1,~2\) eseteket nem tárgyaljuk újra, \(\displaystyle n\geq 3\)-ra mutatunk egy másik lehetséges indoklást.
Az előző megoldásban szereplő \(\displaystyle n=3\) esetén adott konstrukció általánosítható az \(\displaystyle n>3\) esetekre is. Megmutatjuk ugyanis, hogy \(\displaystyle n\geq 3\) esetén a \(\displaystyle 3^n+(n-1)2^n+1,~ \dots,~ 2\cdot3^n-1\) számok egyike sem áll elő \(\displaystyle n\) darab nemnegatív \(\displaystyle n\)-edik hatvány összegeként, számuk viszont nagyobb, mint \(\displaystyle 2^n\).
Először azt igazoljuk, hogy nem állnak elő \(\displaystyle n\) darab nemnegatív \(\displaystyle n\)-edik hatvány összegeként. Ha \(\displaystyle n\geq 3\), akkor \(\displaystyle 2\cdot 3^n-1<4^n\), ugyanis \(\displaystyle 4^n=64\cdot 4^{n-3}\geq 64\cdot 3^{n-3}>54\cdot 3^{n-3}=2\cdot 3^n\). Tehát az előállításban \(\displaystyle 4^n\) (és a nagyobb \(\displaystyle n\)-edik hatványok) már nem használható(k), vagyis mindegyik összeadandó a \(\displaystyle 0\), \(\displaystyle 1\), \(\displaystyle 2^n\), \(\displaystyle 3^n\) számok közül kerül ki. Világos, hogy a \(\displaystyle 3^n\) nem használható kétszer, viszont így a legnagyobb összeg, amit kaphatunk \(\displaystyle 3^n+(n-1)2^n\), ami túl kicsi. Tehát ezek a számok valóban nem állnak elő a kívánt alakban.
A megadott számok száma \(\displaystyle 3^n-(n-1)2^n\), azt kell belátnunk, hogy ez legalább \(\displaystyle 2^n\), vagyis, hogy \(\displaystyle n\cdot 2^n\leq 3^n\). Az egyenlőtlenség \(\displaystyle n=1,~2\) esetén teljesül, ha pedig \(\displaystyle n\geq 2\) értékét \(\displaystyle (n+1)\)-re növeljük, akkor a jobb oldal pontosan 3-szorosára változik, a bal oldal pedig legfeljebb 3-szorosára, hiszen \(\displaystyle \frac{n+1}{n}\cdot 2\leq \left(1+\frac12\right)\cdot2=3\). Ezzel beláttuk, hogy a megadott számok száma legalább \(\displaystyle 2^n\), vagyis \(\displaystyle n\) értéke valóban nem lehet legalább 3.
Statistics:
66 students sent a solution. 6 points: Anay Aggarwal, Anudeep Prashanth, Aravin Peter, Bodor Mátyás, Csonka Illés, Diaconescu Tashi, Erdélyi Kata, Farkas 005 Bendegúz, Fórizs Emma, Gömze Norken, Görömbey Tamás, Gyenes Károly, Holló Martin, Juhász-Molnár Erik, Keresztély Zsófia, Klement Tamás, Kovács Benedek Noel, Kővágó Edit Gréta, Molnár István Ádám, Op Den Kelder Ábel, Pálfi András, Sági Mihály, Szakács Ábel, Török Eszter Júlia, Vigh 279 Zalán, Virág Lénárd Dániel, Virág Rudolf, Virág Tóbiás, Zhai Yu Fan. 5 points: Bernhardt Dávid, Elias Simon, Fekete Aron, Horák Zsófia, Licsik Zsófia, Lincoln Liu, Sárdinecz Dóra, Schäffer Donát, Szabó 721 Sámuel, Szabó 810 Levente, Szabó Imre Bence, Szemlér Bálint, Teveli Jakab, Tömböly 299 Áron, Veres Dorottya, Vödrös Dániel László. 4 points: 5 students. 3 points: 3 students. 2 points: 5 students. 1 point: 2 students. 0 point: 5 students.
Problems in Mathematics of KöMaL, September 2023