Home > Mathematics > Two Step Josephus

Two Step Josephus

In this post, I aim to approach the solution for the  Josephus problem for  (n,2) constructively. The motivation is amplification of the  wikipedia entry.

The Josephus problem for step size 2 (i.e. killing of alternate members of group), allows recursive definition of the position of the last person (see the wikipedia entry). Let n by the size of the group.  The recursion can be written as follows:

f(n)= 2 f(\lfloor{\frac{n}{2}\rfloor}) + (-1)^{n+1}

n can represented in binary as: b_0b_1\ldots b_m , i.e n = \sum_{j=0}^m b_{m-j}2^j where b_0 =1 and the remaining b_{1\leq j\leq m} are 0  or 1.

Now I make the following observations (excuse some notational abuses):

  • \lfloor {\frac{n}{2}}\rfloor = \lfloor{b_0\ldots b_m/10}\rfloor = b_0\ldots b_{m-1}
  • n = 2^m + l yields l=b_1\ldots b_m
  • \sum_{j=0}^{m-1} 2^j =2^m -1
  • b_0 =1, f(b_0) =1
Therefore,
f(b_0\ldots b_m) = 2 f(b_0\ldots b_{m-1}) + (-1)^{b_m+1}
Repeating this till f(b_0),
f(b_0\ldots b_m) = 2^m f(b_0) + \sum_{j=0}^{m-1} (-1)^{b_{m-j}+1}2^j
f(b_0\ldots b_m) =(2^m -1 +\sum_{j=0}^{m-1} (-1)^{b_{m-j}+1} 2^j )+1
f(b_0\ldots b_m)=\sum_{j=0}^{m-1} (1+(-1)^{b_{m-j}+1})2^j +1
 N0w, note if b_j =0 then (-1)^{b_j +1}=-1 hence 1+ (-1)^{b_j+1}=0=2^{m-j}\times 0=2 b_j and b_j =1 implies 1 +(-1)^{b_j+1}=2=2 b_j.
Therefore,
f(b_0\ldots b_m) = \sum_{j=0}^{m-1} 2 b_{m-j}2^j \quad +1
f(b_0\ldots b_m)= 2\sum_{j=0}^{m-1} b_{m-j}2^j\quad +1 =10 \times b_1\ldots b_m +1
Using the notation of the wikipedia entry and the definition above,
f(n) = 2 l +1
Now it follows:
  • n =2^k yields f( 10\ldots 0)= 1
  • n=b_0\ldots b_m yields f(b_0\ldots b_m) = b_1b_2\ldots b_mb_0 , i.e cyclic left shift of one
The latter can be seen as follows:
2l +1 =2n -2^{m+1} +1
2n =b_0\ldots b_m0
2n-2^{m+1} = b_1\ldots b_m0 as b_0 =1
2n-2^{m+1} +1 =b_1\ldots b_m1=b_1\ldots b_mb_0
Notes:
WordPress posed problems in \LaTeX arrays in this post. I apologise for the less than ideal formatting.
Advertisements
Categories: Mathematics
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: