ik heb na lange tijd een potentiële directe formule voor het Josephus probleem gevonden, hierbij wordt er elke tweede persoon vermoord. (Dus iedereen staat in een cirkel en persoon met nr. 2 wordt als eerst vermoord, daarna nr. 4 etc. Als het 1 ronde geweest is, wordt het proces herhaalt.) Ik moest dan de formule vinden voor het laatste persoon die werd vermoord.
Ik kwam op het volgende:
\(J(n) = 1 + 2 \cdot (n - 2^{\lfloor \lg n \rfloor})\)
waarbij n is het aantal mensen dat aanwezig zijn in de cirkel.De vraag is nu hoe bewijs ik dit. Ik dacht dus door middel van inductie, maar ik kwam dus bij het volgende (neem aan dat ik wel de basisstap heb gedaan, dus intialisatie).
\( J(n+1) = 1 + 2 \cdot ((n+1) 2^{\lfloor \lg (n+1) \rfloor})\)
\( J(n) = 1 + 2 \cdot (n - 2^{\lfloor \lg n \rfloor})\)
Dus ik dacht ik trek ze van elkaar af en kijken wat ik dan moet bewijzen. Maar het probleem is dat ik niet weet wat hier uit komt: \(J(n+1) - J(n) = ?\)
ik dacht zelf aan \(J(1)\)
maar ik weet het niet zeker.Kan iemand mij misschien vertellen of ik goed zit?
Bedankt!
