發新話題
打印

排列組合再請教

(感覺這兩題比較像數論而非排列組合)


1. 這題個人想不出什麼好方法,只拼湊出一個笨方法,不揣淺陋提供參考。


題目著重於 N 在五進位,六進位,與十進位制的末二位數字,因此我們把焦點放在 N 除以 25,36,與 100 的餘數 (它們依序決定上述之末二位數字)。又所有三位數為連續 900 個整數,而 [25, 36, 100] = 900,因此所有三位數對於 25,36,與 100 的餘數構成一個完整的週期。


現把所有三位數,對於 25 的餘數相同者歸一組,則一組包含 36 個數,且這 36 個數對於 36 的餘數皆相異 (因為 (25,36) = 1)。亦即,同一組內的數,用六進位表示時,末二位數字將是 00, 01, ..., 55 共 6*6 = 36 個。由於一組內的數用六進位表示時,末二位數字"應有盡有",因此猜想每一組都找得到符合題意的數。以下考察是否如此。


考慮某一組為包含對於 25 的餘數 = n 的三位數 N,n 用五進位表示時為 ab (即 N 用五進位表示時,末二位數字為 ab ), n = 5*a + b,(a,b) ∈ {0, 1, 2, 3, 4}。則 N 對於 100 的餘數 ∈ {n, n+25, n+50, n+75},那麼 2N 對於 100 的餘數 ∈ {2n, 2n+50},這兩類 (2n 或 2n+50) 各自包含了組內所有奇數與偶數的成員。現在考慮 2N 在十進位制的末二位,此即 2n 與 2n+50 在十進位制的表示法。由  2n = 10*a + 2b,(a,b) ∈ {0, 1, 2, 3, 4},得 2N 在十進位制的末二位為 (a)(2b) 與 (a+5)(2b) [括弧內為一個"位數"]。這兩個"末二位"與 N 用五進位表示時末二位數字 "ab" 分別差了 "0b" 與 "5b"。而諸 N 用六進位表示時,末位為 "b" 者皆有相同的奇偶性,因此必同屬上述 (a)(2b) 或 (a+5)(2b) 兩類之一,且其倒數第二位含有 0, 1, 2, 3, 4, 5,因此必定恰有一個滿足題目的條件。


以上證明了所有對於 25 同餘的三位數,恰有一個合所求。又模 25 的餘數有 25 個,因此所求 = 25。


p.s. 本題之所以用 25 而非 36 分組,是因 100 與 25 關係密切。

TOP

2. 題目研究有幾個"相鄰 5 的(非負)整數次冪夾住 3 個相鄰 2 的正整數次冪",因此先考察 5 的次冪與 2 的次冪的相對位置關係。


首先在數線上,正整數 N 跳到 2N 時,必定"恰跨越 1 個" 或 "恰踩到 1 個"  2 的次冪 (把 "2" 改成其它大於 1 的正整數亦成立)。 現圖示數線上某相鄰 5 的次冪:


---5ⁿ---2*5ⁿ---4*5ⁿ---5*5ⁿ---8*5ⁿ---


依上所述,區間 (5ⁿ, 2*5ⁿ] 與 (2*5ⁿ, 4*5ⁿ] 與 (4*5ⁿ, 8*5ⁿ],各恰包含 1 個 2 的次冪。因此,某相鄰 5 的次冪間 (5ⁿ, 5*5ⁿ),必恰包含 2 或 3 個 2 的次冪。


現在題目說:


1---5---...---2²°¹³---5⁸⁶⁷---2²°¹⁴---


並等同問: 在 2²°¹⁴ 以下有幾個"相鄰 5 的次冪夾住 3 個相鄰 2 的次冪"。由於在 2²°¹⁴ 以左共有 867 個 5 的次冪形成的間隔,它們共含有 2013 個 2 的次冪,且每個間隔恰含 2 或 3 個。因此,所求 = 2013 - 2*867 = 279 (個)。

[ 本帖最後由 cefepime 於 2015-1-1 12:40 AM 編輯 ]

TOP

發新話題
最近訪問的版塊