謎題解答(8)


首先讓我們從直觀去試解這道題,然後嘗試總結一些規律出來。驟看這道題,我們很容易便想到在1至100這些數字中,以0或5結尾的數字都會令最後結果增添0。由於在1至100中,共有20個數字是以5或0結尾(10、20...100;5、15...95),我們可能會想1 x 2 x ...100的結尾應該有20個0。但是,且慢,100這個數不只給我們一個0,所以答案不只20。而且,不好,25 x 4 = 100,所以25這個數字也給我們兩個0。情況好像很複雜,還有遺漏嗎?

來到這裡,我們便得嘗試總結一些規律出來,看看為何100和25給我們增添兩個0,而15這個數則只給我們增添一個0,而其餘某些數(例如3)則不會為我們增添0。其實,為甚麼5、10這些數會令結果增添0?原因很簡單,就是這些數字含有5這個因子,而只要把5乘以一個偶數便可得到一個以0結尾的整數。不過,100和25這兩個數不僅含有一個5作為因子,而是含有兩個5,這兩個5只要各自乘以一個偶數便可得到兩個以0結尾的整數(換句話說,只要把100和25各乘以一個4的倍數便可得到以00結尾的整數)。這就是為何100和25會給我們增添兩個0。可是,在1至100之間,不僅100和25含有兩個5作為因子,還有50和75這兩個數字也是這樣。因此,我們可以總結說,在1至100之間,25、50、75和100這4個數字每個都會為我們增添2個0,而其餘16個以0或5結尾的數字則每個只為我們增添1個0。因此,1 x 2 x ... 100的結尾應該共有4 x 2 + 16 = 24個0。

說到這裡,有些人可能會指出,20 x 5也等於100,那麼20豈不是也給我們增添兩個0嗎?以上的計算好像還有遺漏啊。但請注意,5和20都是以0或5結尾的數字,因此我們在本文第一段點算1至100中以5或0結尾的數字時,已把這兩個數包括在內了。這兩個數合在一起剛好為我們增添兩個0,所以本文第一段的點算沒有遺漏。這跟25不同,25要與4一起才增添兩個0,而4並不是以5或0結尾的數字。在本文第一段點算1至100中以5或0結尾的數字時,我們並沒有把4包括在內,所以我們在數25時,要把它數兩次,而在數20時,卻只需把它數一次。

我們還可以從另一個角度看以上的分析,從而找出一條「公式」以概括以上的推理。上述討論其實就等同於,首先找出在1至100的數之間,有多少個數含有5作為因子,應該共有100 / 5 = 20個。這20個數會為我們的結果增添20個0。接著我們再找出在1至100之間,有多少個數含有25(即兩個5)作為因子,應該共有100 / 25 = 4個。請注意這4個數已包含在剛才算出的20個數之內,所以這4個數會為我們再增添4個0。由於在1至100之間不可能存在含有125(即三個5)作為因子的數,我們不用再計下去。因此我們所求的答案是20 + 4 = 24。總結一下,我們所求的「公式」就是100/5 + 100/25 = 24。

可是,我們還有遺漏嗎?只要我們想一想「九因歌」(即乘法表),應能發現只有在5乘以一個偶數的情況下才會產生10的倍數。除此以外,再沒有其他可能。所以以上的推理應該沒有遺漏了。

接著我們可以把以上推理推廣至一般情況。設有一個正整數n,我們要求n!的末尾有多少個連續的零。但在進行討論之前,我們先引入一個「floor函數」。任給一個實數x,floor(x)就是少於x的最大整數(註1)。依照以上分析,我們首先求1至n之間,有多少個數含有5作為因子,應該共有floor(n/5)個(註2),這些數會為我們增添floor(n/5)個零。接著我們求1至n之間,有多少個數含有52作為因子,應該共有floor(n/52)個。由於這些數已包含在先前的n/5個數中,因此這些數會為我們再增添floor(n/52)個零。接著我們再求1至n之間,有多少個數含有53作為因子,應該共有反floor(n/53)個,這些數會為我們再增添floor(n/53)個零.....如此類推。因此,我們得到以下「公式」:

floor(n/5) + floor(n/52) + floor(n/53) + ...

可是這條「公式」沒有說清楚要加到哪一項為止。為了使我們的公式更清晰,我們作出以下推理。由於任何整數的因數都必定小於或等於該數,上述公式只會加到floor(n/5k)項,使得5k <= n。接著讓我們從這一不等式求出k的值,我們在等號兩邊同時進行對數運算(註3):

log(5k) <= log(n)
k.log(5) <= log(n)
k <= log(n) / log(5)

