發新話題
打印

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

將2017用二進位表示 11111100001 ---------->(把最前面數字移到最後) 變成11111000011

還原此數的二進位變回十進位

即為1987

TOP

前幾天發現這次107中山大學雙週一題第一學期第五題的題目跟這題幾乎一模一樣,不過還是時間截止再丟上來討論,抄個題先

一疊紙牌有 2018 張標記 1 到 2018,其每張紙牌數字皆不同。這疊紙牌並無按照數字
大小做排序。將最上面的牌抽出並且放到桌上,而下一張牌放置於這疊紙牌的最後一張。
之後新的最上面那張牌再抽出並且放到之前桌上那張牌的右邊,然後其下一張牌再放置於
這疊紙牌的最後一張。此過程−將上面這張牌放到之前桌上那張牌的右邊並且下一張牌再
抽放置於牌組的最後一張,重複過程直到所有牌都被放到桌上為止。發現從左讀到右,這
桌上的牌之順序為 1, 2, 3, . . ., 2017, 2018。請問原本那疊紙牌中,有多少張卡片在號碼
為 2017 的卡片上面?

可以先討論16張牌情形,從上到下(仿造約瑟夫問題就是劃一個圓)
編號1-16,倒數第二張會是8,
15張是6,14張是4。同理,17張是10,18張是12
所以這題知道2048張是1024,2018就是1024-30*2=964,編號964的上方有963張就是答案

TOP

發新話題