Josephus problem is rather well known - every $m$-th person in circle of $n$ people is killed - question is where in the circle was the last person standing?

Let us make an inverse of that problem and ask

What is the least step $m$ for which $k$-th person is the last one standing in a circle of $n$ people ($n$ and $k$ are given)?

There are two logical questions to ask:

Does such $m$ always exist? (Conjecture: yes - computer tests show it is correct up to $n=300$).

What is the upper bound for $m$? $\text{lcm}(1,2,\ldots,n)$ seems logical, but is there something lower (computer tests show a number of outliers that make it hard to estimate such a bound).

  • $\begingroup$ See OEIS A198789 and A198790 for small examples $\endgroup$
    – Henry
    May 10 '12 at 7:18
  • $\begingroup$ Thank you for the reference, Henry - still, I have an even larger table produced with my own and it doesn't really help. $\endgroup$ May 10 '12 at 7:26

Here's the maximum of $m$ over all $k$ for fixed $n$ plotted over $n$ together with $nH_n$, the expectation value for the coupon collector's problem (where $H_n$ is the $n$-th harmonic number):

maximum of m over all k

The fact that the values seem to scatter around this expectation value indicates that it may be a good heuristic to consider the last person standing to be selected uniformly at random, independently for all $m$. If so, the "probability" for there to be any counterexamples beyond $n=1000$ (up to which I tested) should be exceedingly small. It's hard to quantify exactly how small, since the heuristic might not be valid all the way up to $m=\operatorname{lcm}(1,\dotsc,n)$, but even if it's just valid up to $n^2$, the "probability" of someone surviving all $n^2$ attempts on their life would be roughly

$$n\left(1-\frac1n\right)^{n^2}\approx n\mathrm e^{-n}\;,$$

so the expected number of counterexamples beyond $n=1000$ would be roughly

$$\int_{1000}^\infty n\mathrm e^{-n}\mathrm dn=1001\mathrm e^{-1000}\approx5\cdot10^{-432}\;.$$

  • $\begingroup$ The almost linear appearance of $nH_n$ tricked me and made me wonder why is it so - now it makes sense after all! Thank you for the answer. $\endgroup$ May 10 '12 at 9:43

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.