#042 ミッシングナンバー

問題

 ホテルの部屋の扉に4と9を使わないで1号室から番号をつけていくと500番目の部屋は何号室か?

イズミの解答への道

 規則性を利用して、上手にかつ地道に数えることで解けるので小学生レベルである。
 この問題の面白いとろは、よりスマートに解く方法がないか、と考えるところである。

解答

解答1-地道に数える

 100号室までは、40号台と90号台の20部屋と、そのほかの部屋のうち1桁が4あるいは9になる 2 × 8 = 16 部屋を除いた64部屋である。
 100号台でも64部屋、200号台、300号台でも64部屋なので、ここまでで
   64 × 4 = 256 部屋
である。また、400号台は存在せず、また500号台から同様に64部屋ずつ増える。
 
 ここまでをまとめると、
   500号台 64部屋(ここまでで320部屋)
   600号台 64部屋(ここまでで384部屋)
   700号台 64部屋(ここまでで448部屋)
となる。800号台をあわせると500を超えるので、求める部屋の番号は800台である。
 
 10号室ごとに8部屋ずつ増えるので、
   810号室までに8部屋(つまり810号室が456部屋)
   820号室までに8部屋(820号室が464部屋)
   830号室までに8部屋(830号室が472部屋)
となり、840号台は存在しないので、
   850号室までに8部屋(850号室が480部屋)
   860号室までに8部屋(860号室が488部屋)
   870号室までに8部屋(870号室が496部屋)
となり、あと4部屋なので、871、872、873、875号室がそれぞれ497部屋目、498部屋目、499部屋目、500部屋目となり、答えは875号室

解答2-8進法を利用する

 4と9が使えないということから、500を8進数で表した数を考えればよい。そこで10進法の500を8進法に直すと、
   500 = 7 × 82 + 6 × 81 + 4 × 80
となるため、764となる。 
 ここで、今回の8進数は4と9を使わず、 0 , 1 , 2 , 3 , 5 , 6 , 7 , 8 から構成されるので、普通の8進数(0から7を使う)を、
   0 → 0 , 1 → 1 , 2 → 2 , 3 → 3 , 4 → 5 , 5 → 6 , 6 → 7 , 7 → 8
のように変換しなければならない。この変換によって 764 は 875 に変換されるので、これが求める答えである。

研究

n 進数

 まずは n 進数について勉強しよう。
 普段使っている 0 から 9 の10個の数字によって数を数える数え方のことを10進数という。
 これに対し、たとえば 0 と 1 のみで数字を数えていくことを考える。するとそれは、
  0, 1, 10, 11, 100, 101, 110, …
と続いていくことになる。
 
 今回は4と9が使われないということから8進数を思いつく。通常の8進数は0から7の8つの数で構成されるもので、
   0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, …, 76, 77, 100, 101, …
のように数えていくものになる。

進数の変換

 では、まずは10進数で表されたある数字を n 進数に変換する方法を考えよう。
 まず表記法であるが、ある数が何進数であるかを明確に表すために、数字の後ろの下側に括弧付きで何進数かを表す。例えば10進数の123は、
  123(10)
と表す。さて、10進数の123は、
  123 = 1 ×102 + 2 ×101 + 3 ×100
と表すことができる。10kで分けているのは10進数だからであり、指数とその係数が、それぞれの桁とその値を表していることがよく分かるだろう。
 
 では、123を8進数に直すときはどうすればよいかというと、この区切りを 8 に替えればよいのである。つまり、
   123 = a × 82 + b × 81 + c ×80
としたときの、a , b , c を求めればよい。これは、地道に計算することで、
   123 = 1 × 82 + 7 × 81 + 3 ×80
より、 a = 1 , b = 7 , c = 3 だと分かる。これが、123の8進法表記である。言い換えれば、
   123(10) = 173(8)
ということである。
 
 逆もこれと同じことをすればよい。例えば5進法の204は、
   2 ×52 + 0 × 51 + 4 ×50
ということであり、これを計算して、54となる。つまり、
   204(5) = 54(10)
となる。また、10以外の n 進数から m 進数への変換は、一度10進数を経由することになる。

特殊な n 進数

 今回は 4 と 9 を使わないといった特殊なものであるため、実際には、
   0 , 1 , 2 , 3 , 5 , 6 , 7 , 8 , 10 , 11 , 12 , 13 , 15 , 16 , 17 , 18 , 20 , 21 , …
と数えなければならない(下線部が変化した部分)。このとき、どのように数字を読みかえればよいかというと、先ほどの■解答2で示した、
   0 → 0 , 1 → 1 , 2 → 2 , 3 → 3 , 4 → 5 , 5 → 6 , 6 → 7 , 7 → 8
といった変換を利用すればよいのことが分かる。

学校で学習するの?

 実は n 進数は以前(S44?S51とH1?H9)は中学校で学習する内容だった(ただし2進数のみ)。しかし、現在の指導要領ではこの n 進数という概念自体を数学で学ぶことはなくなった(一応高校の「情報」という科目に含まれる)。
 また、一般化した n 進数(記数法)については高校卒業までに学習しない人の方が多いと思われるが、コンピュータ関連では2進数や16進数は頻出であるし、今回の問題のように知っていることで思考を簡便化できる場合もある。
 指導要領が「学習すべき最低限の内容」と定められる今、学校では学ばないが重要な内容であることはたくさんあるので、このような機会にぜひ勉強しておきたいものである。

コメント

タイトルとURLをコピーしました