Weekend Mathematics問題/問題25

25.1999年の問題

1999!を十進法で表すとき、末尾に何個の0が並ぶでしょうか?

(ただし、N!=N(N−1)(N−2)・・・3・2・1です。)




問題の出典


1997年日本数学オリンピック予選

(財)数学オリンピック財団






答えと解説












答えと解説

解答・その1

(ペンネ−ム:ヤマさん)

p個の0が並ぶとおく。
このとき 1999!=ax10 (aは10で割り切れない整数) とおける。
10=2x5 より、 1999!がいくつの2x5 を持つかを調べればよい。
1〜1999において5の約数を持つ整数の方が少ないことは明らかであるから、 5の約数の個数を求める。
1〜1999の中で、 5、25、125、625で割り切れる数の個数はそれぞれ、
5・・・399
25・・・79
125・・・15
625・・・3
となる。
ここで、25・・・79は、25で割り切れる数が5で割り切れる数 にはない新たな5の約数を79個持つことを表すから、 上記の個数には重複がないと言える。
よって1999!がもつ5の約数の個数は、
399+79+15+3=496
ゆえに1999!は、2496x5496を約数に持つ。
だから、1999!=ax10496となり、末尾には0が496個並ぶ。



解答・その2

(ペンネ−ム:2丁目の山田)

n個0が並ぶ⇔10nで割れる
で、ここでは
⇔5nで割れる
で、1999!何回5でわれるかで
[1999/5]+[1999/25]+[1999/125]+[1999/625]=399+79+15+3=496
[x]はxを越えない最大の整数




解答・その3

(ペンネ−ム:kiyo)

1999!のなかに5の素因数がいくらあるか調べる。
1999÷5=399...4
1999÷25=79...24
1999÷125=15...124
1999÷625=3...124
399+79+15+3=496
2の素因数はそれ以上であるから、末尾の0の個数は496個となる。
答え 496個。



解答・その4

(ペンネ−ム:みや)

1999!が10の何乗で割り切れるかということだから 2×5の何乗かを考える。
2についてはたくさんあるから、 1999!に(×5)がいくつ含まれているかを考える。
1999以下の5の倍数は399個(1999÷5)
1999以下の5の2乗の倍数は79個(1999÷25)
1999以下の5の3乗の倍数は15個(1999÷125)
1999以下の5の4乗の倍数は3個(1999÷625)
1999!に含まれる(×5)の個数は399+79+15+3=496
よって(2×5)が496個含まれている。
答え 496



解答・その5

(ペンネ−ム:yuuちゃん )

10=(2×5)=(2)×(5)となります
1999!=1999×1998×1997×・・・・・・×3×2×1
1999!の式の中で、2で割れるものは、
1998、1996、・・・・、4、2であり、
除した商も同様に考えると、
(999+499+249+124+62+31+15+7+3+1)となります
また、同様に5で割れるものは1995、1990、・・・・、10、5であり、
(399+79+15+3)となります
これらより

 1999!
=(2(999+499+249+124+62+31+15+7+3+1))×(5(399+79+15+3))×・・・・
=(2(399+79+15+3))×(5(399+79+15+3))×(2(999+499+249+124+62+31+15+7+3+1)−(399+79+15+3))×・・・・
=(10(399+79+15+3))×・・・・・
となり、 399+79+15+3=496 となります。



解答・その6

(ペンネ−ム:まめ )

1999!を素因数分解した場合に、 2と5が一組あるごとに、末尾に10が増えていきます。
明らかに、2よりも5の方が個数が少ないですから、 いくつ5があるかを数えれば、それが答えです。
まず、1999を5で割って、 1999以下の5の倍数の個数を求めてみます。
1999÷5=399・・・4
ですから、全部で399個あります。
しかし、5の数はこれだけではありません。
それは、25や、125など、5のn乗で表されるものがあるからです。
5の2乗である25の、1999以下の倍数は、
1999÷25=79・・・24
というわけで79個。 これでさらに5の数は79個増えます。
また、5の3乗である125の、1999以下の倍数は、
1999÷125=15・・・124
というわけで15個。これでさらに5の数は15個増えます。
最後に、5の4乗である625の、1999以下の倍数は、
1999÷625=3・・・124
というわけで3個。これでさらに5の数は3個増えます。
以上の考察から、1999!を素因数に分解した場合にでてくる5の個数は、
399+79+15+3=496
となります。 これが、1999!を計算した場合に、末尾に並ぶ0の個数です。

図で描くともう少し分かりやすくなりそうです。
下のように、5がでてくるたびに、●をつけていきます。

        5    ●
       10    ●
       15    ●
       20    ●
       25    ●    ●
        ・ 
        ・
       50    ●    ●
        ・
        .
       75    ●    ●
        ・
        ・
      125    ●    ●    ●
        ・
        ・
      250    ●    ●    ●
        ・
        ・
      625    ●    ●    ●    ●
        ・
        ・
     1250    ●    ●    ●    ●
        ・
        ・
     1875    ●    ●    ●    ●
        ・
        ・
     1999    −    −    −    −
