Assignment: the Josephus problem
Forty-one rebels in a circle, eliminated three by three: where should you stand to survive? A take-home assignment leading from a Python simulation to an exact formula readable off the binary expansion.
Advanced 120 min 45 viewsmathsarithmétiquealgorithmiquePythonrécurrenceDM
Table of contents
- 01
Part I — Computational treatment
- Forty-one rebels in a circle(not finished)
- Eliminating with a Python list(not finished)
- The function returning the last survivorOpen answer
- Numerical application: the case of JosephusShort answer
- Numerical application: elimination two by twoShort answer
- Returning the last p survivorsOpen answer
- Fifty good people and fifty villainsOpen answer
- 02
Part II — Base-2 expansion
- 03
Part III — A recurrence relation for the case k = 2
- The recurrence hidden behind J(not finished)
- The parity of the survivorOpen answer
- The two recurrence relationsOpen answer
- The case of powers of twoShort answer
- Writing n in the form 2^α + ℓOpen answer
- The formula J(n) = 2ℓ + 1Open answer
- J(n) read off the binary expansionMCQ
- The Josephus problem two by twoShort answer
- 04
Part IV — More general recurrences
- Three basis sequences(not finished)
- Turning the problem around(not finished)
- The three basis sequences A, B and COpen answer
- The general solution as a linear combinationOpen answer
- Recovering the formula of part IIIOpen answer
- Existence of the decomposition, without guessing A, B and COpen answer
- The parameters of the identity functionShort answer
- The system that yields A, B and COpen answer
- The binary reading of the general solutionOpen answer