现实 中 的 鱿鱼 游戏 ， 你 能 成功 活 到 最后 吗 ？—— 约瑟夫 问题
各位 同學 大家 好 我 是 李永樂 老師
最近 有 一個 熱播 的 韓劇 《 魷魚 遊戲 》
講述 的 一群 為 生活 所困 的 人
為 了 巨額 獎金 而 參加 生死 逃殺 遊戲 的 故事
有 小朋友 就問 我 說
如果 有 一天
他 也 參加 了 這樣 的 一個 大逃殺 遊戲
有沒有 什 麽 辦法 能夠 在 遊戲 中 生存 下來 呢
其實 在歷史上 這樣 的 遊戲 還 真的 發生 過
今天 我們 就 來講 述 一個 兩千年 以前
發生 在 古羅馬 時代 的 生存 逃殺 遊戲
約瑟夫 問題
約瑟夫 是 誰 呢
約瑟夫 是 古羅馬 時代 的 一個 猶太 的 歷史學家
那 麽 約瑟夫 曾經 領導 過
猶太人 反抗 羅馬帝國 的 統治
那 麽 他 帶領 了 一些 士兵
在 一個 要塞 堅守 了 47 天
結果 還是 被 羅馬 士兵 圍困 到 一個 山洞 裏邊 了
他 手下 有 40 名 士兵
這些 士兵 們 都 說 我們 寧可 自殺 也 不 投降
這個 時候 約瑟夫 本人 並 不想 自殺
他 想 向 羅馬 士兵 投降 但是 他 又 不敢 說
怎 麽 辦 呢
於是 他 就 對 士兵 說
自殺 不 符合 我們 猶太人 的 傳統
所以 我們 可以 這樣 做
我們 41 個人 圍成 一個 環兒
然後 1 號 士兵 殺死 他 旁邊 的 2 號 士兵
3 號 士兵 殺死 他 旁邊 的 4 號 士兵
39 號 士兵 殺死 40 號 士兵
41 號 士兵 再 去 殺死 還活 著 的 1 號 士兵
如此 類推
最終 只 剩下 一個 士兵
這個 士兵 再 自殺 就 可以 了
經過 幾輪 之後
這 約瑟夫 和 另外 一位 士兵 還活 著
約瑟夫 就 勸說 這位 士兵
跟 他 一起 向 羅馬 士兵 投降
於是 他們 就活 了 下來
約瑟夫 還把 這個 故事 寫 在 了 他 的 日記 之中
那 今天 的 這個 問題
就 被 我們 稱之為 約瑟夫 問題
約瑟夫 問題
如果 我們 討論 得 普遍 一點 就是 這樣 的
說 一共 有 N 個人
有 N 個人 圍成 一個 環兒 圍成 一個 環兒
然後 每隔 幾個 人 殺掉 一個 人
我們 先說 最 簡單 的 情況
比如說 每 兩人 每 兩人 我們 殺 一人
然後 這樣 一輪 一輪 地殺 下去
直到 最後 剩下 一個 人
那 麽 我 就 想問 最後 剩下 的 是 誰
這個 問題 我們 就 稱 之 為 約瑟夫 問題
這個 約瑟夫 問題 到底 該 怎 麽 解 呢
可能 剛 拿到 我們 手裏 我們 也 不 清楚
於是 我們 要 試一試 對 吧
怎 麽 試 呢
我們 從 最 簡單 的 情況 開始
比如說 我們 用 字母 N 來 表示 這個 人數
然後 我們 最後 剩 的 這個 人 我們 管 他 叫 f
我們 來 琢磨 琢磨
在 不同 的 情況 下 最後 會 剩下 幾號 人
如果 一共 就 只有 一個 士兵 是 吧
那 麽 每 兩個 人殺 一個 人 最後 肯定 就 剩 他 自己
因為 一共 就 只有 他 自己
那 麽 假如 有 兩個 士兵 呢
1 號殺 了 2 號
所以 誰 會 剩下
1 號會 剩下 對 不 對
那 如果 有 3 個 士兵 呢
1 號殺 了 2 號 3 號會 殺 了 1 號 對 吧
所以 最後 剩 的 是 3 號
如果 有 4 個 士兵 呢
1 號殺 2 號 3 號殺 4 號
然後 1 號又殺 了 3 號
所以 最後 剩 的 還是 1 號
如果 有 5 個 士兵 呢
1 號殺 2 號 3 號殺 4 號
5 號殺 1 號 3 號殺 5 號
所以 最後 剩 的 是 3 號
如此 類推 我們 可以 寫出 很 多種 情況 來
好 我們 這個 表格 就 補完 了
我 計算 了
從 1 個人 一直 到 16 個人
最後 余下 的 人 的 情況
咱們 來 觀察 一下 這個 表格
你 發現 了 什 麽 特點 嗎
首先 就是 不管 你 有 幾個 人
最後 剩下 的 那個 人 的 編號 一定 是 一個 什 麽 數
你 看 1 1 3 1 3 5 7
1 3 5 7 9 11 13 15 1
是不是 都 是 奇數
所以 我們 的 特點
首先 余下 的 人 f 一定 是 奇數 f 一定 是 奇數
剩 不下 偶數
為什 麽 剩 不下 偶數 呢
因為 第一輪 的 時候 每 兩個 人殺 一個 人
所以 2 4 6 8 10... 這種 偶數
全都 被 殺掉 了 對 不 對
所以 肯定 剩 的 不是 偶數 一定 是 奇數
這是 其一
你 還能 找到 什 麽 特點 嗎
你 仔細 看 很 多種 情況
最後 剩 的 是 1 號 是不是
你 看 剩 的 是 1 號
剩 的 是 1 號
剩 的 是 1 號
剩 的 是 1 號
哪些 人數 最後 會 剩下 1 號呢
你 發現 了 嗎
如果 有 1 個人 剩下 的 1 號
如果 2 個人 剩下 的 1 號
如果 4 個人 剩下 的 1 號
如果 8 個人 剩下 的 是 1 號
如果 16 個人 剩下 的 1 號
你 知道 什 麽 時候 會 剩下 1 號嗎
你 看 出來 了
知道 吧
如果 這個 N=2^a
其中 這個 a 是 個 整數
如果 它 是 2 的 冪次 的話
那 麽 最後 剩下 的 就 一定 是 1 號 對 不 對
這又是 一個 特點
好 咱們 繼續 找 特點 看看 還有 什 麽 特點
你 看 在 2 個人 和 4 個人 中間
剩下 的 那個 士兵 編號 是 1 號 3 號 對 吧
在 4 個人 到 8 個人 之間
剩下 的 士兵 編號 是 1 3 5 7
在 8 個人 到 16 個人 之間
剩下 的 編號 是
1 3 5 7 9 11 13
你 發現 了 嗎
就是 如果 你 這個 人數
是 在 2 的 兩個 冪次 之間 的話
那 麽 你 剩余 的 編號 一定 是 奇數 數列
1 3 5 7 9... 這樣 的 排列 是不是
我們 用 數學 化 的 語言 表述 一下
就是 假如 說 這個 人數
它 可以 寫成 2^a+b
2^a 就是 2 的 整數 冪
然後 還 剩下 一 個數 這個 數 就是 b
很 顯然 這個 b 必須 小於 2^a
必須 小於 2^a
那 麽 b 如果 是 0 的話
最後 剩 的 那個 人 肯定 是 1 號 對 不 對
如果 b 分別 是 1 2 3 4 5...
你 剩下 的 人 編號 就 應該 是
3 5 7 9 11...
咱們 仔細 琢磨 琢磨
b 是 0 剩 1 號
b 是 1 剩 3 號
b 是 2 剩 5 號
b 是 3 剩 7 號
你 能 看 出來 嗎
最後 剩余 的 這個 人 他 的 編號 是 什 麽
是不是 正好 是 2b+1
能 不能 看 出來 對 吧
我舉 個例 子
你 比如說 如果 你 一共 有 11 個人 的話
那 麽 你 相當於 是 2^3 8 再 加上 3
所以 說 a 就 等於 3 b 也 等於 3
在 這種 情況 下 你 剩余 的 是 2b+1 號
那 也 就是 7 號
如果 你 一共 12 個人 的話 你 相當於 是 8+4
b 就是 4
b 既然 是 4 你 剩余 的 就是 2×4+1
你 就 剩余 9 號 是不是
你 通過 這樣 的 規律 你 就 發現 了
我 原來 可以 把 原來 的 人數 寫成 2 的 一個 冪次
再 加 一個 余數 的 形式
然後 把 這個 余數 乘以 2 再加 1
就是 剩余 的 那個
最後 的 那個 活著 的 戰士 了 對 吧
那 咱們 來看 一看 約瑟夫 問題
如果 是 約瑟夫 一共 有 41 個人
40 名 士兵 連同 他 自己 一共 有 41 個人
每 2 個人 我們 殺掉 一個
那 這樣一來 我們 就 把 41 寫成 是 32+9
32 是 什 麽
32 是 2^5
然後 再 加上 9
所以 就 相當於 按照 剛才 這個 公式
a＝5 而 b＝9 對 吧
那 在 這種 情況 下
你 最後 生存 的 是 哪 一個 戰士 呢
你 生存 的 戰士 應該 是 f＝2b+1
也 就是 18+1 等於 19 號
於是 約瑟夫 只要 最 開始 站 在 第 19 號的 位置
他 就 能夠 活 到 最後 一輪 對 吧
他 就 可以 向 羅馬 士兵 投降 了
當然 大家 也 可以 想一想
除了 約瑟夫 以外 還有 一個 活著 的 士兵
那個 是 哪 一號
那 麽 為 什 麽 最終 的 結論 是 這個 呢
就是 為什 麽 我們 約瑟夫 問題 的 解 就是 這個 解 呢
我們 能否 去 證明 一下 呢
來 我們 現在 開始 證明 它
其實 證明 這個 問題 也並 沒有 太 復 雜
首先 我們 先說 第一種 情況
如果 這個 人數 正好 是 2 的 整數 次 冪
這個 a 是 個 整數 的話
這個 時候 肯定 f 是 1
為什 麽 呢
咱們 仔細想
如果 你 有 8 個人 每 2 個人 殺 1 個人 的話
那 麽 最後 就 會 把 偶數 全都 殺掉
變 4 個人 對 吧
然後 下 一輪 殺 的 時候
是不是 還是 1 號做 殺手 對 吧
那 麽 這樣一來 再 殺掉 一半 這還 剩 2 個人
然後 下次 還是 1 號做 殺手
所以 說 如果 你 是 2 的 冪次 的話
你 每 一次 遊戲 都 會 依然 保證 是 2 的 冪次 對 吧
直到 最後 剩下 一個 人
2^0 也 就是 一個 人
剩下 的 這 一個 人 就是 1 號 對 吧
那 既然如此 的話 1 號 一直 都 是 安全 的
因為 他 一直 都 是 殺手 他 不會 被 人 殺
好 這種 情況 下
如果 你 是 2 的 整數 次 冪 的話 那 一定 剩 1 號
這個 是 可以 理解 的
還有 一種 情況
就是 如果 你 不是 2 的 整數 次 冪
而是 2 的 整數 次 冪 再加 一個 余數 b
這種 情況 下 我們 又 該 怎 麽 辦 呢
那 這種 情況 下 我們 把 這圈畫 出來
比如說 這是 1 號 旁邊 是 2 號
然後 3 號 4 號
一直 有 那 麽 一 個數 叫做 2b 號
然後 2b+1 號 然後 繼續 圍
一直 圍到 最後 一個 是 第 N 號 圍成 一個圈
現在 不是 已經 有 了 2^a+b 個人 嗎
他 不 滿足 2^a
所以 咱們 這 麽 辦
先 讓 這個 遊戲 進行 b 次
也就是說 進行 第一次 1 號殺 2 號
進行 第二次 3 號殺 4 號
進行 到 第 b 次
那 是不是 2b-1 殺 了 2b 號
因為 他 每 兩個 人殺 一個 對 不 對
所以 你 進行 了 b 次 之後 殺掉 了 b 個人
最後 就 剩 了 2^a 個人
大家 聽 明白 了 嗎
所以 我們 的 做法 是
第一步 先殺 b 人余 2^a 個人
先殺 了 這 麽 多 個人
那 麽 殺 到 最後 一個 人 應該 是 第 2b 號 對 不 對
於是 現在 你 是不是 已經 剩 了 2^a 個人 了
那 麽 我問 你 剩 2^a 個人 之後
你 應該 是 誰 生存
是 不 就 第一個 人 生存
但是 這 第一個 人 是 誰
是 他
他 是 多少
他 是 2b+1 號 對 不 對
所以 最後 的 結果 是 2b+1 號 生存 對 吧
你 看 我們 就 證明 完畢 了
所以 思路 其實 也 很 簡單
就是 你 首先 先殺 b 個人
殺 了 b 個人 之後
就 轉化成 了 2^a 次方 個人 這樣 的 遊戲 了
然後 就是 第一個 人 生存
而 第一個 人 就是 第 2b+1 個人 對 不 對
所以 他 就 生存 下來 了
因此 我們 這個 結論 是 沒有 問題 的
當然 我們 剛才 說 的 這種 情況
只是 在 每 兩個 人殺 一個 人 的 情況
那 麽 假如 你 參加 這個 遊戲 是 每 三個 人
每 四個 人 每 五個 人殺 一個 人 的話
那 又 該 怎 麽 去 處理 呢
那 下面 我們 來 討論 一個 更加 一般 的
更 一般 的 情況
這個 一般 的 情況 就是
首先 有 N 個人 成 一個 環兒
然後 我們 每 k 個人 殺 一人
那 麽 最後 我們 生存 下來 的 或者說 剩余 的 是 誰
這個 是 一個 更加 普遍 的 約瑟夫 問題
如果 k=2 就 回到 了 這個 基礎 版 的 是 吧
如果 k=3,4,5,6,7,...
那 麽 這個 問題 又 該 怎 麽 解 呢
這種 情況 下
沒有 像 k=2 那 麽 簡單 的 一個通 項 公式
但是 我們 也 有 一個 遞推 式 來 求解
咱們 把 這個 最後 生存 下來 的 人 寫作 f(N,k)
N 的 意思 是 最 開始 的 人數 是 吧
3 個人 5 個人 10 個人 ... 41 個人 ...
k 是 每 幾個 人殺 一個 是 吧
2 個人 殺 1 個 3 個人 殺 1 個 4 個人 殺 1 個 ...
這種 情況
我 就 問說 這個 式子 得解
怎 麽 做 呢
我們 分 兩步 來 做
首先 第一步 f(1,k) 等於 幾
也就是說 我 不管 你 隔 幾個 人殺 一個
如果 我 一共 就 只有 一個 玩家 的話
你 說 最後 誰 剩下
那 不 就是 1 號人 剩下 嗎
因為 一共 就 他 一個 是不是
所以 不管 隔 幾個 殺 一個 人
你 只要 是 只有 一個 玩家
那 最後 剩 的 這個 玩家 就是 最後 生存者
那 麽 假如 說
假如 說 你 有 N 個 玩家 的話
那 我 想問 N 個 玩家 它 的 生存者 有什 麽 規律 呢
這個 是 整個 約瑟夫 問題 裏邊 最 精彩 的 一環
大家 仔細 看 一下
我們 舉 一個 例子
比如說 一共 有 八個 玩家 一共 有 九個 吧
一共 有 九個 玩家
然後 我 告訴 你 說 k=3
K=3 的 意思 就是 每 3 個人 我 殺 一個 人
好 現在 我 做 一件 事
首先 1 2 第 3 個人 我 把 他 殺掉
那 現在 就 不是 九個 人 了 現在 就是 八個 人 了
這 八個 人 遊戲 的 最後 生存者
和 剛才 九個 人 遊戲 的 最後 生存者
是不是 同一個 人 對 吧
因為 它 實際上 是 同一個 遊戲
只不過 我 現在 先殺 了 一個 人 就 剩 八個 了
那 剩余 遊戲 的 最後 生存者
就是 最 開始 那個遊戲 的 最後 生存者 對 不 對
那 麽 假如 我們 從 4 號 開始
我 重新 編號 1 2 3 4 5 6 7 8
我 編成 新 的 8 個人
那 麽 他 就 會 有 一個 新 的 最後 生存者
叫做 f(N-1,k)
這 8 個人 最後 的 生存者
和 剛才 9 個人 最後 生存者
其實 是 1 個人
但 他 編號 不 一樣
你 看 原來 的 4 號 現在 是 1 號
原來 的 5 號 現在 是 2 號
原來 6 號 現在 是 3 號
說明 他 的 編號 差 了 3
這個 3 就是 什 麽
就是 那個 每幾人 殺 一人 的 k
所以 我 應該 讓 它 加上 k
這樣 新 的 編號 就 和 原來 編號 一樣 了
然後 還有 一個 問題 你 仔細 看
就是說 前 幾個 都 沒 問題
一直 到 這
1+3=4 2+3=5 3+3=6 ...
一直 到 最後 6+3=9 都 沒 問題
但是 7+3 就 不是 1 了 就是 10 了 為什 麽
因為 他 扣圈 了 對 不 對
所以 我們 說 如果 你 要是 超過 了 N 個 的話
你 就 得減 N
所以 最後 對於 右邊 的 這個 式子
我 還要 做 一點 說明
如果 結果 大於 N
那 麽 我們 就要 減去 N
就是 對 右邊 的 結果 做 一個 說明
說 左邊 的 這個 式子 等於 右邊 的 這個 式子
但是 右邊 的 式子 如果 結果 是 比 N 大 的
我 就 得 減去 一個 N
這樣 才能 和 左邊 的 這個 式子 相等
這樣 我 就 把 N 個人 最後 生存者 的 問題
轉化成 一個 N-1 個人 最後 生存者 的 問題
這個 問題 我們 稱之為 遞歸
就是 我們 從 一 個數 比較 大 的 情況
回到 數 比較 小 的 情況
以前 我們 講 漢諾塔 其實 用 的 也 是 這種 思路
好 有 了 這個 首項 和 一個 遞推 式 的話
那 麽 任何 的 一般 情況 我們 都 是 可以 解 的
舉 個例 子 比如說 一共 有 8 個人
然後 我們 每隔 3 個人 每 3 個人 我 殺 1 個人
請問 最後 生存者 是 誰
怎 麽 算 呢
首先 我們 假設
如果 有 1 個人 每 3 個人 殺 1 個
那 麽 最後 生存者 是 1 對 不 對
如果 有 2 個人 每 3 個人 殺 1 個
最後 生存者 是 什 麽
套用 這個 公式 它 等於 f(1,3)+k
f(1,3) 是 1 1+k k 是 3
1+3=4
但是 你 要 註 意 結果 如果 大於 N 就要 減去 N
對於 第二個 式子 來講
N 是 2 因為 兩個 人 遊戲
2 個人 遊戲 每 3 個人 殺 1 個
所以 你 比 2 大 所以 我 要減 2 就 變成 了 2
這就是說 2 個人 遊戲 每 3 個人 殺 1 個
最後 生存者 是 2 號 是不是
好 咱們 繼續
如果 有 3 個人 每 3 個人 殺 1 個
最後 生存者 是 幾號
按照 我們 遞推 公式 它 等於 2+3
然後 2+3=5 是不是
但是 5 比 3 大 所以 減去 3 變成 了 2
f(4,3) 按照 這個 規律 就是 2+3=5
5-4=1
然後 f(5,3) 5 個人 玩遊戲 每 3 個人 殺 1 個
它 等於 1+3=4
那 麽 這個 4 沒有 5 大
所以 不用 再 減去 5 了
然後 f(6,3) 6 個人 玩遊戲 每 3 個人 殺 1 個
它 等於 4+3=7
7 比 6 大 還要 減去 6 變成 1
然後 f(7,3) 等於 1+3=4 4 不用 減 7 了
然後 f(8,3) 等於 4+3=7 7 比 8 小
所以 不用 減 1
最後 生存者 是 7 號 對 不 對
這個 遊戲 我們 就 找到 了 一個 通解 了
我們 就 可以 生存 下來 了
其實 這個 數學 問題 也 不僅僅 是 在 古羅馬 有
在 東方 也 有
比如說 在 日本 這個 問題 叫做 繼子 立 問題
問題 說 有 一個 富豪 有 30 個兒 子
讓 他們 圍成 一個圈 每 10 個人 去掉 一個
最後 剩下 一個 人來 繼承 家產
請問 剩下 一個 人 是 誰
日本 的 著名 數學家 叫 關孝和
曾經 對 這個 問題 進行 過 一般性 的 討論
中國 的 數學家 方中通
在 他 的 著作 《 數度 衍 》 裏邊
也 描述 過 類似 的 問題
他 說 一共 有 20 個 棋子 圍成 一圈
其中 有 2 個 黑子 是 挨 一塊 的
其它 的 子 是 白子
從 某 一個 子 開始 每 9 個子 去掉 一個
直到 最後 你 發現 剩余 的 是 這 2 個 黑子
請問 它 是從 哪個 子 開始 去掉 的
那 麽 這 兩個 問題 留給 各位 同學 自己 思考
如果 你 知道 答案 的話
不妨 在 評論 區裏 寫下 你 的 看法
大家 如果 喜歡 我 的 視頻
可以 在 YouTube 賬號 李永樂 老師 裏 訂閱 我
點擊 鈴鐺 可以 第一 時間 獲得 更新 信息
