灘中学 2009年　1日目　大問６　場合の数

さて、表題の件です。

整数問題のような雰囲気の場合の数に関する問題です。

色々な事が学べる良問だと思います。是非解いてみて下さいね。

問題

以下　灘中学2009年　算数１日目　大問６より引用

9の倍数でなく、かつ各桁の数字に9を含まない1以上の整数のうち、

(1)999以下のものは□個ある。

(2)小さい方から数えて999番目の数は□である。

引用終わり

解答

9の倍数でなく、かつ各桁の数字に9を含まない1以上の整数のうち、

(1)999以下のものは□個ある。

１～999の整数　を　□□□（□は０～９の整数）　と考えると　10×10×10の1000個から『０００』の１個を引いた 999個である事が分かります。

では９を用いない数はいくつある？と考えれば

□□□（□は０～８の整数）となりますから

9×９×９＝729個、000を除くと 728個　である事が分かります。

『n進数』の考え方ですね。

ここから工夫して９の倍数を取り除くための最速ルートを考えられるかどうかです。

例えば愚直に以下のように場合分けをしても解答に辿り着く事は可能です。

１～９の整数　⇒　９のみ・・・・１個
10～99の整数　⇒　18 27 36 45 54 63 72 81 90 99 10個（ただし　90 と 99はダブリ）
100～999の整数・・・・・・

このように場合分けを進め　コツコツ進めれば答えに辿り着きます。
しかし、かなり時間を消費してしまうでしょう。数えモレも発生しやすいでしょう。

ここで数え上げるのではなく、『現象の理解とアイデア抽出』に時間を割き、以下の事に気付けばすぐに答えに辿り着きます。

９の倍数である条件は
★各位の数字の和が９の倍数である
です。ここから下の内容が連想出来るかどうかです。
★３桁の数字を　ＡＢＣ　と考えると　ＡとＢまたはＡとＣまたはＢとＣが決まれば９の倍数になるための残りの数字は自動的に決まる。

例１）Ａ＝３　Ｂ＝５　であれば　Ｃはただ一つ１の時だけが　９の倍数になる
例２）Ａ＝０　Ｂ＝０　であれば　Ｃは０と９の時だけが　９の倍数になる
例２が例外です。A＝０、B＝０の時のみCは２つ解を持ちます。
しかし、000は題意の範囲外ですから無視して良く、任意のABに対してCはただ一つの整数解(ただし0～8の範囲)を持つという事です。

さて、題意を言い換えると以下のようです。

9の倍数でなく、かつ各桁の数字に9を含まない1以上の整数
⇒９を使わずに作れる各位の数字の和が９にならない整数は１～９９９のうちに何個ありますか？

以上の事から　ABCの順で考えると
Aは０～８の９種類
Bは０～８の９種類
Cは０～８のうち任意の１種類を引いた８種類

となり　９×９×８＝６４８個　が答えとなります。

愚直に場合分けをした場合、かなり時間を消費しますから、「現象の理解、アイデア抽出に時間を使ってみよう！」という判断が出来るかどうかで消費時間に差が出る問題です。

9の倍数でなく、かつ各桁の数字に9を含まない1以上の整数のうち、
(2)小さい方から数えて999番目の数は□である。

さて、これも工夫次第で早く解ける問題です。

まずは当たりを付けます。

こう考え範囲を絞っていきます。

１ABC　という４桁の数字を考えると（１）で得た知見から以下の事が分かります。

Cが使える数は０～８の９種類から１種類を除いた　８種類
だから　Bが０⇒１　１⇒２　のように　１増える毎に　８個ずつ題意の条件を満たす数字が増えていく。
だから　Cが０⇒１　１⇒２　のように　１増える毎に　９×８＝７２個ずつ題意の条件を満たす数字が増えていく。

999-648 ＝351個
351÷72＝4.875
この式が示すところはAの種類は４つ以上である　という事です。
Aが　０、１、２、３　の４つだとすれば題意の条件を満たす数字は　７２×４＝288個あるという意味です。
以上の事から　Aは４である事が確定します。

残りは　351ー288＝63個です。
『Bが０⇒１　１⇒２　のように　１増える毎に　８個ずつ題意の条件を満たす数字が増えていく。』
事を利用すれば、Bが０～７までの８種類使える時に　８×８＝６４個となる事が分かります。

よって　B＝７　が確定し、１個オーバーしていますから、１個引けば良いでしょう。
『147C』の中で最も大きい題意を満たす数字である　1478 から１つ戻った値
１４７７　が答えとなります。

場合の数、整数に長けた方は以下のようにすれば早いでしょう。

999-648＝351
351÷8＝43余り７
8進数の1桁目が43回繰り上がったと考えます。
繰り上がった43という数字は10進数です。10進数の43は9進数では47ですから9進数の世界では47回繰り上がります。
よって　『147C』
余りは7でしたから最後に７を足します。
よって　1477　が答えとなります。

もっと簡略化すれば
999÷8＝124余り7
8進数の1桁目が124回繰り上がったと考える。
繰り上がった124という数字は10進数です。10進数の124は9進数の147ですから　余りの7を足して
答えは　1477 となります。

(追記)
この手法で解く場合は　1477 が 9の倍数になっていないかをチェックする必要があります。
例えば 998番目を求める場合
998÷8 = 124 余り6
124(10進数)⇒147(9進数)
ゆえに　1476 とすると間違いです。1+4+7+6＝18となり　9の倍数になるからです。
よって　1475 が答えとなります。
この124余り６の　６　という数字の意味は　1桁目で使える数の６番目　という意味です。
ここは注意が必要な点です。
(追記終わり)

１桁目が8進数、それ以外が9進数の世界　とみなす事も出来るでしょうか。
そう考えれば解きやすいように思います。

ちなみにですが、以下の問題集では本問題をひたすら場合分けをして解く解法のみが示されています。
大手塾では過去問集の解答ではなく、スマートな解法を習う事が出来るでしょうから、灘中学の過去問演習の指導においては塾が有利かもしれませんね。

過去問演習では以下のシリーズをオススメしております。
スマートな解法例が多く、非常に学習効果が高いと感じます。
予習シリーズを一通り終えた後の自学自習にはグノーブルの過去問演習が大変オススメです。

御参考になりましたら。

あとがき

整数の世界、n進法の世界、場合の数の世界　を股にかけるとても良い問題だと思います。

子供心に研究のしがいがありますよね。

本問題はセンター試験や中堅国立二次に出題されるようなレベル感の問題でもあります。

Musukoが解いた際は粘って粘って粘って　n進法で解いておりました。
アイデア出しに時間がかかっていたため　場合分けで解くのと大差ない時間を消費していましたが（笑）

いやはや九州出張は大変でした。
ブログを更新する暇も無く、しばらく間が空いてしまいました。

以前に書いたかもしれませんが私の優先順位は以下のようです。

１：生きるための時間
２：仕事の時間
３：道場運営の時間
４：ブログ執筆

となっております。

ブログの更新がされない時は　１～３が忙しいのだなと考えて頂けましたら。

九州出張で得た情報や写真なども今後公開予定です。

さて、最近ミスが多いので、記事の内容はまた見直しておきます。

時間が無い中で執筆しておりますので多少のミスは御容赦頂けましたら幸いです。

我が家の学習事例が少しでも家庭学習に取組む皆様の御参考になりましたら望外の喜びです。

ではまた！