0
$\begingroup$

Josephus problem*:
circle=1,2,3,4,5,6,7,8,9,10. count=2. (Beginning at 1) The "last man standing" in this case=9.
Order of elimination or permutation (?): 2,4,6,8,10,3,7,1,9

For any size circle and any size count what is the math that produces the order of elimination? e.g. circle=1,2,3,4,5,6,7,8,9. count=10.
Order of elimination (starting at 1): 1,3,6,2,9,5,7,4,8

*(From wikipedia: http://en.wikipedia.org/wiki/Josephus_problem) The Josephus problem is a theoretical problem related to a certain counting-out game. There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

(Original post)

(please forgive me if this looks slightly familiar to anyone...)

Hello,

Does anybody know the math for a general case Josephus-like permutation (any size circle, any size count)?

e.g circle=9, count=10.
1,3,6,2,9,5,7,4,8

I only have access to what I can find on the web (Google) and what has previously been suggested doesn't cover this particular aspect (Concrete math; wikipedia....). The nearest I have found is http://mathworld.wolfram.com/JosephusProblem.html
Can anyone help?

TIA, Ian

  • 0
    Gerry, please tell me, is that any clearer?2012-05-20

1 Answers 1

1

The math that produces the order of elimination is just counting repeatedly up to 10. Here's your circle: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, etc. Starting at 1, you count to 10, you land on 1, so you eliminate it. Now your circle is 2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, etc. You count to 10, and you land on 3. You eliminate it, and your circle becomes 4, 5, 6, 7, 8, 9, 2, 4, 5, 6, 7, etc. You count to 10, land on 6, eliminate it, etc., etc., etc.

Now it's possible (but not at all clear from your question) that you already know all that, and what you really want is a formula that gives you the order of elimination without doing all the counting. I don't know if there is such a thing, but I know a good place to start looking: Gregory L. Wilson and Christopher L. Morgan, An application of Fourier transforms on finite Abelian groups to an enumeration arising from the Josephus problem, J. Number Theory 130 (2010) 815–827, MR 2600404.The paper gives many references to other papers on the Josephus problem.

  • 0
    You might have to understand abelian groups and Fourier transforms to understand that paper, but as I wrote the paper gives many other references to work on the Josephus problem, and some of those other works may be more accessible. Also, many papers have a non-technical introduction that summarizes what's known about the problem, and what's new in the paper at hand, so it's worth having a look at that.2012-05-21