發新話題
打印

106建中學科能力競賽初試

推到噗浪
推到臉書

106建中學科能力競賽初試

把1到2017這2017個自然數,按順時鐘方向依序排列在一個圓周上,由1開始,順時鐘方向,保留1,擦去2,保留3,擦去4,以此規則,每隔一個數就擦去一個數,請問最後一個擦去的數字為何。

TOP

以前看過如下解法。

先考慮: 如果共有 2ⁿ 個數,則易知最後一個擦去的數字為 1。

現在共有 2017 個數,把它視為 2¹¹ = 2048 個數擦去 31 個數後所留,回補 31 個數後的那個 "1" 的位置即為所求 = 2017 - 30 = 1987。

當然也可以由 2017 個數擦去 993 個剩 1024 = 2¹⁰個數,那個 "1" 的位置即為所求 = 1+2*993 = 1987。

TOP

感謝分享,真是妙解

TOP

可以google "Josephus Problem"

其實是一樣的

TOP

發新話題