我們可以取k = floor(log(n)/log(5)),因此我們的公式便成為:

floor(n/5) + floor(n/52) + floor(n/53) + ... floor(n/5k),其中 k = floor(log(n)/log(5))   (A)

現在我們可以運用上述公式來計算1013!的末尾有多少個連續的零了。由於floor(log(1013)/log(5)) = floor(4.3) = 4,我們把k = 4代入上式,得

floor(1013/5) + floor(1013/52) + floor(1013/53) + floor(1013/54) = 202 + 40 + 8 + 1 = 251

即1013!的末尾共有251個連續的零。

可是我們還有一個問題未解決。上述公式能成立(註4)的一個先決條件是,在1至n這些數中有足夠的偶數「分配」給各個含有5作為因子的數,使它們能「配對」相乘得出10的倍數。而且如果某一整數含有k個5作為因子,它便必須與一個含有(至少)k個2作為因子的偶數相乘,才能使以上公式成立。因此我們還必須證明,在1至n這些數中,的確有「足夠」的偶數使上式成立。這一點是容易證明的,我們可以把n!這個連乘積看成為質因數的連乘積(註5)。那麼我們便可把這個問題看成,在n!的質因數分解中,5的冪次是否小於或等於2的冪次?因為如果5的冪次小於或等於2的冪次,那麼便有足夠的2與各個5「配對」了。如何求5的冪次和2的冪次呢?5的冪次其實就是n!中所含5這個因子的次數,這正是上面公式(A)所求的數。至於2的冪次,其計算原理跟5的冪次的計算原理完全相同,因此我們可以容易得出求2的冪次的公式如下:

floor(n/2) + floor(n/22) + floor(n/23) + ... floor(n/2k),其中 k = floor(log(n)/log(2))   (B)

比較公式(A)和(B),我們容易看到,由於2 < 5,所以n/2 > n/5以及log(n)/log(2) > log(n)/log(5),因此公式(A)的結果必然小於(B)的結果。由此便可證明公式(A)的確是我們所要求的公式。

筆者之所以費這麼大力氣去證明以上這個頗為明顯的事實,是因為假如我們不是求n!,而是求一個更一般的(不包含0的)整數集的連乘積的末尾有多少個連續的零,那麼我們便必須小心考慮是否有足夠的2去和5「配對」(註6)。以下我用一個簡單的例子去說明這個問題。

假設我們要求3 x 4 x 5 x 30 x 75這個數的末尾有多少個零。在進行質因數分解後,我們得出這個連乘積含有3個2以及5個5作為因子(寫成算式就是3 x 4 x 5 x 30 x 75 = m x 23 x 55,其中m為一個整數)。由此我們看到這個連乘積雖然含有5個5,可是卻只有3個2「分配」給其中3個5,因此3 x 4 x 5 x 30 x 75的末尾只含有3個零而非5個零(請讀者自行用計算機驗證)。由此我們得出一個更一般情況的解:

任給一個不包含0的整數集,假如我們要求這個集中各整數的連乘積的末尾有多少個連續的零,我們只需求各個整數的質因數分解中2的冪次以及5的冪次,把這兩種冪次加起來比較其大小,較小的數字就是我們要求的答案。


註1:如果x是正實數,那麼floor(x)就等於把這個正實數的小數部分去掉,只留下整數部分。例如floor(36.7) =36、floor(36)=36。

註2:例如若n=101,則n / 5 = 20.2。可是20.2並非整數,在1至101之間應只有20(即floor(20.2))個數含有5作為因子,這就是為何要引入「floor函數」的原因。

註3:由於以下運算會涉及兩個對數相除,所以這裡無需註明對數的底,即在運算中取任何大於1的整數作為對數的底,其結果都一樣。

註4:這裡「成立」的意思是指,公式(A)所得結果的確就是我們所要求的結果。假如公式(A)不成立,那麼它只是求出在1至n這些數中所含5這個因子的總數,這個數並不等於我們要求的答案。

註5:這即是說,把1至n所有整數分解為質因數,然後把它們相乘。例如6! = 1 x 2 x 3 x 4 x 5 x 6可以看成(1) x (2) x (3) x (2 x 2) x (5) x (2 x 3)。把上述連乘積加以整理後,我們可得6! = 1 x 24 x 32 x 5。

註6:由於現在只考慮「質因數」,我們無需再考慮其他因數了,因為除了2和5外,沒有其他質數相乘會得出10的倍數(其他以2或5結尾的整數都不是質數,為甚麼?)。這就是為何我們在這裡引入質因數概念的原因了。

返回猜謎題,學推理