There are 1000 people standing in a row. They are numbered as 1,2,...,1000. There is a unique demon who eats only the persons which are standing on odd positions. It means that after his first round the person numbered 2 will come at position 1 and the one at 4 will come at 2 and so on. So what was the number assigned to the person which is left at last ?
A little investigation should convince you that for n people, the person numbered 2^k will be left standing, where k is the largest number such that
2^k <= n
To find the number assigned to the person who is left at last, we can approach this problem using a step-by-step elimination process.
Step 1: Eliminate all persons standing on odd positions in the first round.
- After the first round, only persons standing on even positions will remain in the row.
Step 2: Recreate the row with the remaining persons.
- The original row of 1000 people will now be reduced to a new row with only 500 people.
Step 3: Repeat Steps 1 and 2 until only one person is left in the row.
- Continue alternating between eliminating persons on odd positions in each round, and reducing the number of people in the row by half each time.
Let's go through the process step by step:
Round 1: Eliminate persons on odd positions in the row.
- In this round, eliminate the persons numbered 1, 3, 5, 7, and so on until 1000. Only the persons numbered 2, 4, 6, 8, and so on will remain.
- The new row will have 500 people numbered as 2, 4, 6, 8, ..., 1000.
Round 2: Recreate the row with the remaining persons.
- The new row will now have 250 people numbered as 2, 4, 6, 8, ..., 500.
Round 3: Eliminate persons on odd positions in the row.
- In this round, eliminate the persons numbered 2, 6, 10, 14, and so on until 500. Only the persons numbered 4, 8, 12, 16, and so on will remain.
- The new row will have 125 people numbered as 4, 8, 12, 16, ..., 500.
Round 4: Recreate the row with the remaining persons.
- The new row will now have 62 people numbered as 4, 8, 12, 16, ..., 124.
Round 5: Eliminate persons on odd positions in the row.
- In this round, eliminate the persons numbered 4, 12, 20, 28, and so on until 124. Only the persons numbered 8, 16, 24, 32, and so on will remain.
- The new row will have 31 people numbered as 8, 16, 24, 32, ..., 124.
Round 6: Recreate the row with the remaining persons.
- The new row will now have 15 people numbered as 8, 16, 24, 32, ..., 120.
Round 7: Eliminate persons on odd positions in the row.
- In this round, eliminate the persons numbered 8, 24, 40, 56, and so on until 120. Only the persons numbered 16, 32, 48, 64, and so on will remain.
- The new row will have 7 people numbered as 16, 32, 48, 64, 80, 96, and 112.
Round 8: Recreate the row with the remaining persons.
- The new row will now have 3 people numbered as 16, 32, and 48.
Round 9: Eliminate persons on odd positions in the row.
- In this round, eliminate the person numbered 16. Only the persons numbered 32 and 48 will remain.
- The new row will have 2 people numbered as 32 and 48.
Round 10: Recreate the row with the remaining persons.
- The new row will now have 1 person numbered as 32.
After the elimination and recreation process, the person left at last will be the one numbered as 32.