A Circular MassacreDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/