Dropping Out Evens

Algebra Level 2

I've written down the first 1000 positive integers: $1, 2, 3, \ldots, 1000.$

Step 1: Remove all the numbers on even positions, leaving only 500 numbers.
Step 2: Repeat Step 1 , and there are now 250 numbers left.
Step 3: Repeat Step 1 , and there are now 125 numbers left.
$\quad \vdots$
Step $N$ : Repeat Step 1 , and there is just a single number left.

Suppose that $N$ is the minimum number of times Step 1 needs to be executed until there is just one number left.

What can we say about $N?$

2^N = 1000

2N \geq 1000

2^N > 1000

1 solution

Marta Reece
Jul 9, 2017

If we started with $2^N$ , we would take $N$ steps and end with a single number.

But $1000$ is not in the format $2^N$ .

When we get to $125$ , taking out evens will not take out half the numbers. $1$ will stay, and so will $125$ . The number will go down to $\frac{126}2$ rather than $\frac{125}2$ . It will therefore be larger then one half of the previous number.

So taking $2^N$ will come up with a larger number than $1000$ . (As a matter of fact it will be $1024=2^{10})$ .

Dropping Out Evens

1 solution

0 pending reports