Relation/ formula to Find the last person standing after removing people alternatively from a line?

Question

Given N number of people, each marked as a number starting from $1$ through N, standing in a straight line where you remove folks alternatively from a line.

For example in iteration 1: You would remove $1,3,5...$

Iteration $2 : 2,6,10...$

etc. until there is one person standing.

Find the index of the last person standing for a given value of N.

score 0 · Answer 1 · answered Aug 05 '15 at 17:30

0

$$2^{\lfloor\log_2 N\rfloor}$$

answered Aug 05 '15 at 17:30

Intelligenti pauca

50,470
4
42
77

You might want to add an explaination. – wythagoras Aug 05 '15 at 18:21
See the answer by Divergent Queries. I gave no explanation because the OP gave none. – Intelligenti pauca Aug 05 '15 at 18:30

score 0 · Accepted Answer · answered Aug 05 '15 at 17:32

We can look at the process like this:

Remove the numbers of the form $1+2n$. We are left with multiples of $2$.
Remove the numbers of the form $2+4n$. We are left with multiples of $4$.
Remove the numbers of the form $4+8n$. We are left with multiples of $8$.
Remove the numbers of the form $8+16n$. We are left with multiples of $16$.
Etc.

Therefore, the last number standing is the highest power of $2$ less than or equal to $N$.

Relation/ formula to Find the last person standing after removing people alternatively from a line?

2 Answers2