A Circular Massacre

Date: 09/25/98 at 04:33:58
From: Karen Kurczak
Subject: "A Circular Massacre" : Number Theory

Ten thousand sailors are arranged around the edge of their ship. 
Starting with the first one, every other sailor is pushed overboard 
until they are all gone. 

  1) Where would you be standing to be the last survivor? 

  2) How many times is the last survivor skipped over before he is 
     finally pushed overboard? 

  3) Find the location of the 
     a) second to last survivor 
     b) third to last survivor 
     c) 100th to last survivor.

Date: 09/25/98 at 15:58:49
From: Doctor Rob
Subject: Re: "A Circular Massacre" : Number Theory

Number the sailors around the edge of the ship in sequence from 1 to 
10000.

Round 1: Push 1, 3, 5,..., 9999 overboard, not 2*k (5000 numbers)
Round 2: Push 2, 6, 10,..., 9998 overboard, not 4*k (2500 numbers)
Round 3: Push 4, 12, 20,..., 9996 overboard, not 8*k (1250 numbers)
Round 4: Push 8, 24, 40,..., 9992 overboard, not 16*k (625 numbers)
Round 5: Push 16, 48, 80,..., 10000 overboard, not 32*k (312 numbers)

Since the highest number was pushed overboard, the lowest remaining 
number is skipped in the next round. This happens when the length of 
the list remaining is odd and the lowest number had been removed, or 
else the length is even, and the second-lowest number had been removed. 
That happens when bit n-1 in the base-2 form of N is a 1.

Round 6: Push 64, 128, 192,..., 9984 overboard, not 64*k+32 (156 #s)
Round 7: Push 96, 224, 352,..., 9952 overboard, not 128*k+32 (78 #s)
Round 8: Push 160, 416, 672,..., 9888 overboard, not 256*k+32 (39 #s)
Round 9: Push 288, 800, 1312,..., 9504 overboard, not 512*k+32 (20 #s)
Round 10: Push 32, 1056, 2080,..., 9248 overboard, not 1024*k+544 (10)  
Round 11: Push 544, 2592, 4640, 6688, 8376 overboard, not 2048*k+1568 (5)
Round 12: Push 1568, 5664, and 9760 overboard, not 4096*k+3616 (2)
Round 13: Push 7712 overboard, not 3616 (1)

The last survivor is 3616, the next-to-last is 7712, and the one before 
that is 9760.

All the numbers remaining after round n have the same low-order n bits 
when written in base 2. They are also the low-order n bits of 2*N.

The last survivor L is given by L = 2*N - 2^e, where 2^e is the power 
of 2 with 2*N > 2^e >= N. In this case it is:

   20000 - 2^14 = 20000 - 16384 = 3616

The proof of this formula depends on the statement between Round 5 and 
Round 6 above. The bits of L when written in base 2 are gotten from
those of N by dropping the leftmost 1 and putting an extra 0 on the 
right end. N = 10000 base 10 = 10011100010000 base 2, so 
L = 111000100000 base 2 = 3616 base 10.

The next-to-last (or penultimate) survivor P is given by 
P = L - 2^(e-1) if N > 3*2^(e-2) (that is, the first two bits of N in 
base 2 are "11", or else P = L + 2^(e-2) if N <= 3*2^(e-2) (the first 
two bits are "10").

When N = 10000, e = 14, and L = 3616. Then since 10000 <= 3*2^12 = 
12288, P = 3616 + 4096 = 7712 base 10 = 1111000100000 base 2.

I leave finding the ante-penultimate survivor A and the 
100th-from-the-end survivor to you.

You can also check out a similar problem at:

  Knights of the Round Table
   http://mathforum.org/dr.math/problems/lou7.1.98.html   

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/