# Crossing out every second number

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?

• The wording of this puzzle was, IMO, extremely unclear. Like msh, I had thought you started at 1 and then crossed out the second number, 2, and so on. But it seems the intended answer was to cross out 1, the first number. Perhaps a short example would have explained to not confuse answerers? – Sciborg Dec 9 '20 at 1:54
• I've added an example. – Dmitry Kamenetsky Dec 9 '20 at 1:59

I think the number that remains is

512

Reasoning

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.

• Snap! Only a few seconds in it – lxop Dec 9 '20 at 0:40
• Yep you got it! – Dmitry Kamenetsky Dec 9 '20 at 0:51

The last number will be

512

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.

• Also correct, but @hexomino was a fraction earlier. – Dmitry Kamenetsky Dec 9 '20 at 0:52

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.

• Each run you cross out the first number too. So you will cross out 1 on the first run. – Dmitry Kamenetsky Dec 9 '20 at 1:58
• No, @DmitryKamenetsky, each run you cross out "every second number", not the first. – msh210 Dec 9 '20 at 2:03

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.