Math Pro 數學補給站

標題: 排列組合再請教 [打印本頁]

作者: tsyr 時間: 2014-12-29 18:50 標題: 排列組合再請教

最近在研究排列組合~~
1. 伯納多選取一個三位數的正整數N，並在黑板上將N分別改寫成以5為底以及以6為底的表示法。稍後，拉洛伊看到黑板上伯納多所寫的這兩個數，就將它們當做以10為底的整數相加，而得正整數S。例如，如果N=749，那麼伯納多會在黑板改寫成10,444與3,245，而拉洛伊就得到和S=13,689。試問有多少正整數N，會使得S最右邊的兩邊數碼依序與2N的最右邊的兩個數碼相同？(註)：以6為底時3245表 $3\times 6^{3}+2\times 6^{2}+4\times 6+5=749$

2. 已知 $5^{867}$ 是介於 $2^{2013}$ 與 $2^{2014}$ 之間。試問有_________組整數數對(m,n) 滿足：
$1\leq m\leq 2012$ 且 $5^{n}<2^{m}<2^{m+2}<5^{n+1}$ 。

Thank you very much.
第二題答案為279

[ 本帖最後由 tsyr 於 2014-12-29 08:04 PM 編輯 ]

作者: tsyr 時間: 2014-12-29 19:13

我第一題的想法如下，請各位高手提供更快的解答!
先考慮 N的個位數字(x) 以5為底的個位數字(y) 以6為底的個位數字(z)
(1)x=0~4，y=x，z=2x-y=y
(2)x=5~9，y=x-5，z=2x-y-10=y
綜合(1)和(2)，可得y=z，即N除以5和6的餘數相同(為a)。
因此，我們可以列出N=30k+a，其中a=0,1,2,3,4
又對於所有k屬於正整數，若a=0時符合題述條件，則a=1,2,3,4均符合
因此我們剩下要考慮的數字如下，順便連以5為底最後兩位數(m)和以6為底最後兩位數(n)之值也列上
(N,m,n)=
(120,40,20),
(150,00,10),
(180,10,00),
(210,20,50),
(240,30,40),
(270,40,30),
(300,00,20),
(330,10,10),
......後面循環
發現只有360,390,720,900,930符合
再加上a可以等於0,1,2,3,4
故N有5*5=25種可能。

[ 本帖最後由 tsyr 於 2014-12-29 07:19 PM 編輯 ]

作者: thepiano 時間: 2014-12-29 20:36 標題: 回復 1# tsyr 的帖子

第 2 題
之前寫過，可參考 http://www.shiner.idv.tw/teachers/viewtopic.php?f=46&p=10503

作者: thepiano 時間: 2014-12-29 21:56 標題: 回復 2# tsyr 的帖子

第 1 題
您後面的做法可改用同餘
參考 http://www.artofproblemsolving.c ... Problems/Problem_23

作者: cefepime 時間: 2014-12-31 23:44

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

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 關係密切。

作者: cefepime 時間: 2015-1-1 00:34

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 編輯 ]

作者: tsyr 時間: 2015-1-1 21:35 標題: 回復 6# cefepime 的帖子

上面有神快拜!
小弟受教了

非常感謝
cefepime
的精采解答!

大家新年快樂
今年還請各位高手多多指教

[ 本帖最後由 tsyr 於 2015-1-1 09:38 PM 編輯 ]

歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)

論壇程式使用 Discuz! 6.1.0