3
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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 pth and so on. Do you mean the zeroth number, the pth, the 2pth, 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. $\endgroup$ Mar 19, 2011 at 10:05
  • $\begingroup$ 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! $\endgroup$
    – Kerry
    Mar 19, 2011 at 10:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – user9072
    Mar 19, 2011 at 11:33
  • $\begingroup$ 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. $\endgroup$
    – Kerry
    Mar 19, 2011 at 21:21
  • $\begingroup$ 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. $\endgroup$ Mar 19, 2011 at 23:35

1 Answer 1

3
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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$. $\endgroup$
    – Kerry
    Mar 19, 2011 at 21:27
  • $\begingroup$ I think in the Josephus problem you just look at the $p$th guy modulo however many are left... $\endgroup$
    – Igor Rivin
    Mar 19, 2011 at 22:02
  • $\begingroup$ Sorry I still do not really understand... $\endgroup$
    – Kerry
    Mar 19, 2011 at 22:20
  • $\begingroup$ 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. $\endgroup$ Mar 19, 2011 at 23:28
  • $\begingroup$ 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... $\endgroup$
    – Kerry
    Mar 20, 2011 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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