环形淘汰射击

应站在 1 号位。

这是经典 Josephus 问题（步长 2）。当总人数是 $2^m$ 时，最后存活位置恒为 1。

因为 $1024=2^{10}$，所以答案是 1。

---

Original Explanation

1

Solution

Let us try a few numbers.

1. For $n=2$, the $1^{\text{st}}$ person survives by shooting the $2^{\text{nd}}$.
2. For $n=4$, the $1^{\text{st}}$ person survives again.

Let us define "round" as one complete circle of shootings. Logically it makes sense that the first person always survives as the number of people keeps halving evenly in each round. Let us prove this by induction.

Let $S(n)$ be the safe position for a given $n = 2^{k}$

Base Case: When $k = 0$, we have one pirate $(2^0 = 1)$. The only pirate, which is the first, is the last to survive, so $S(1) = 1$.

Inductive Step: Assume our hypothesis is true for $k = m$. That is, $S(2^m) = 1$.

We need to prove this holds for $k = m + 1$, i.e. for $n=2^{m+1}$ pirates.

In the first round of shooting, all pirates in even-numbered positions are eliminated. Therefore, at the end of the first round, there are $2^m$ pirates left, all in odd-numbered positions.

Now, the pirates' positions are reset, and the first pirate (who was initially in position 1) is still in position 1.

Therefore, we now have a circle of $2^m$ pirates, starting from the first pirate. The inductive hypothesis states that the first pirate will survive till the end.

Thus, $S(2^k) = 1$ is true for any integer $k\ge 0$.

For $n = 1024 = 2^{10}$, the position of the surviving pirate would still be the $1^{\text{st}}$ position. Therefore, someone should stand in the first position to survive.

---

Trivia

1. This problem is called "Josephus problem", named after Flavius Josephus, a Jewish historian living in the $1^{\text{st}}$ century. Allegedly, he and his 40 soldiers were trapped in a cave by Roman soldiers. Preferring suicide instead of being captured, they decided to form a circle and, kill every third soldier until none remained. Josephus, who preferred to surrender, managed to arrange the order of the soldiers in the circle so that he and another man were the last two survivors. At this point, they surrendered to the Romans rather than killing themselves.

2. If $n$ is not a power of $2$, then we can use a formula. Find the largest $m$ such that $2^m < n$.

   Take $l = n-2^m$. Then the safe position is $2 \cdot l + 1$.

   For example, in the case of 100 pirates (the original puzzle), $N=100, 2^m=64, m=6, l = 36 \implies 2 \cdot l + 1 = 73$

   The formal proof for this formula can be found here (Wikipedia).