Problem B. 5220. (January 2022)
B. 5220. Let \(\displaystyle n\) be a positive integer. Prove that it is possible to select \(\displaystyle n\) perfect squares from the numbers \(\displaystyle 1\) to \(\displaystyle 2^{n+2}\) such that the sums obtained by adding an arbitrary subset of the selected numbers (including sums of single terms and the sum of all the numbers) are all distinct.
Proposed by R. Freud, Budapest
(6 pont)
Deadline expired on February 10, 2022.
Sorry, the solution is available only in Hungarian. Google translation
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\).
Statistics:
18 students sent a solution. 6 points: Bényei Borisz, Chrobák Gergő, Duchon Márton, Kalocsai Zoltán, Sági Mihály, Varga Boldizsár. 5 points: Baski Bence, Ben Gillott, Lovas Márton. 4 points: 4 students. 3 points: 2 students. 2 points: 1 student. 0 point: 2 students.
Problems in Mathematics of KöMaL, January 2022