2
$\begingroup$

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1".

$J(2n) = 2J(n) - 1$, for $n \ge 1$

I don't quite understand where the subtraction of 1 comes in.

This also goes for the odd problem where the formula is given as:

$J(2n+1) = 2J(n) + 1$, for $n \ge 1$

I know I'm missing an obvious piece of logic here but I haven't figured it out so far...

$\endgroup$
1
$\begingroup$

For the even case, the reason for the decrease is that instead of having $n$ numbers as:

$\qquad 1,2,3, \ldots n\qquad$ we have $\qquad 1,3,5, \ldots 2n-1$

So the $i^{th}$ number is $2i - 1$ now. So whatever $J\left(n\right)$ is we need to double it and subtract $1$ to get the correct result.

Similarly for the odd case, instead of the $n$ numbers as:

$\qquad 1,2,3, \ldots n\qquad$ we have $\qquad 3,5,7, \ldots 2n+1$

So the $i^{th}$ number is $2i + 1$ now.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Right, so it's got to do with the positioning of the numbers after every second number is removed. But I don't understand the leap of logic from determining the new positioning with this equation to actually solving for the number that remains... $\endgroup$ – momo Aug 2 '14 at 12:05
  • $\begingroup$ We initially had (for the even case) $2n$ numbers, now we have $n$ numbers. So it means if we can evaluate $J(n)$ then we can evaluate $J(2n)$. Eg. we know $J(1)=1$ so our eqn gives us $J(2)=2*J(1)-1=1, J(4)=2J(2)-1=1$, and so on. What's really happening here for $J(4)$: start with "1,2,3,4". After one cycle we have: "1,3". We know $J(2)=1$, which means if we have 2 numbers, the 1st will be the survivor. It doesn't matter if those 2 numbers are "1,2" or "1,3" or "1698, 543" - the number in position 1 survives. So for "1,3" we know 1 is the answer. I hope I have understood you correctly. :-) $\endgroup$ – Mick A Aug 2 '14 at 12:52
  • $\begingroup$ Ah yes, your comment + a little reading on the wiki cleared it up for me. I forgot that this is solved with recursion. $\endgroup$ – momo Aug 3 '14 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.