Zeckendorf-tétel

A Zeckendorf-tétel Edouard Zeckendorf 1972-es tétele, mely így szól: Minden természetes ${\displaystyle n}$ szám előáll különböző Fibonacci-számok összegeként. Ha adottnak vesszük, hogy ${\displaystyle \forall i(1\leq i<r):k_{i}\geq k_{i+1}+2}$ és ${\displaystyle k_{r}\geq 2}$ (azaz, hogy a Fibonacci-számok között nem lehet két egymást követő, valamint a Fibonacci-sorozat első tagja, ${\displaystyle F_{1}=1}$, sem), a felírás egyértelmű, ${\displaystyle n=\sum _{i=0}^{r}F_{k_{i}}}$.

A Zeckendorf-tételnek köszönhetően konstruálható olyan számrendszer, melyben a helyiértékek rekurzív sorozatot alkotnak. Ez az ún. Fibonacci-számrendszer, melynek helyiértékei: … 21, 13, 8, 5, 3, 2, 1. A tétel miatt ebben a számrendszerben csak két számjegy (a 0 és az 1) szerepelhet. A tétel második része miatt továbbá, az ebben a számrendszerben történő felíráskor nem állhat egymás mellett két egyes. A természetes számoknak ezt a fajta felírását Zeckendorf-reprezentációnak nevezzük. Így például a 4 Zeckendorf-reprezentációja 101, a 6-é 1001, a 18-é 101000 stb.

A Fibonacci Nim egy kétszemélyes játék. Szabályai: Adott egy tetszőleges (ismert) számú kavicsból álló halom. Az első játékos ebből tetszőleges számú kavicsot elvehet, de az összeset nem. Ezután minden játékos legfeljebb annyi kavicsot vehet el, mint az előző lépésben elvett kavicsok számának kétszerese (természetesen minden lépésben legalább egy kavicsot kötelező elvenni). A játékot az nyeri, aki az utolsó kavicsot vette el. Ennél a játéknál azt kell megfigyelnünk, hogy a kezdő játékosnak pontosan akkor van nyerő stratégiája, ha a kavicsok száma nem Fibonacci-szám. A pontos nyerő stratégia meghatározásában pedig a Zeckendorf-reprezentáció nyújthat segítséget.

• Fibonacci-sorozat
• Aranymetszés

• A more general Fibonacci System
• Sulinet – A Fibonacci-számrendszerről