Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
See OEIS A198789 and A198790 for small examples –  Henry May 10 '12 at 7:18
    
Thank you for the reference, Henry - still, I have an even larger table produced with my own and it doesn't really help. –  H. M. Šiljak May 10 '12 at 7:26

1 Answer 1

up vote 3 down vote accepted

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}\;.$$

share|improve this answer
    
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. –  H. M. Šiljak May 10 '12 at 9:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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