Problem B. 5179. (May 2021)
B. 5179. Is there a set \(\displaystyle H\) of integers with the following property: every nonzero integer can be represented in infinitely many ways as a sum of some distinct elements of \(\displaystyle H\), but \(\displaystyle 0\) cannot be represented at all?
(6 pont)
Deadline expired on June 10, 2021.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Azt fogjuk igazolni, hogy van ilyen \(\displaystyle H\) halmaz.
Legyen \(\displaystyle (F_n)\) a Fibonacci-sorozat, vagyis \(\displaystyle F_1=F_2=1\), és \(\displaystyle n\geq 3\) esetén \(\displaystyle F_n=F_{n-2}+F_{n-1}\). Legyen
\(\displaystyle H=\{F_2,-F_3,F_4,-F_5,F_6,-F_7,\dots\}=\{1,-2,3,-5,8,-13,\dots\}.\)
Először megmutatjuk, hogy a 0 nem áll elő összegként, viszont minden más egész szám előáll – esetleg egytagú – összegként. Teljes indukcióval megmutatjuk, hogy \(\displaystyle F_2,-F_3,F_4,-F_5,\dots,(-1)^n F_n\) segítségével
- páros \(\displaystyle n\) esetén minden nemnulla érték előáll a \(\displaystyle [-(F_{n}-1),\dots,F_{n+1}-1]\) intervallumban, a 0 viszont nem áll elő,
- páratlan \(\displaystyle n\) esetén minden nemnulla érték előáll a \(\displaystyle [-(F_{n+1}-1),\dots,F_{n}-1]\) intervallumban, a 0 viszont nem áll elő.
Ezt \(\displaystyle n\)-re vonatkozó teljes indukcióval igazoljuk.
Az állítás \(\displaystyle n=2\)-re azt mondja, hogy \(\displaystyle F_2=1\) segítségével \(\displaystyle [0,1]\) minden nemnulla eleme – vagyis az 1 – előáll, a 0 viszont nem, ami nyilván teljesül. Az \(\displaystyle n=3\) esetben pedig azt, hogy \(\displaystyle F_2=1,-F_3=-2\) segítségével \(\displaystyle [-2,1]\) minden nemnulla eleme előáll, ami szintén teljesül:
\(\displaystyle -2=-2,\)
\(\displaystyle -1=(-2)+1,\)
\(\displaystyle 1=1,\)
és az is világos, hogy a 0 nem áll elő.
Most az indukciós lépés igazolásához tegyük fel, hogy \(\displaystyle n=k\)-ra már igazoltuk az állítást, megmutatjuk, hogy \(\displaystyle n=k+1\)-re is teljesül.
Először tegyük fel, hogy \(\displaystyle k\) páros, és tudjuk, hogy \(\displaystyle [-(F_{k}-1),\dots,F_{k+1}-1]\) minden nemnulla eleme előáll összegként, a 0 pedig nem áll elő. Az \(\displaystyle n=k+1\) esetben a \(\displaystyle -F_{k+1}\) elem is használható. Természetesen, minden ami eddig előállt, továbbra is előáll (ugyanúgy), azonban \(\displaystyle -F_{k+1}\) segítségével újabb előállításokat is kapunk. Például \(\displaystyle -F_{k+1}\) előáll mint egytagú összeg, továbbá a \(\displaystyle [-(F_{k}-1),\dots,F_{k+1}-1]\) intervallumba eső számok előállításához \(\displaystyle -F_{k+1}\)-et hozzávéve megfelelő előállítást kapunk, így \(\displaystyle [-F_{k}-F_{k+1}+1,\dots,-1]\) minden eleme szintén előáll, pontosan ezek azok az értékek, amelyeknek van \(\displaystyle -F_{k+1}\)-et tartalmazó előállítása. Speciálisan ez azt is jelenti, hogy a 0 továbbra sem áll elő, hiszen az előbbi intervallum minden eleme negatív. Ugyanakkor, mivel \(\displaystyle F_k+F_{k+1}=F_{k+2}\), ezért
\(\displaystyle [-(F_{k}-1),\dots,F_{k+1}-1]\cup [-F_{k}-F_{k+1}+1,\dots,-1]=[-(F_{k+2}-1),F_{k+1}-1]\)
minden nemnulla eleme előáll, azaz az állítás \(\displaystyle n=k+1\) esetén is teljesül.
Az az eset, amikor \(\displaystyle k\) páratlan, teljesen hasonló. Ekkor az \(\displaystyle n=k\) esetből tudjuk, hogy \(\displaystyle [-(F_{k+1}-1),\dots,F_{k}-1]\) minden nemnulla eleme előáll, a 0 viszont nem. Így ha \(\displaystyle F_{k+1}\)-et is használhatjuk, akkor a
\(\displaystyle [-(F_{k+1}-1),\dots,F_{k}-1]\cup [1,F_k+F_{k+1}-1]=[-(F_{k+1}-1),F_{k+2}-1]\)
intervallum nemnulla elemei állíthatók elő, a 0 pedig továbbra sem, mert az \(\displaystyle F_{k+1}\)-et tartalmazó előállítások mind pozitív összeget adnak. Tehát az állítás teljesül \(\displaystyle n=k+1\)-re is.
Teljes indukcióval következik, hogy az állításunk minden \(\displaystyle 2\leq n\)-re igaz.
Az eddigiek alapján tehát különböző \(\displaystyle H\)-beli elemek összegeként minden nemnulla egész szám előállítható (esetleg egytagú) összegként, a 0 viszont nem. Most belátjuk, hogy egy előállításból kaphatunk 1-gyel több tagú előállítást, ezt ismételten alkalmazva végtelen sok előállítás nyerhető, és ez azt jelenti, hogy a megadott \(\displaystyle H\) halmaz valóban kielégíti a megadott feltételeket.
Legyen egy \(\displaystyle a\) egész szám előálításában a legnagyobb abszolút értékű tag \(\displaystyle (-1)^nF_n\). Ekkor \(\displaystyle (-1)^{n+1}F_{n+1}\) és \(\displaystyle (-1)^{n+2}F_{n+2}\) nem szerepelnek a felbontásban, így \(\displaystyle (-1)^nF_n\)-t lecserélhetjük erre a két elemre, hiszen:
\(\displaystyle (-1)^{n+1}F_{n+1}+(-1)^{n+2}F_{n+2}=(-1)^n(-F_{n+1}+F_{n+2})=(-1)^nF_n.\)
Megjegyzés. A feladatban szereplő konstrukció a Lányok Európai Matematikai Olimpiája (EGMO) 2012, 1. nap 4. feladatának is megoldását adja. Ennél a feladatnál egészek olyan végtelen halmazát kellett konstruálni, melynek minden eleme előáll két másik elem összegeként, azonban a 0 nem áll elő részhalmaz összegként. Világos, hogy a fent megadott \(\displaystyle H\) halmaz megfelelő, hiszen
\(\displaystyle (-1)^nF_n=(-1)^{n+1}F_{n+1}+(-1)^{n+2}F_{n+2}.\)
Zaimi 2010-es kérdése, hogy ilyen tulajdonságú véges halmaz is létezik-e, amire már nemleges a válasz.
Megemlítjük még a Zeckendorf-reprezentációt, mely szerint minden pozitív egész szám egyértelműen állítható elő egy vagy több Fibonacci-szám összegeként úgy, hogy az előállításban szereplő számok közül semelyik kettő nem szomszédos a Fibonacci-sorozatban. Például az első néhány előállítás:
\(\displaystyle 1=1,\quad 2=2,\quad 3=3,\quad 4=1+3,\quad 5=5,\quad 6=1+5,\quad 7=2+5,\quad 8=8,\quad 9=1+8,\quad 10=2+8.\)
Statistics:
16 students sent a solution. 6 points: Beinschroth Ninett, Ben Gillott, Fekete Richárd, Kalocsai Zoltán, Kovács 129 Tamás, Kökényesi Márk Péter, Lovas Márton, Nagy 551 Levente, Sztranyák Gabriella, Zömbik Barnabás. 2 points: 1 student. 1 point: 1 student. 0 point: 4 students.
Problems in Mathematics of KöMaL, May 2021