圓桌上1000個人輪流開槍，最後活下來的是幾號？
圓桌上有1到1000號，1號右手邊是2號，左手邊是1000號。1號開槍打死2號，把槍交給3號，3號打死4號交給5號。。999號打死1000號後把槍交給1號，繼續循環。最後留下來的是幾號？
了解到這是約瑟夫環，解可以寫成
977號。小學數學。
問題轉化。
（1）如果是只有2人，誰活？1號啊！
（2）那麼，4個人呢？
第一輪開槍結束，只剩2人，槍在1手中，所以顯然是1號；
（3）8個人呢？第一輪開槍結束，只剩4人，槍在1手中，由（2）討論，我們知道最後是1號；
……
（9）512人，第一輪開槍結束，只剩256人，槍在1手中，所以顯然是1號；
那麼1000……什麼，1000不是2的整數次方？
那想辦法划到512人去啊！
所以，考慮槍剛遞到誰手上，還剩的人數，剛好是512人即可。這個時候開槍的人，可以存活到最後。
顯然，到這個人手上時，已經開了488槍，那這個人應該是488*2+1=977號。
答，最後活下來的，是977號。受眾知友的啟發，我突然有了一個思路。
一張圓桌，每一輪殺死近一半的人，那麼，從剩下的人的編號來研究一下，會怎麼樣呢？
第一輪完，剩1、3、5……997、999，編號形成以1開始，依次遞增2的等差數列，共500個。
第二輪完，剩1、5、9……993、997，編號形成以1開始，依次遞增4的等差數列，共250個。
第三輪完，剩1、9、17……985、993，編號形成以1開始，依次遞增8的等差數列，共125個。
第四輪，介於上一輪剩下的人數為奇數，所以這一輪的最後，1號會死在993號的手上，所以剩17、33、49……977、993，編號形成以17開始，依次遞增16的等差數列，共62個。
第五輪完，剩17、49、81……977，編號形成以17開始，依次遞增32的等差數列，共31個。
第六輪完，介於上一輪剩下的人數為奇數，所以這一輪的最後，17號會死在977號的手上，所以剩81、145、209……977，編號形成以81開始，依次遞增64的等差數列，共15個。
第七輪完，介於上一輪剩下的人數為奇數，所以這一輪的最後，81號會死在977號的手上，所以剩209、337、465……977，編號形成以209開始，依次遞增128的等差數列，共7個。
第八輪完，介於上一輪剩下的人數為奇數，所以這一輪的最後，209號會死在977號的手上，所以只剩465、721、977三個（等差為256）。
第九輪，465打死721後被977打死。
所以，977成為了最後的王者。
手機打字不易，大佬們給個贊可好？
如果有和我一樣邏輯能力為0,看不懂邏輯推理的朋友的話...
我們來玩找規律吧!
還有我想換個情景,不想回答無意義的應用題...
Josephus和n-1個大鬍子被特警包圍了, 然後他們決定去見真主.
他們圍城一個圈,從首領(1號)開始輪流槍斃自己右手邊的人.
但是 Josephus 是卧底他不準備死,那麼他應該站在哪個位置?
- 1個人...一個人就算了,槍斃自己嗎
- 2個人,槍斃2號結束,倖存者1號
- 3個人,槍斃{2,1}結束,倖存者3號
- 4個人槍斃{2,4}變成2人情形,槍斃3號結束,倖存者1號
- .........................................
好,現在問題轉化為簡單的找規律了...
可以發現以2的冪劃分就是奇數....所以偶數就抱歉了
於是我們從 開始數
個人
然後換元令
於是
這個公式給出了高贊的過程
總人數t=1000,減去低於1024的冪512,然後翻倍加一
附加題 Anti-Josephus-Problem:
Josephus 深得首領器重,首領讓Josephus站自己旁邊(2號),然後徵求他的意見,應該隔幾個人槍斃.
如果你是 Josephus ,你必定能活下來嗎? 你應該怎麼回答?
為什麼2號要參加這個遊戲？
修改答案。。。
假設有1024人，當開槍殺死24人後，也就是49號接槍時，還剩1000人。這時讓49成為新1號，將原1 3 5 7……47號一共24人移到最後面，使之成為一條1000人的新隊伍，這時原1號，也就是幸運兒，會成為現在的1024-48＋1＝977號。
——以下是原答案——
當然是977號啦~
易知：當人數x=2、4、8、16、32、64....即2的n次方時，活下來的永遠是1號
那麼現在有1000個人，活下來的是誰呢？
由前面的易知得知，當n=10時，x=1024，我們可以理解成在一號前面再排24個人，我們給他們編號為-23、-22、-21……-1、0。現在讓-23開第一槍，打死-22，接著-21接過槍打死-20，由此循環，最終活下來的一定是-23。
那麼問題來了，-23是誰呢？
因為槍打完一圈是要輪到一號的，因此可以認為隊伍是繞成一個圓環的。我們可以這麼理解：把977號--1000號這24個人移到1號前面，使他們成為-23號--0號，這樣977號就成了那位幸運的-23號。
所以活下來的是977號
N個人，{p0, p1, p2 ... }
設 X(N) ：X 是活下來的那位：pX
這個 X(N) 怎麼算？
首先 X(1) = 0 （N=1，一個人，活下來的只能是他）
然後 X(2N) = 2X(N)
為什麼？
2N個人，走完一輪，偶數都殺死右邊奇數。然後回到第一個人 p0。
活下來的還有N個人{p0,p2,p4...}，所以第二輪相當於 X(N) 的情況。
但是要乘以2，把 {p0,p1,p2...} 映射到 {p0,p2,p4...}
而且 X(2N+1) = 2X(N) + 2
為什麼？
2N+1 個人，走完一輪，偶數豆沙四右邊奇數。但是最後一個人p2N殺死p0，所以輪到了p2。
活下來的還有N個人{p2,p4,p6...}，所以第二輪也相當於 X(N) 的情況。
但是要乘以2，再加2，把 {p0,p1,p2...} 映射到 {p2,p4,p6...}
這三個規則已經夠了。
比如：
X(1000)
= 2X(500)
= 4X(250)
= 8X(125)
= 16X(62) + 16
= 32X(31) + 16
= 64X(15) + 64 + 16
= 128X(7) + 128 + 64 + 16
= 256X(3) + 256 + 128 + 64 + 16
= 512X(1) + 512 + 256 + 128 + 64 + 16
(結束了，總共九輪）
= 0 + 512 + 256 + 128 + 64 + 16
X(1000) = p976
[實際上是第977的人活下來，因為我們是從第一個人p0開始]
或者：
X(2017)
= 2X(1008) + 2
= 4X(504) + 2
= 8X(252) + 2
= 16X(126) + 2
= 32X(63) + 2
= 64X(31) + 64 + 2
= 128X(15) + 128 + 64 + 2
= 256X(7) + 256 + 128 + 64 +2
= 512X(3) + 512 + 256 + 128 + 64 + 2
= 1024X(1) + 1024 + 512 + 256 + 128 + 64 + 2
(結束了，總共十輪）
= 0 + 1024 + 512 + 256 + 128 + 64 + 2
X(2017) = p1986 (第1987的人)
好吧，全部換成二進位。。。
1000 的二進位：1111101000
X(1111101000)
= 10X(111110100)
= 100X(11111010)
= 1000X(1111101)
= 10000X(111110) + 10000
= 100000X(11111) + 10000
= 1000000X(1111) + 10000000 + 10000
= 10000000X(111) + 10000000 + 1000000 + 10000
= 100000000X(11) + 100000000 + 10000000 + 1000000 + 10000
= 1000000000X(1) + 1000000000 + 100000000 + 10000000 + 1000000 + 10000
= 0 + 1000000000 + 100000000 + 10000000 + 1000000 + 10000
X(1111101000) = p1111010000
i.e. X(1000) = p976
hmmm.... 二進位，這兩個數字長得很像啊。（而且這個後綴的積累方式很像）
2017呢。。。
X(11111100001) = p11111000010
i.e. X(2017) = p1986
這個機制，不就是把二進位大部分0,1都保留下來嗎？
只是前面的1不要，後面多加一個0。
又符合上面三個recursive規則
X(1) = 0
X(10N) = X(1abc...xyz0) = abc...xyz00 = 10X(1abc...xyz)
X(10N + 1) = X(1abc...xyz1) = abc...xyz10 = 10X(1abc...xyz) + 10
去掉最大的二進位1是什麼概念？
N -&> N - 2^floor(log(2,N))
後面加一個0是什麼概念？
N -&> 2N
所以我們終於可以確定： X(N) = 2(N - 2^floor(log(2,N)))
X(1000)
= 2(1000 - 2^floor(log(2,1000)))
= 2(1000 - 512)
= p976
（好吧，還是要+1, 因為我們都從0開始算的）
不好意思，剛看到問題，沒有整理，寫得比較亂；我也不會用latex
如果改規則，改成每個人開槍時殺死右邊的k個人，這就有k+1個recursive條件，要改成(k+1)進位空間去理解。
#跑題#
一號確實開槍幹掉了二號，本來應該把槍交給三號的，結果眾人突然齊刷刷地開口說『我覺得一號可以多干一屆』，場面一下子就尷尬了，三號只好表示『我無意接槍』然後示意一號親自開槍幹掉了四號。之後嘛，三號還不知死活，後面的誰接槍事就更不知道了
假設原來有1024個人，已經死了24個
於是時光倒流
把24個人復活一下看看槍在誰手上，
24個人插了23個空，
還原事故現場，
倒數第23個人正拿著槍，
遊戲開始。。
2的n次方數一定是第一個活著的。
倒數23就是現在的1號。
1000-23=977
我又最笨的方法推理了兩個小時左右
1. 將1000寫成2進位得1111101000
2. 將1111101000最高位移到末位1111010001
3. 1111010001轉為十進位得977
僅適用於n=2
第一輪，1號先開槍，剩下1、3、5……995、997、999，最後是999號殺1000號（此次人數為偶數，倒數第二位殺死倒數第一位，下同），槍交給1號，一共剩下500人；
第二輪，1號先開槍，剩下1、5、9……989、993、997，最後是997號殺999號，槍交給1號，一共剩下250人；
第三輪，1號先開槍，剩下1、9、17……977、985、993，最後是993號殺997號，槍交給1號，一共剩下125人；
第四輪，1號先開槍，剩下17、33、49……961、977、993，最後是993號殺1號（此次人數是奇數，倒數第一位殺死最前面的一位，下同），槍交給17號，一共剩下62人；
第五輪，17號先開槍，剩下17、49、81……913、945、977，最後是977號殺993號，槍交給17號，一共剩下31人；
第六輪，17號先開槍，剩下81、145、209……849、913、977，最後是977號殺17號，槍交給81號，一共剩下15人；
第七輪，81號先開槍，剩下209、337、465、593、721、849、977，最後是977號殺81號，槍交給209號，一共剩下7人；
第八輪，209號先開槍，剩下465、721、977，最後是977號殺209號，槍交給465號，一共剩下3人；
最後一輪，剩下977號(╯°Д°)╯︵┻━┻scala&> def T(n: Int): Int = if (n == 1 || n == 2) 1 else if ( n % 2 == 0) 2 * T(n / 2) - 1 else 2 * T((n - 1) / 2) + 1
T: (n: Int)Int
scala&> T(1000)
res20: Int = 977
隔一個殺一個，非環狀約瑟夫抽殺最簡單，是小學奧數的學習內容。環狀的要難一點，是小學奧數高端學生學習內容。
隔兩個殺一個就麻煩了，尤其是非環狀，大學生普遍跪。
隨便寫代碼跑了下：
輸出： the winner is 977int main()
{
std::list&
for(int i=0;i&<1000;i++)
{
people.push_back(i+1);
}
while(people.size()&>1)
{
int criminal=people.front();
people.pop_front();
people.pop_front();
people.push_back(criminal);
}
std::cout&<&<"the winner is :"&<&
謝邀。結果應該是977。
Interesting problem! 感覺以前好像見過， 突然發現至今不會解析解 。 希望有數學大神能給出精妙解答（可能跟1000有關係？）
下面是我的一個演算法。 主要是基於每次循環後 是否能被2整除討論的。
# method 2
# setup
import numpy as np
n = 1000
a = [1]*n
res = 0 # indices we wanna know
k = 1
while n &> 1:
if n % 2 == 0:
n = n/2
else:
res = res + 2 * k
n = (n - 1)/2
k = 2 * k
print(res + 1) # 977
這個演算法是 的， 並且可以任意跟換n， 關鍵點是跟新array中的首項， 因為它才是留下來元素的起點。
可以和比較直接的遍歷方法進行比較（感覺應該是 , 當然還可以簡便些。）
# method 1
# setup
import numpy as np
n = 1000
a = np.ones(n, dtype = "int")
def next_nonzero(i, A, m):
"""find the next nonzero indice"""
for k in range(i + 1, m):
if A[k] != 0:
return k
for k in range(0, i):
if A[k] != 0:
return k
# remove nonzero element one by one
i = 0
while np.count_nonzero(a) &> 2:
j = next_nonzero(i, a, n)
i = next_nonzero(j, a, n)
a[j] = 0
print(i + 1) # 977
以上code中nonzero的element就是榮幸活下來的。
希望各路大神可以提出建議並且有更好的解答。
好的， 覺得此問題可以終結了。 ( ′? ??") 。 這是Josephus problem。 詳見
Josephus problem
本題就是977.
顯而易見，第一圈下來消滅掉了所有偶數號，剩500人，並且槍回到1號
現在把所有人重新編號（1~500）
一圈下來同樣消滅掉所有偶數號，剩250人
同上一步，現在剩125人
繼續
很顯然，第124個人被幹掉之後，剩63人
槍會被交給最後一個人，然後1號就會被幹掉，接著是3號，不難想現在是消滅奇數項。
為了統一消滅偶數，我們把最後一個人消滅1號後算作一圈，把之前的號往前推1位，現在就是消滅偶數了。當然，剩的就是62個人了
所以又被消滅掉31個，剩31個，槍回到第一個人，現在消滅偶數
剩31個，和剩125個時一樣
然後15,7,3,1
emmmmmm，不過現在推號數成了個問題，慢慢來吧
〇：1,2,3,…,999,1000(1000)n+1
一：1,3,5,…,997,999(500)2n+1
二：1,5,9,…,993,997(250)4n+1
三：1,9,17,…,985,993(125)8n+1
四：17,33,…,977,993(62)16n+1+16
五：17,49,81,…,945,977(31)32n+1+16
六：81,145,209,…,913,977(15)64n+1+16+64
七：209,337,465,…,849,977(7)128n+1+16+64+128
八：465,721,977(3)256n+1+16+64+128+256
九：977(1)512n+1+16+64+128+256+512
對，你一定注意到了後面的式子
我們把這個方法可以歸納為：
一組人編號的通項公式為n+1(n=0,1,2,…)
Ⅰ如果這一組人數是偶數，人數直接除以2，通項公式中n的係數乘以2（如〇到一）
Ⅱ如果這一組人數是奇數，人數減1除以2，通項公式中n的係數乘以2，常數項中加上乘以2之後的n的係數（如三到四）
並且每一步的影響都要累計下來
因為最後只有一個人，把n=0代入最後的通項公式，即為最後的編號（你可以試試代一下上面第九步）
現在我們來這樣試一下：
1024
因為1024是2^10，每次都能整除，所以只用一直執行Ⅰ，最後的通項公式就是2^10n+1，所以1號存活
1023
因為1024是2^10-1，每次都不能整除，所以只用一直執行2，最後的通項公式就是2^9n+1023，所以1023號存活
100(n+1)
50(2n+1)
25(4n+1)
12(8n+1+8)
6(16n+1+8)
3(32n+1+8)
1(64n+1+8+64)
所以73號存活
至於為什麼
因為是隔一人給（開）槍，所以（這裡要簡單地推一下）每次係數乘以二
如果上次人數是偶數，槍會回到第一個人，首項不變，所以不加
如果上次人數是奇數，第一個人就會死，首項就變成原來第二個人，所以需要加中間間隔的數號，也就是n的係數（例如1,65,…係數就是64，中間間隔64，1（原第一項）死後第一項就加64）
沒時間了，說得很粗糙，大致地理解一下吧
對吼，直接用二進位表示1000=1111101000(2)
977=1111010001(2)
也就是說把二進位中第一位移到最後一位就行了。。。
感覺高票答案說的都有些太過複雜了，我來說說我的解答
不難知道
若是恰好有2的n次方個人，那麼活下來的人就一定是1號
那麼我們假設 共有1024個人 ，若要場上只剩下1000個人，那麼必須死去24個人，想要死去24個人，那麼就需要有48個人參與這個遊戲，所以，當47號開槍殺死48號時，49號露出了猥瑣且陰暗的笑容，這時場上就剩1000人了
此時 編號重排
49號成了1號，50號成了2號....以此類推
這個時候就出現了次方的輪迴，不管怎樣 活下來的都是1號，也就是977
所以 答案是977
這個題目從本質上來看，還是應該考慮二進位。首先1000＝（1111101000）2
其中n＝（abc）p，表示p進位下n的表示為（abc）
我們將一號視作第一次開槍的人。當槍被數碼較大的人交給數碼較小的人時，稱作過了一個回合。（比如說1、3、5……這些人開槍打死2、4、6……然後1再拿到槍，就過了一個回合）
假設現在到了一個新的回合，場上有
k＝（a1a2……am）2
個人存活。（其中1、2、……、m為下標）
設他們是A1、A2、……、Ak
顯然，若am＝1，則A1必死，且Ak存活。
若am＝0，則A1存活，Ak必死。
而且這個回合死去了[（k＋1）/2]個人。其中[x]表示x向下取整。
於是經過這個回合，場上只剩下k`＝（a1a2……a（m-1））2
（其實就是將k的二進位表示下最後一位數碼抹去）
回到原題，1000＝（1111101000）2
那麼最後五個回合的最後一個人一定不會死，所以他就是活到最後的那個人。
另外，如果對這1000個人進行賦值1-1000
那麼顯然第m個回合過後，存活的人一定模2的m次方同餘。（否則他將被前一個人殺死）
前三個回合1號一直存活，那麼三個回合之後，數字最大的那個人模8餘1。他是993號。
第四個回合1號死亡，993號存活。所以這個回合除1外，所有模16餘1的人存活。那麼數字最小的人是17號。
第五個回合17號存活，所以這個回合剩餘的人模32餘17。數字最大的人為977。
最後1000＝（1111101000），接下來的五個回合977號都活了下來。所以他就是活到最後的那個人。
用類似的方法可以推廣到n的情況。看了各位的回答終於想明白了，我也試著說說。
按照規則，人數是2的正整數次冪的情況下，永遠是第一個開槍的剩下，這個就不多解釋了。
那麼我們再來考慮人數是1000的情況。
這個情況可以認為是從距離這個數字最近的2的整數次冪即1024發展而來：
1024個人排排坐吃槍子。他們每人一個編號，就叫做a1號，a2號……a1024號好了。從a1號幹掉a2號開始玩，可以預見，最終必然是a1號勝出。
模仿@岳承宇 的思路，用mathematica來湊個熱鬧
推薦閱讀：
※此圖像的參數方程應該是什麼？
※數學中的「數」如果按照其所描述的範圍，由小到大應該如何排列？
※為什麼對任何 N，N 是兩個平方數的和 <=> N^3 也是兩個（其他）平方數的和？
※已知f(f(x))，在怎樣的條件下，可求f(x)？
※如何證明加法交換律？