電話番号の組合せ数から必要な桁数を求める
ITパスポート試験 令和元年度秋期 問82 ／ 基礎理論 › 離散数学
過去問にチャレンジ
次の体系をもつ電話番号において、80億個の番号を創出したい。番号の最低限必要な桁数は幾つか。ここで、桁数には “020” を含むこととする。
- ア
11
- イ
12
- ウ
13
- エ
14
会話形式の解説
講師注目するのは、桁ごとに選べる数字の数です。固定された部分も全体の桁数に含めます。
受験者「020」は3桁として数えるのですね。その後はすべて0〜9の10通りでしょうか。
講師図では「020」の直後だけ、1〜3と5〜9の8通りです。それより後の各桁は10通りです。
受験者直後の1桁を10通りにすると、作れる番号を多く見積もってしまいますね。
講師はい。全体をn桁とすると、最初の4桁の後にはn−4桁が残ります。番号の総数は8×10の（n−4）乗通りです。
受験者11桁なら残りは7桁なので、8×10の7乗で8000万通りです。80億には足りません。
講師その通りです。12桁でも8×10の8乗、つまり8億通りで不足します。
受験者13桁なら残りが9桁です。8×10の9乗で、ちょうど80億通りになります。
講師正解です。14桁なら800億通り作れますが、13桁で必要数を満たすので、最低限必要な桁数にはなりません。
受験者8通りの桁と、その後の10通りの桁を分けて数え、初めて80億に届く桁数を選ぶのですね。
講師はい。「020」を桁数から除かないことも大切です。桁を一つ増やすと、後ろの部分の組合せは10倍になります。
まとめ
固定された「020」も全体の桁数に含めます。その直後は8通り、残りの各桁は10通りなので、全体がn桁なら8×10の（n−4）乗通りの番号を作れます。12桁では8億通りで不足し、13桁で80億通りに達します。したがって、最低限必要なのは13桁です。
解答・解説
正解はウです
この問題のテーマ
固定された「020」に続く各桁の組合せを数え、80億個の番号を作るために必要な最小桁数を求める問題です。
解き方の考え方
全体をn桁とすると、「020」の次の1桁は8通り、残りのn−4桁はそれぞれ10通りです。したがって番号の総数は通りです。12桁では8億通りで足りず、13桁では億通りになるため、最小は13桁です。
選択肢ごとの解説
- ×ア 11アの11桁では、最初の4桁の後に7桁が残ります。作れる番号は万通りで、80億通りには足りません。
- ×イ 12イの12桁では、最初の4桁の後に8桁が残ります。億通りなので、まだ必要数に届きません。
- ○ウ 13ウの13桁では、最初の4桁の後に9桁が残り、その部分だけで億通りあります。「020」の次の桁の8通りを掛けると80億通りです。12桁では足りないため、13桁が最小です。
- ×エ 14エの14桁では、億通りを作れます。しかし、13桁で既に80億通りを作れるため、最低限必要な桁数ではありません。
補足
「020」の次の桁まで10通りとして数えると、番号の総数を多く見積もってしまいます。桁を一つ増やすと、それ以降の部分の組合せは10倍になります。
POINT
- 固定された「020」も全体の桁数に含めます。
- 「020」の直後は8通り、それ以降は各桁10通りです。
- 全体がn桁なら、番号の総数は通りです。
- 必要数を初めて満たす桁数を答えます。