×

Χρησιμοποιούμε cookies για να βελτιώσουμε τη λειτουργία του LingQ. Επισκέπτοντας τον ιστότοπο, συμφωνείς στην πολιτική για τα cookies.

image

李永樂老師, 现实中的鱿鱼游戏,你能成功活到最后吗?——约瑟夫问题

现实 中 的 鱿鱼 游戏 , 你 能 成功 活 到 最后 吗 ?—— 约瑟夫 问题

各位 同學 大家 好 我 是 李永樂 老師

最近 有 一個 熱播 的 韓劇 《 魷魚 遊戲 》

講述 的 一群 為 生活 所困 的 人

為 了 巨額 獎金 而 參加 生死 逃殺 遊戲 的 故事

有 小朋友 就問 我 說

如果 有 一天

他 也 參加 了 這樣 的 一個 大逃殺 遊戲

有沒有 什 麽 辦法 能夠 在 遊戲 中 生存 下來 呢

其實 在歷史上 這樣 的 遊戲 還 真的 發生 過

今天 我們 就 來講 述 一個 兩千年 以前

發生 在 古羅馬 時代 的 生存 逃殺 遊戲

約瑟夫 問題

約瑟夫 是 誰 呢

約瑟夫 是 古羅馬 時代 的 一個 猶太 的 歷史學家

那 麽 約瑟夫 曾經 領導 過

猶太人 反抗 羅馬帝國 的 統治

那 麽 他 帶領 了 一些 士兵

在 一個 要塞 堅守 了 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 賬號 李永樂 老師 裏 訂閱 我

點擊 鈴鐺 可以 第一 時間 獲得 更新 信息

Learn languages from TV shows, movies, news, articles and more! Try LingQ for FREE

现实 中 的 鱿鱼 游戏 , 你 能 成功 活 到 最后 吗 ?—— 约瑟夫 问题 |||Squid Game||||||||||

各位 同學 大家 好 我 是 李永樂 老師

最近 有 一個 熱播 的 韓劇 《 魷魚 遊戲 》

講述 的 一群 為 生活 所困 的 人

為 了 巨額 獎金 而 參加 生死 逃殺 遊戲 的 故事

有 小朋友 就問 我 說

如果 有 一天

他 也 參加 了 這樣 的 一個 大逃殺 遊戲

有沒有 什 麽 辦法 能夠 在 遊戲 中 生存 下來 呢

其實 在歷史上 這樣 的 遊戲 還 真的 發生 過

今天 我們 就 來講 述 一個 兩千年 以前

發生 在 古羅馬 時代 的 生存 逃殺 遊戲

約瑟夫 問題

約瑟夫 是 誰 呢

約瑟夫 是 古羅馬 時代 的 一個 猶太 的 歷史學家

那 麽 約瑟夫 曾經 領導 過

猶太人 反抗 羅馬帝國 的 統治

那 麽 他 帶領 了 一些 士兵

在 一個 要塞 堅守 了 47 天

結果 還是 被 羅馬 士兵 圍困 到 一個 山洞 裏邊 了

他 手下 有 40 名 士兵

這些 士兵 們 都 說 我們 寧可 自殺 也 不 投降

這個 時候 約瑟夫 本人 並 不想 自殺

他 想 向 羅馬 士兵 投降 但是 他 又 不敢 說

怎 麽 辦 呢

於是 他 就 對 士兵 說

自殺 不 符合 我們 猶太人 的 傳統

所以 我們 可以 這樣 做

我們 41 個人 圍成 一個 環兒

然後 1 號 士兵 殺死 他 旁邊 的 2 號 士兵

3 號 士兵 殺死 他 旁邊 的 4 號 士兵

39 號 士兵 殺死 40 號 士兵

41 號 士兵 再 去 殺死 還活 著 的 1 號 士兵

如此 類推

最終 只 剩下 一個 士兵

這個 士兵 再 自殺 就 可以 了

經過 幾輪 之後

這 約瑟夫 和 另外 一位 士兵 還活 著

約瑟夫 就 勸說 這位 士兵

跟 他 一起 向 羅馬 士兵 投降

於是 他們 就活 了 下來

約瑟夫 還把 這個 故事 寫 在 了 他 的 日記 之中

那 今天 的 這個 問題

就 被 我們 稱之為 約瑟夫 問題

約瑟夫 問題

如果 我們 討論 得 普遍 一點 就是 這樣 的

說 一共 有 N 個人

有 N 個人 圍成 一個 環兒 圍成 一個 環兒

然後 每隔 幾個 人 殺掉 一個 人

我們 先說 最 簡單 的 情況

比如說 每 兩人 每 兩人 我們 殺 一人

然後 這樣 一輪 一輪 地殺 下去

直到 最後 剩下 一個 人

那 麽 我 就 想問 最後 剩下 的 是 誰

這個 問題 我們 就 稱 之 為 約瑟夫 問題

這個 約瑟夫 問題 到底 該 怎 麽 解 呢

可能 剛 拿到 我們 手裏 我們 也 不 清楚

於是 我們 要 試一試 對 吧

怎 麽 試 呢

我們 從 最 簡單 的 情況 開始

比如說 我們 用 字母 N 來 表示 這個 人數

然後 我們 最後 剩 的 這個 人 我們 管 他 叫 f |||||||||||call him 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 個 ...

這種 情況

我 就 問說 這個 式子 得解 |||||solvable

怎 麽 做 呢

我們 分 兩步 來 做

首先 第一步 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 號 對 不 對

這個 遊戲 我們 就 找到 了 一個 通解 了 |||||||universal solution|

我們 就 可以 生存 下來 了

其實 這個 數學 問題 也 不僅僅 是 在 古羅馬 有

在 東方 也 有

比如說 在 日本 這個 問題 叫做 繼子 立 問題

問題 說 有 一個 富豪 有 30 個兒 子

讓 他們 圍成 一個圈 每 10 個人 去掉 一個

最後 剩下 一個 人來 繼承 家產

請問 剩下 一個 人 是 誰

日本 的 著名 數學家 叫 關孝和

曾經 對 這個 問題 進行 過 一般性 的 討論

中國 的 數學家 方中通

在 他 的 著作 《 數度 衍 》 裏邊

也 描述 過 類似 的 問題

他 說 一共 有 20 個 棋子 圍成 一圈

其中 有 2 個 黑子 是 挨 一塊 的

其它 的 子 是 白子

從 某 一個 子 開始 每 9 個子 去掉 一個

直到 最後 你 發現 剩余 的 是 這 2 個 黑子

請問 它 是從 哪個 子 開始 去掉 的

那 麽 這 兩個 問題 留給 各位 同學 自己 思考

如果 你 知道 答案 的話

不妨 在 評論 區裏 寫下 你 的 看法

大家 如果 喜歡 我 的 視頻

可以 在 YouTube 賬號 李永樂 老師 裏 訂閱 我

點擊 鈴鐺 可以 第一 時間 獲得 更新 信息