發新話題
打印

排列組合再請教

排列組合再請教

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

2. 已知是介於之間。試問有_________組整數數對(m,n) 滿足:



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

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

TOP

我第一題的想法如下,請各位高手提供更快的解答!
先考慮  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 編輯 ]

TOP

回復 1# tsyr 的帖子

TOP

回復 2# tsyr 的帖子

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

TOP

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


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

回復 6# cefepime 的帖子

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

非常感謝
cefepime
的精采解答!

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

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

TOP

發新話題