Jag sprang "av en slump" över en notis på Donald Knuths hemsida (ni vet, han som bland annat skrev TeX). Han nämner Fibonacci talsystem, ett talsystem där man skriver ett tal som summan av Fibonacciatal.
Jag hittade problemformuleringen här: http://www.hostsrv.com/webmaa/app1/MSP/webm1010/fibonaccinumbersystem.msp
Jag skrev en text om problemet, med ett något slarvigt bevis, och skrev sedan ett ännu slarvigare program som konverterar tal. Allt upplagt på min hemsida, under other: www2.paulsundvall.net
Uppdatering 20080317:
Christians kommentar är korrekt. Jag har tillåtit mig själv att ha 0 och 1 i koefficienterna, rätt är att man bara får ha 1 eller 2. Det som krävs för att komma hela vägen fram är att visa att alla mellanliggande nollor i ett tal skrivet med nollor och ettor går att eliminera, och få ett tal med enbart ettor och tvåor. Dvs att exempelvis talet (1,0,1,1) går att byta till (0,1,2,1) (inledande nollor räknas naturligtvis inte).
1 kommentar:
Intressant. Dock tror jag att du har förenklat problemet i och med din omformulering.
Skicka en kommentar