2
$\begingroup$

Numbers 1, 2, 3 ……, 2009 are written in the natural order. Numbers in odd places are stricken off to obtain a new sequence. Numbers in odd places are stricken off from this sequence to obtain another sequence and so on, until only one term 'a' is left. Then find 'a'.

Please help explain the process of doing this.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Better write them as $1, 10, 11, 100, \ldots, 11111011001$ $\endgroup$ – peterwhy Dec 27 '14 at 15:39
13
$\begingroup$

By writing numbers $1$ to $2009$ in binary form: $$1, 10, 11, 100, 101, 110, 111, 1000,1001 \ldots, 11111011001$$

the procedure should be clearer.

The first round, numbers of last bit of $1$ are removed. The second round, numbers of the second last bit of $1$ are removed. Keep doing this, the last remaining number is the number in the form $100\ldots000_2$ between $1$ and $2009_{10}$ with the longest string of $0$'s, or $1024_{10}$.

|cite|improve this answer
$\endgroup$
6
$\begingroup$

Hint: In the first pass, all terms of the form $2n+1$ are struck off ($n\ge 0$), leaving only terms of the form $2n$. In the second pass, all terms of the form $2(2n+1) = 4n+2$ are struck off, leaving only terms of the form $4n$. And so on. How many passes are there, and what terms remain after the last pass?

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Then after this I believe the only remaining terms are in the form 8n. This continues in geometric progression until the terms left are in the form 1024n, leaving 1024 as the last term. I believe this is the correct answer - do correct me if I'm wrong. $\endgroup$ – Shreyash Chaudhari Dec 27 '14 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.