 |
A B. 5179. feladat (2021. május) |
B. 5179. Van-e olyan egész számokból álló \(\displaystyle H\) halmaz, amelyre teljesül, hogy a \(\displaystyle 0\) kivételével minden egész szám végtelen sokféleképpen felírható néhány, egymástól különböző \(\displaystyle H\)-beli elem összegeként, de a \(\displaystyle 0\) nem írható fel ilyen módon?
(6 pont)
A beküldési határidő 2021. június 10-én LEJÁRT.
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.\)
Statisztika:
16 dolgozat érkezett. 6 pontot kapott: 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 pontot kapott: 1 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 4 versenyző.
A KöMaL 2021. májusi matematika feladatai