 |
A B. 5220. feladat (2022. január) |
B. 5220. Legyen \(\displaystyle n\) pozitív egész szám. Mutassuk meg, hogy megadható \(\displaystyle 1\)-től \(\displaystyle 2^{n+2}\)-ig \(\displaystyle n\) négyzetszám úgy, hogy közülük akárhány különbözőt összeadva (beleértve az egytagú összegeket és az összes szám összegét is) csupa különböző számot kapjunk. (Lásd Freud Róbert cikkét a 2. oldalon.)
Javasolta: Freud Róbert (Budapest)
(6 pont)
A beküldési határidő 2022. február 10-én LEJÁRT.
Megoldás. Tekintsük a következő eljárást: minden lépésben válasszuk ki a legkisebb négyzetszámot úgy, hogy a megadott feltétel – miszerint a részhalmaz összegek mind különbözők – érvényes maradjon, a kiválasztott négyzetszámok sorozata legyen \(\displaystyle a_1,a_2,\dots\) Ekkor tehát \(\displaystyle a_1=1,a_2=4,a_3=9,a_4=16\), majd ezután \(\displaystyle a_5=36\), mert \(\displaystyle 16+9=25\) miatt a 25 már nem választható ki. Ezzel egyértelműen definiáltuk négyzetszámok egy sorozatát, meg fogjuk mutatni, hogy \(\displaystyle a_n\leq 2^{n+2}\). A továbbiakban feltesszük, hogy \(\displaystyle 5<n\), mert \(\displaystyle n\leq 5\)-re teljesül az egyenlőtlenség a már meghatározott értékek alapján.
Először is jegyezzük meg, hogy \(\displaystyle a_{k+1}\) legfeljebb akkora, mint a legkisebb \(\displaystyle s_k:=a_1+a_2+\dots+a_k\)-nál nagyobb négyzetszám. Ha ugyanis \(\displaystyle s_k<b\) négyzetszám, akkor az \(\displaystyle a_1,a_2,\dots,a_k,b\) elemekből képezhető (részhalmaz)összegek mind különbözők. Az összes \(\displaystyle b\)-t nem tartalmazó összeg \(\displaystyle b\)-nél kisebb, és ezek az \(\displaystyle a_1,a_2,\dots\) sorozat definíciója alapján mind különbözők. Ha \(\displaystyle b\)-t használjuk, akkor az összeg legalább \(\displaystyle b\), így az előbbi összegeknél biztosan nagyobbat kapunk. Ezek egymástól is különböznek, hiszen ha két \(\displaystyle b\)-t tartalmazó összeg egyenlő lenne, akkor ezekből \(\displaystyle b\)-t elhagyva két \(\displaystyle b\)-t nem tartalmazó egyenlő összeget kapnánk, azonban ez a sorozat definíciója alapján nem lehetséges.
Így \(\displaystyle a_{k+1}\leq (\sqrt{s_k}+1)^2\) minden \(\displaystyle k\)-ra teljesül. Azt szeretnénk belátni, hogy \(\displaystyle a_n\leq 2^{n+2}\), ehhez először az \(\displaystyle s_k\) értékekre keresünk felső becslést:
\(\displaystyle s_{k+1}=s_k+a_k \le s_k+\left(\sqrt{s_k}+1\right)^2 < 2\left(\sqrt{s_k}+\frac1{\sqrt2}\right)^2,\)
amiből
\(\displaystyle \sqrt{s_{k+1}} < \sqrt2\cdot\sqrt{s_k}+1. \)
Ahhoz, hogy ennek segítségével könnyebben tudjunk explicit becslést adni \(\displaystyle s_{n+1}\)-re, keressünk olyan \(\displaystyle c\) konstanst, melyre az előbbi egyenlőtlenség ekvivalens a
\(\displaystyle \sqrt{s_{k+1}}+c < \sqrt2\cdot\left(\sqrt{s_k}+c\right) \)
egyenlőtlenséggel. A két egyenlőtlenség pontosan akkor ekvivalens, ha \(\displaystyle \sqrt{2}c-c=1\), vagyis ha \(\displaystyle c=\frac{1}{\sqrt2-1}=\sqrt{2}+1\). Vagyis minden \(\displaystyle k\)-ra
\(\displaystyle \sqrt{s_{k+1}}+\sqrt2+1 < \sqrt2\cdot\left(\sqrt{s_k}+\sqrt2+1\right). \)
A becslést \(\displaystyle k=4\)-től \(\displaystyle k=n-1\)-ig alkalmazva kapjuk, hogy
\(\displaystyle \sqrt{s_{n-1}} +\sqrt2+1 < (\sqrt{s_4}+\sqrt2+1)\cdot\sqrt2^{n-5} <8 \cdot\sqrt2^{n-5} = \sqrt2^{n+1}, \)
hiszen \(\displaystyle s_4=1+4+9+16=30\) és \(\displaystyle \sqrt{30}+\sqrt2+1<8\). Ebből pedig
\(\displaystyle a_n<\left(\sqrt{s_{n-1}}+1\right)^2<2^{n+1}.\)
Ezzel igazoltuk a feladat állítását, abban az erősebb formában, hogy már 1-től \(\displaystyle 2^{n+1}\)-ig is kiválasztható \(\displaystyle n\) négyzetszám a feltételeknek megfelelően (ez \(\displaystyle n\leq 5\)-re is teljesült).
Megjegyzés. 1-től \(\displaystyle 2^n\)-ig \(\displaystyle n=5\) esetén nem választható ki 5 négyzetszám, ehhez ugyanis az \(\displaystyle 1,4,9,16,25\) négyzetszámokat kellene kiválasztani, azonban \(\displaystyle 9+16=25\).
Statisztika:
18 dolgozat érkezett. 6 pontot kapott: Bényei Borisz, Chrobák Gergő, Duchon Márton, Kalocsai Zoltán, Sági Mihály, Varga Boldizsár. 5 pontot kapott: Baski Bence, Ben Gillott, Lovas Márton. 4 pontot kapott: 4 versenyző. 3 pontot kapott: 2 versenyző. 2 pontot kapott: 1 versenyző. 0 pontot kapott: 2 versenyző.
A KöMaL 2022. januári matematika feladatai