prisoner solution
tbitonti said:
Does anyone know a non-iterative way to solve this using elementary
functions (or even using Fibonacci numbers, or a base 2 representation
and a summation)?
Sure. Here's a solution involving binary representation, although at the end I'll turn the final answer into a straight arithmetic formula.
First time through, you're knocking out all the odd numbers, i.e. those ending in 1. Once you've done that, since everything left ends in 0, you can erase the final zero to prepare for the next round. So when you're ready to start round 2, you've renumbered your round-1 survivors from 1-500, although the prisoner now numbered k used to be numbered 2k.
Since 1000 is even, the last prisoner survives the first round. That means the second round proceeds the same as the first round, with the first prisoner in line, and all who now have odd numbers (second bit from the right is 1) getting killed and those whose second bit from the right is 0 surviving.
Likewise, since 1000 has 0 for its second and third rightmost bits, the third and fourth rounds will eliminate those whose third and fourth bits respectively are 1.
But the third round will leave 125 prisoners, number 1-125 (after their three trailing 0's have been erased. This is odd, so the fourth round will kill the last prisoner. That means that the fifth round will begin by sparing the first prisoner, and continue by killing the even numbers and sparing the odd numbers.
Notice the key property of 1000: its fourth-smallest bit, which becomes the smallest bit on the fourth round, is a 1. That tells you that on the fifth round its the numbers with 1 for their now-smallest (originally fifth-smallest) bit that get spared.
You see the pattern: whatever bit (0 or 1) 1000 has in any given place, survivors must have the same bit in the next place to the left. In other words, the final survivor must look like the original number of prisoners (in this case 1000), shifted one bit to the left, with the leading one erased (so that the number isn't bigger than 1000).
Now shifting the whole number one place to the left with a trailing 0 is equivalent to multiplying by 2. Erasing the leading 1 is subtracting the highest power of two smaller than the now-doubled number, or equivalently the smallest power of 2 larger than the original number.
So, if you have n prisoners, the survivor is 2n-p, where p is the next power of 2 after n. In this case, 2x1000-1024-976.
And when you write
tbitonti said:
Note that 976 == 1024 - 48 == 1024 - 32 - 16,
you miss the more interesting breakdown: 976=1024-24-24, the 24 being relevant because 1000=1024-24.
