包除原理(ベン図やガウス記号を駆使して解きます)

[問題 NT-05] 包除原理

(1) 1 から 99 までの整数のうち、 2, 3, 5 のいずれの数でも割り切れない数はいくつありますか。

(2) 99! を素因数分解したとき素因数 5 はいくつ含まれますか。

問題 NT-05 のヒント

「含む含まれない」を考える問題です。混乱したらベン図などを書いて整理してみてください。ガウス記号 [ ] を用いるとすっきりとした答案を作成できます。 [N] は N を超えない整数という意味です。たとえば [10.5] = 10 となります。(2) は 99! = 2a 3b 5c ... と分解したときの指数 c を求めよということです。

フェルマー予想

中古価格
¥3,380から
(2017/9/1 13:29時点)

問題 NT-05 の解答

 1 から 10 まで数を並べて 3 の倍数に○をつけてみます。

1, 2, ③, 4, 5, ⑥, 7, 8, ⑨, 10

 3 の倍数は 3 つごとに現れますから、1 から 10 までに含まれる 3 の倍数は 10 を 3 で割って端数を切り捨てた数 [10/3] に等しいことになります。以上のことをふまえて解答を作ります。

(1) 99 から 2 の倍数、 3 の倍数、 5 の倍数を引きます。

99 - [99/2] - [99/3] - [99/5] = 99 - 49 - 33 - 19 = - 2

 「え? マイナス? 計算ミス?」と驚かれるかもしれませんが、引きすぎがあるということです。 2 と 3 および 2 と 5, 3 と 5 の共通の倍数を 2 重に引いてしまっているので、今度はそれを足して戻します。

- 2 + [99/6] + [99/10] + [99/15] = - 2 + 16 + 9 + 6 = 29

 しかし今度は 2, 3, 5 の共通の倍数を足し過ぎているので再度引きます。

29 - [99/30] = 29 - 3 = 26

 分かりにくいと思ったら下のベン図を参照してください。

 ベン図235倍数

(2) 99! を書き下しておきます

99! = 1・2・3・4・5・6・・・24・25・・・74・75・・・97・98・99

 素因数 5 は 5 の倍数の中にしかないので、それを抜き出してみると

5, 10, 15, 20, 25, 30, 35, ...... 70, 75, 80, ......, 90, 95

 25 の倍数 25, 50, 75 には 5 の倍数が 2 つ含まれます。それ以外は 1 つずつです。つまり 5 の倍数について数え上げて、そのあと 25 の倍数を数え上げて足せば、含まれる素因数 5 を過不足なく数えることができます。したがって

99! に含まれる素因数 5 の数 = [99/5] + [99/25] = 19 + 3 = 22

が答えとなります。 ≫ [問題06] 分数式が整数となる条件 ≫ 数学演習問題

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。