−−−−−−−−−−−−−−−−−−−−−−−−−−−
            399   79    15    3
という感じです。



解答・その7

(浜田 明巳 )

答は496個です。
ようするに1999!を素因数分解したときに、 何個の5が含まれているかを求めればよいわけです。
そのために、5から1995までの5の倍数の中で、 何個の5が含まれているかを、 次のVISUAL BASICのプログラムで求めてみました。

Option Explicit
Private Sub Command1_Click()
    '1999!を十進法で表すとき,末尾に何個の0が並ぶでしょうか?
    Dim kotae, j, jj As Integer
    kotae = 0
    For j = 5 To 1995 Step 5
      jj = j
      Do While jj Mod 5 = 0
        jj = jj \ 5
        kotae = kotae + 1
      Loop
    Next
    Picture1.Print "答="; kotae
End Sub
Private Sub Command2_Click()
    End
End Sub




解答・その8

(ペンネ−ム:水の流れ )

解答 10=2×5より、1999!の中に10の倍数は何個あるかは、 5の倍数が何個あるかになります。 だから、
1から1999までに5の倍数がa個で、
1から1999までに5=25の倍数がb個で、
1から1999までに5=125の倍数がc個で、
1から1999までに5=625の倍数がd個あるとします。 よって、


したがって、=399+79+15+3=496(個)・・・(答え)
または、ガウス記号を[   ]を使って、

a+b+c+d =[1999/5]+[1999/25]+[1999/125]+[1999/625]
               =399+79+15+3=496(個)・・・(答え)

定理1
n!に含まれる素数pのすべての個数をn(p)とおくと、

n(p) =[n/p]+[n/p2]+[n/p3]+[n/p4]+・・・
    =a+b+c+d+・・・     である。
<証明> 自明ですので、省きます。

そこで、自然数nをp進法で表して、これを用いて別の方法で解きます。
n=Apα+Bp(α−1) +Cp(α−2)+ Dp(α−3)+・・・+Gp+H
ただし、A≠0,0≦A,B,C,D,・・・,G,H< p とする。
また、Hは(α+1)番目とします。
すなわち、表記として、n・・・(十進法)→ABCD・・・GH <p進法>
ここで、
n/p=Ap(α−1) +Bp(α−2)+Cp(α−3)+・・・+G+H/p
ですから、
a=[n/p]=Ap(α−1)+Bp(α−2)+Cp(α−3)+・・・+G
b=[a/p]=Ap(α−2)+Bp(α−3)+・・・+F
  ・・・・・・・・・・・・・・・・・・・
g=[f/p]=Ap+B
h=[g/p]=A
したがって、これらα個を全部加えて

 n(p)=a+b+c+d+・・・+g+h  
    =A×(pα−1)/(p−1)+B×{p(α−1)−1}/(p−1)+・・・+G
ここで、表記のために、分母の(p−1)を掛けて、括弧の中を別々に加えると
  n(p)×(p−1)
={Apα+Bp(α−1) +Cp(α−2)+Dp(α−3)+・・・+Gp}−(A+B+C+・・・+G)    
={Apα+Bp(α−1) +Cp(α−2)+Dp(α−3)+・・・+Gp+H}−(A+B+C+・・・+G+H)
=n−(A+B+C+・・・+G+H)
故に、

定理2
n!に含まれる素数pのすべての個数をn(p)とおいて、
n=Apα+Bp(α−1) +Cp(α−2)+Dp(α−3)+・・・+Gp+H
ただし、A≠0,0≦A,B,C,D,・・・,G,H< p とする。
また、Hは(α+1)番目とします。 
  すなわち、表記として、n・・・(十進法)→ABCD・・・GH <p進法>
このとき、
n(p) ={n−(A+B+C+・・・+G+H)}/(p−1) ・・・(答え)

例 1999(10進法)は5進法で30444<5進法>と表せます。
よって、前述の表記によると、
A=3,B=0,C=4,D=4,E=4 だから、
求める個数は
{1999−(3+0+4+4+4)}/(5−1)=496 (答え)




まとめ

今回は、因数5の個数を数える、という問題でした。
そのためには、5で次々と割っていくわけですから、 10進法表示されている1999を5進法表示に直す時の作業と全く同じです。


この時に、5で割った商を次々に足していって、496という答えを出したわけです。
それに対して1999を5進法表示に直す時は、商ではなく余りに注目して30444と表記します。
その関連を「水の流れ」さんが見事に解明してくださいました。



関連した内容が コロキウム室のNO.297NO.298NO.315にあります。



正解者

水の流れ

ヤマさん

ありさのお父さん

マサボー

2丁目の山田

みや

kiyo

Takahisa Iida

yuuちゃん

浜田 明巳

まめ




戻る