Josephus Problem - Puzzle

Read about this in Concrete Mathematics - Knuth some time back... Interesting problem

There are n persons in a circle, numbered 1 to n. Going around the circle, every second person is removed from the circle, starting with person number 2, 4, and so on. Show that the number of the last person remaining in the circle can be obtained by writing n in binary, then moving the leftmost 1 to the right. So for example, with n = 13 persons (1101 in binary), the last person is number 11 (1011 in binary).

Math at :
http://en.wikipedia.org/wiki/Josephus_problem

Solution:

In case of 13,
The order in which people die are
xxx0
xx01 {Since last bit of 13 was 1, hence xx01, otherwise it would have been xx11}
x111 {Since secondlast bit of 13 was 0, hence x111, otherwise it would have been x011}
0011 {Since thirdlast bit ....}

So, you would want to be 1011

So, we can see that the solution for a general n is
in the bit representation of n, add a bit 1 at the end and remove the first bit

So, for 1101 -> 1011

For 10,
order of killing is 2, 4, 6, 8, 10, 3, 7, 1, 9
So left is 5
1010 -> 0101

For 15,
order of killing is 2, 4, 6, 8, 10, 12, 14, 1, 5, 9, 13, 3, 11, 7
1111 -> 1111

For 7,
order of killing is 2, 4, 6, 1, 5, 3
0111 -> 1111?? 0111

For 6,
order of killing is 2, 4, 6, 3, 1
0110 -> 1101?? 0101

So, if the output is >n, we should be making the first bit 0

I suppose.. thats the answer.... :)

Comments

  1. Anonymous11:49 PM, February 15, 2012

    This answer seems not to be able to generate to every third people get killed. For example, for 27 people, the survivor is number 20
    and the base 3 notation for 27 is 1000,
    20 is 202, does not seem to be obviously related..

    ReplyDelete
  2. Samyak Jaroli1:08 AM, September 05, 2013

    To add to the solution:
    Adding more to the solution for generalized N.

    For general case,
    I am first proving that for N = 2^a + b persons; 2b+1 location person would be last remaining. 0 <= b <(2^a)

    First considering when n= 2^a:
    In n= 2*a, the starting point will be remaining person.
    Eg. 1 as starting point
    1,2,3..16 (16 persons)
    1,3,5..15 (8 persons)
    1,5,9,13 (4 persons)
    1,9 (2 persons)
    1 (Last persons)

    Now we consider the case when n = 2^a + 1:
    In n=(2^a) + 1, After first round starting point will change.
    Eg. 1 as starting point
    1,2,3..17 (17 persons)
    1,3,5..17 (9 persons)
    3,7,11,15 (4 persons)*
    3,11 (2 persons)
    3 (Last person)

    This removal series generated is series with a starting point and increments (AP, incr=2^iteration)
    In the above case of 2^a + 1 people, we can just remove 1 person and result will follow the traits of 2^a.
    I.e. in 17 people we can remove No.2 (first removal) to get 2^a people and starting point would be 3.

    ||ly in case of 2^a + b people we just remove b *alternate* people and person after that would be the starting point (last person remaining.) The location of this person would be 2b+1.

    For N = no. of people in circle, can be written as:
    N = 2^a + b such that 0 <= b < (2^a)
    and last remaining person in 2b+1

    For N = 13, N = 2^3 + 5
    => last remaining person is 2*5 +1

    In binary for N, removing 1 from MSB will mean subtracting 2^a to get only b.
    And to get 2b+1, appending 1 in the end. (one right shift will give 2b and adding 1)

    For N = 13, 1101 in binary, removing 1 from MSB will give 5. Meaning we remove 5 persons to get 2^a form.
    And location of this last remaining person is 2*5 + 1 (1010 + 1 in binary)




    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more