Question

Here is a new puzzle 100 people standing in a circle in an order 1 to 100. no.1 has a sword 🔪 he kills next person (i.e. no. 2) and gives sword to next to next (i.e no.3). all of them do the same until only one person survives. which number survives at the last? warning- not as easy as it appears.

Answer 1

Suppose there are n people in the circle, and we know the answer for all numbers smaller than n.

If n=2kn=2k is even, then every second person gets killed, and we are left with the kk numbers 1,3,5,…,n−11,3,5,…,n−1.  We can reduce this to a problem with kk people, by mapping the numbers 1,3,5,...,n−11,3,5,...,n−1 onto 1,2,3,...,k1,2,3,...,k.  If the solution for kk people is the person numbered ii, then the solution for nn people is 2i−12i−1, since the ith number in the sequence is 2i−12i−1.

If n=2k+1n=2k+1 is odd, then we are left with the kknumbers 3,5,…,n3,5,…,n.  If the solution for kk people is the person numbered ii, then a similar reduction shows the solution for nn people is 2i+12i+1.

Let SkSk be the solution for kk people.

Then S100=2S50−1S100=2S50−1
=2(2S25−1)−1=4S25−3=2(2S25−1)−1=4S25−3
=4(2S12+1)−3=8S12+1=4(2S12+1)−3=8S12+1
=8(2S6−1)+1=16S6−7=8(2S6−1)+1=16S6−7
=16(2S3−1)−7=32S3−23=16(2S3−1)−7=32S3−23
=32(2S1+1)−23=64S1+9=32(2S1+1)−23=64S1+9
=64∗1+9=64∗1+9
=73=73