返回题库

最后幸存者

Last One Standing

专题
Brainteaser / 脑筋急转弯
难度
L5

题目详情

假设有 100 个人围成一圈，编号为 1 到 100。1 号拿到一把剑并淘汰 2 号；3 号捡起剑再淘汰 4 号，以此类推。这个过程持续进行，直到只剩下一个人。最后幸存者是谁？

英文原题

Suppose there are 100 people standing in a circle numbered 1-100. Person 1 is given a sword and uses it to slay person 2. Person 3 picks up the sword and uses it to eliminate person 4 and so on. This continues until just one person remains. Which person is the survivor?

解析

这是步长为 2 的经典 Josephus 问题。

对 nn 个人、每次淘汰下一个人，幸存者位置满足
J(n,2)=2ℓ+1,J(n,2)=2\ell+1,
其中
n=2m+ℓ,n=2^m+\ell,
且 2m2^m 是不超过 nn 的最大 2 的幂。

这里 n=100n=100，因为
26=64≤100<128=27,2^6=64\le100<128=2^7,
所以
ℓ=100−64=36.\ell=100-64=36.

于是
J(100,2)=2⋅36+1=73.J(100,2)=2\cdot36+1=73.

因此最后的幸存者是
73.\boxed{73}.

英文解析

This is the classic Josephus problem with n=100n=100 and step k=2k=2.
We can write
n=2m+ℓn = 2^m + \ell
where 2m2^m is the largest power of 22 not exceeding nn.
The survivor J(n,2)J(n,2) is given by
J(n,2)=2ℓ+1.J(n,2) = 2\ell + 1.

For n=100n=100, we have 26=64≤100<128=272^6 = 64 \leq 100 < 128 = 2^7,
so m=6m=6 and ℓ=100−64=36\ell = 100 - 64 = 36.
Hence
J(100,2)=2⋅36+1=73.J(100,2) = 2 \cdot 36 + 1 = 73.

Another quick method: \text{Another quick method: }
10010=11001002.Move the leading 1 to the end to get 10010012, which equals 73.100_{10} = 1100100_2. \\ \text{Move the leading $1$ to the end to get } 1001001_2, \\ \text{ which equals } 73.

Answer=73\text{Answer} = \boxed{73}