Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For $n\in \mathbb{N}$ numbers $I_{n}=(1,2,3..n)$ and prime $p$, we define operation $(1,2,3..n)$ to $A=(a_{1},a_{2}...a_{p-1})$ as follows:

We arrange the $n$ numbers in a circle, then we eliminate the first number, the $p$th number, the 2$p$th number, etc, until there is only $p-1$ numbers left and the process terminated. We identify this subset as $A$.

My question is, for given $p$, does $A$ being equidistributed in $I_{n}$ with $n\rightarrow \infty$? I feel that "equidistributed" in arbitrarily set seems to be not well defined. In this one I want at least for a subset of $I_{n}$ of the form $S=(s,s+1...s+t-1)$. $|S\cap A|\rightarrow \frac{t}{n}*(p-1)$ with $n\rightarrow \infty$. I do not know whether this is possible. A few simple cases (like $p$=3, $n$=2011) is already in need of programming and the result seemed to be very random, I feel "intuitively" this should be true, but I do not know how to prove it.

There is some confusion which is obvious from the comment. I mean a circular process that eliminate a certain number, jump $p-1$ numbers in between, and then terminate the next number. This process will stop at the place there are $p-1$ numbers left.

An example: $n=20$, $p=5$, we have $(1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19)$ in the first elimination process. Then we have $(1,2,3,4,7,8,9,11,13,14,16,17,19)$ in the second round elimination process, and $(1,2,3,7,11,14,16,17,19)$ in the third round, and $(2,3,7,11,16,17,19)$ in the fourth round, finally yielding $(2,7,11,17)$ in the end.

share|improve this question
1  
You can probably do something with this problem with trigonometric sums, if I understand you. But there is a problem with the formulation? You say delete the first number, the p*th and so on. Do you mean the zeroth number, the *p*th, the *2p*th, and so on? That would make more sense to me. That is, you want to think about an arithmetic progression with difference *p, but regarded mod n, and look at its complement. –  Charles Matthews Mar 19 '11 at 10:05
    
I think $0$ th did make more sense than first number. The way you look at it - arithmetic progression mod $n$ is very surprising to me - I never thought this way. I will try to work with this hint. Thank you! –  Kerry Mar 19 '11 at 10:13
2  
The very natural interpretation of C.M. might not be what P. is asking for. (This is independent of starting with $0$ or $1$). Pencil, when you say the '2p-th number, etc' What do you do after you made a full round and there are already numbers missing: a. Do you count the 'empty spots' or b. do you only count the numbers that are remaining? Say for p=2 and {1,2,3,4,5,6,7}, let's ingnore the starting issue and assume you delete 2, 4, 6, then 1, but what now do you delete 3 (version a., counting the deleted 2) or 5 (v.b., ignoring 2 and 4)? C.M.'s is version a. Please clarify. –  quid Mar 19 '11 at 11:33
    
I think after a full round, we do not count the empty spots anymore. So for p=2 we delete 2,4,6, then we delete 1 and 5 from 7135, finally left us 7. I still need to think how Charles's comment may help. I did know Weyl's criterion but I do not know how to apply similar ideas to this problem. –  Kerry Mar 19 '11 at 21:21
    
I am trying to understand the process. Do you definitely mean (as in the Josephus process) that at each stage when you remove a number, you then move $p$ steps past the remaining numbers to find the next one that you remove? A small concrete example would be helpful. –  Anthony Quas Mar 19 '11 at 23:35

1 Answer 1

up vote 3 down vote accepted

Not quite an answer to the question but see http://en.wikipedia.org/wiki/Josephus_problem

There is a huge literature on the Josephus problem -- the wiki article is a good start. See also:

http://doc.utwente.nl/67513/1/pospp.pdf

and the very cool:

ftp://ftp.cis.upenn.edu/pub/wilf/josephus.ps

share|improve this answer
    
Hi! One thing I do not really understand is, the statement of the problem looks to be similar to my one, but the process cannot continue when there are less than $p$ numbers in my one (as we need $p-1$ numbers in between), yet in this problem it becomes "until only the last person remains, who is given freedom". I do not know how they managed to do this. For example, for number $(123456)$, $p=3$ would eliminate $3,6$, then $4,2$, and left us with $1,5$. –  Kerry Mar 19 '11 at 21:27
    
I think in the Josephus problem you just look at the $p$th guy modulo however many are left... –  Igor Rivin Mar 19 '11 at 22:02
    
Sorry I still do not really understand... –  Kerry Mar 19 '11 at 22:20
    
Another good reference for the Josephus problem is Graham, Knuth, and Patashnik's Concrete Mathematics. And to help unconfuse, using your example, we can count off. So we count 1, 2, eliminate 3, 4, 5, eliminate 6, wrap around, 1, 2, eliminate 4, 5, wrap around 1, eliminate 2, 5, wrap around, 1, eliminate 5. Now only 1 is left. –  Aubrey da Cunha Mar 19 '11 at 23:28
    
Hi! Thanks for the info, but if you eliminate $3,4,5,6$ already, then how could you eliminate $4,5$ and $2,5$ again? I feel even more confused now... –  Kerry Mar 20 '11 at 11:10

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.