in Combinatory
146 views
0 votes
0 votes
Question $33–37$ deal with a variation of the $\textbf{Josephus problem}$ described by Graham, Knuth, and Patashnik in $[G_{r}K_{n}P_{a}94].$ This problem is based on an account by the historian Flavius Josephus, who was part of a band of $41$ Jewish rebels trapped in a cave by the Romans during the Jewish Roman war of the first century. The rebels preferred suicide to capture; they decided to form a circle and to repeatedly count off around the circle, killing every third rebel left alive. However, Josephus and another rebel did not want to be killed this way; they determined the positions where they should stand to be the last two rebels remaining alive. The variation we consider begins with n people, numbered $1$ to $n,$ standing around a circle. In each stage, every second person still left alive is eliminated until only one survives. We denote the number of the survivor by $J (n).$

Show that $J (n)$ satisfies the recurrence relation $J (2n) = 2J (n) − 1\:\text{and}\: J (2n + 1) = 2J (n) + 1,\:\text{for}\: n \geq 1, \:\text{and}\: J (1) = 1.$
in Combinatory
by
146 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true