Write down all integers from 1 to 1000. Cross out the first number and every second number after that. So you will cross out 1, 3, 5 and so on. Now repeat the process exactly - cross out the first number and every second number from those that remain. Keep repeating the process until just one number remains. What is this last remaining number?
I think the number that remains is
First we cross out odd numbers leaving numbers divisible by 2.
Then we cross out numbers congruent to 2 modulo 4 leaving only numbers divisible by 4.
Then we cross out numbers congruent to 4 modulo 8 leaving only numbers divisible by 4. We see the pattern that we are always crossing out numbers congruent to 2n - 1 mod 2n leaving numbers divisible by 2n so it will be the highest power of 2 less than 1000 that remains at the end.
The last number will be
Every time the process is repeated, the remaining numbers are the multiples of the next integer in the sequence 2n:
1, 2, 3, 4, ...
2, 4, 6, 8, ...
4, 8, 12, 16, ...
Since 512 is the largest 2n in the range [1..1000], it will be the remaining number.
Beginning with 1 cross out every second number.
So I start at 1 and cross out 2, 4, …: all the evens. The odds remain.
Now repeat the process - cross out every second number from those that remain.
I cross out every second odd: 3, 7, 11,…: but I don't cross out 1, for example.
Keep repeating the process until just one number remains. What is this last remaining number?
No matter what, your "every second number" will always start after 1, so you'll never cross out 1, and it will be the last number standing.
In the first step (as can already be quite clearly seen from what's in the question), we cross out all the odd numbers, and so
we are left with the even numbers, that is, with the multiples of 2. Since we are crossing out the 1st, 3rd, 5th etc. of the numbers remaining, we are crossing out all the odd multiples of 2, that is, numbers of the form k x 2 where k is an odd number, so we are left with the even multiples of 2, which are the multiples of 4, and where the first number remaining is 2 x 2
We then cross out the odd multiples of 4, leaving the even multiples of 4, which are the multiples of 8, and the first number remaining, being the first even multiple of 4, is 2 x 4 = 2 x (2 x 2) = (2 to the power of 3).
Clearly after each step the smallest remaining number is a power of 2. The largest power of two in the given range is 512 so this will be the last number left.