
武蔵野個別指導塾の特徴
共通テスト情報I ビット数と種類の数—桁の個数と並べ方の個数を同じ数にしない|武蔵野個別指導塾

固定長の全ビット列を並べ、0の列を含めた数え方と誤答の反例から種類数を見直します。
よくあるのは、高校生が装置の状態を表すビット数を見て、その数字をそのまま状態の種類数に書く場面です。3ビットと書かれていれば、3種類と答えたくなるかもしれません。しかし、3は横に並べる場所の数です。それぞれの場所に0か1を置いたとき、完成する列の数は別に数えます。
ここでは、指定された長さの列はどれも使用でき、同じ列は同じ状態、異なる列は異なる状態に対応するとします。特別に使えない列は設けません。全部0の列も、長さが合っていれば立派な1種類です。まず小さい場合を実際に並べ、数える対象を目で追いましょう。
何を数える問いか
一つ目の型は、決められた桁数から、使用できる列の総数を求める問いです。各桁の選択肢は0と1の2通りで、ある桁の選択が別の桁の選択を制限しません。桁数を固定し、列の中身を変えて数えます。答えの単位はビットではなく種類、または列です。
二つ目の型は、挙げられた列の一覧が完全かを判定する問いです。並び順が異なれば別の列として扱いますが、同じ並びを二度書いても1種類です。抜けがないか、重なりがないかを別々に調べます。先頭の0を消すと固定長の列を見失うので、表記の長さも条件の一部として残します。
三つ目の型は、種類数についての主張が正しいかを判定する問いです。たとえば桁数と種類数が同じだという主張に対し、一つの桁数について全列を列挙して違うと示せば、その一般的な主張は崩れます。一方、たまたま同じ数になった一例だけでは、他の桁数でも同じだとは言えません。反例がどの主張を否定するかまで説明します。
問題の条件が全列を利用可能としているかは最初に確認します。実際に何種類の状態を割り当てるかが別に決められているなら、使える列の総数と実際に割り当てた状態数は同じとは限りません。以下の問題では、列の総数を問うとき全列を利用できると明示します。
桁と完成した列を分ける
ビットは0か1のいずれかを表す一つの桁です。固定長とは、どの列も決められた同じ桁数で書くことです。列の種類を数えるときは、どこか1桁でも異なれば別の列とします。例えば01と10は、含まれる0と1の個数は同じでも位置が違うため別です。
図1のように、1桁目を決めた後でも、2桁目には0と1の二つの選択肢があります。左側が0の列の組と左側が1の列の組を分けると、両方を重複なく数えられます。図1の4列には00も含まれます。

1桁目が0のとき、2桁目は0または1なので00、01です。1桁目が1のときは10、11です。先頭が違う二つの組に共通の列はありません。また、どの2桁列も先頭は0か1なので、どちらかの組に入ります。重複も抜けもないため、2通りを二組合わせて4種類です。
同じ考えを続けると、既にある列のそれぞれの末尾に0と1を付けられます。元の列が異なれば、末尾を付けた後も元の部分が異なるので、同じ列にはなりません。したがって1桁増えるたびに種類数は2倍です。n桁なら、2をn個掛けた数が全列の個数です。ここでnは正の整数とし、各桁の二つの選択が独立しているという条件を使っています。
種類数は、桁の中に現れる1の個数でもありません。000と111はどちらも3桁の列ですが、1の個数はそれぞれ0個と3個です。さらに001、010、100は1の個数が同じでも位置が異なる3列です。何を同じとみなすかを変えると数え方も変わりますが、ここでは列全体の並びを区別します。
基本例題:3桁の表示
ある表示器は3ビットの固定長の列で状態を区別します。各桁は0か1で、3桁の全列を使用できます。異なる列は異なる状態に対応します。全列を先頭の桁ごとに並べ、区別できる状態は何種類か整数で答えてください。
図2のように、先頭を0と1に分け、それぞれの後ろに来る2桁を00、01、10、11の順で付けます。先頭を固定した後でも、残り2桁に各4通りあることが見えます。

先頭が0の組は000、001、010、011です。先頭が1の組は100、101、110、111です。各組に4列あり、先頭が異なるので組同士は重なりません。両方を合わせて4を2組、8種類です。掛け算では2 × 2 × 2と表せます。3は掛ける2の個数であり、答えの種類数ではありません。
数を確かめるときは、答えの8をそのまま信じるのではなく、表に戻します。各列の長さは3桁で、各位置の文字は0か1です。先頭が0と1の両方について、残り2桁の4通りがそろっています。これで、条件に合わない列を混ぜず、同じ列を重ねず、条件に合う列を漏らさず数えたことを説明できます。
000を除いて7種類とするのは、0だけの列を使えないという条件を勝手に加えた数え方です。000は数として見れば0ですが、ここでは3桁の一つの並びです。何を表すかは対応の決め方によります。表示する状態がゼロに見えるかどうかと、その列が一覧に存在するかどうかは別の判断です。
一覧を使って主張を調べる
標準例題:同じ桁数なら同じ種類数か
二つの表示欄A、Bはどちらも4ビットの固定長です。各桁は0か1で全列を使用でき、異なる列を別の状態に対応させます。Aには「4種類」、Bには「16種類」と書かれています。どちらが全列の種類数として正しいか、先頭2桁で場合分けして答えてください。
先頭2桁は00、01、10、11の4通りです。それぞれに対して末尾2桁も00、01、10、11の4通りあります。たとえば先頭が00の組は0000、0001、0010、0011です。他の先頭についても末尾の4通りを付けられます。先頭が異なる組は重ならず、どの列も先頭2桁の4組のどれかに入ります。
4組それぞれ4列なので4 × 4で16種類です。正しいのはBです。Aの4は桁の数としては正しいものの、全列の数としては足りません。0000から始まる組だけで4列あり、さらに先頭が01、10、11の組もあることを挙げれば、4種類という答えを具体的に反証できます。
16という答えを条件に戻すには、4組の先頭と各組の4通りの末尾を対応させます。どの組も長さは4桁で、全部0の0000もあります。例えば0011と1100は0と1の個数が同じでも位置が違い、別の状態に対応します。個数だけで並びをまとめない点も確認できます。
発展例題:一致した一例から一般化できるか
ある人は「ビット数と全列の種類数はいつも同じ」と主張しています。1ビットと2ビットの固定長を調べ、どちらも全列が使用できるとします。この二つの一覧を示し、主張を判定してください。答えには反例となる桁数と、そこでの種類数を含めます。
1ビットの全列は0、1で2種類です。2ビットの全列は00、01、10、11で4種類です。いずれも桁数と種類数は一致しません。たとえば1ビットには0と1の2列があるので、「いつも同じ」という主張の反例になります。2ビットの場合も別の反例です。
反例は、主張が対象としている条件を満たす必要があります。3桁の列を2ビットの例に混ぜれば反例になりません。また、列をいくつか省いた一覧を出すだけでは全列の数と比較できません。各桁が0か1という条件から網羅した表を作り、その数と桁数を比べることで反証が成立します。
誤答が生まれる位置を直す
3ビットの全列について「3種類」と答えた場合、計算の最初に桁の数を列の数として扱っている可能性があります。図3のように、3つの箱は1列を作るための場所です。箱が3つあることから完成した列が3種類と決まるわけではありません。各箱に0か1を入れてできる列を比べます。

図3では、箱の数を数えた段階で3ビットとわかります。その後で各箱の選択を組み合わせると、完成した列は8種類です。3と8は異なる対象の数なので、片方をもう片方の単位で書くところが最初の食い違いです。修正するときは、まず「何の個数か」を答えの横に添えます。
別の誤りは、000を表示する意味がないと決めて除くことです。問題は全列を利用できるとしているので、意味の有無を推測して除く根拠はありません。000を一覧に戻し、他の列と重ならないことを確認します。反対に、同じ001を2回書いて8列に見せても、異なる並びは増えません。抜けと重複の両方を調べる必要があります。
一覧が途中で止まっているときは、先頭を固定し、残りを順に列挙する方法が役立ちます。順序は数そのものを変えませんが、照合の手がかりになります。表の行数だけでなく、それぞれが指定桁数か、全て異なるか、各組がそろっているかを見ます。
練習:列を作って判定する
次の5問はそれぞれ独立した自作の条件です。各桁は0か1で、指定した固定長の全列を使用できます。異なる列は異なる状態に対応します。先頭の0を省かずに答えてください。
- ある札の状態を1ビットで表します。全列を挙げ、状態の種類数を整数で答えてください。
- ある卓上表示の状態を2ビットで表します。全列を挙げ、「2ビットだから2種類」という主張の正誤を答えてください。
- ある標識は5ビットで状態を表します。先頭1桁ごとの列数と全体の種類数を、それぞれ整数で答えてください。
- ある記録欄は6ビットです。「先頭が0の列と先頭が1の列を合わせて12種類」という主張を判定してください。先頭ごとの列数も整数で答えてください。
- ある表示欄は7ビットです。全列の種類数と、先頭が000で始まる列の種類数を整数で答えてください。先頭の3桁を固定した後も、残る桁は自由に選べます。
練習の答えと道筋
-
全列は0、1の2列で、2種類です。1桁に入る二つの選択をそのまま列挙できます。どちらも1桁であり、0も条件を満たします。元の札の状態に戻すと、それぞれ別の列に一つずつ状態を対応させられます。
-
全列は00、01、10、11です。種類数は4なので主張は誤りです。先頭0の組に00と01、先頭1の組に10と11があり、二組は重なりません。先頭の0も桁として数え、どの列も2桁であることを確認します。
-
先頭を固定すると残りは4桁です。残りの選び方は2 × 2 × 2 × 2で16通りです。先頭0と先頭1に各16列あるので、合計は32種類です。各組の16列は元の5桁の条件を満たし、先頭の違いによって二組は重なりません。例えば00000と10000も別の組に入ります。
-
先頭ごとに残り5桁を選ぶので、各組は2 × 2 × 2 × 2 × 2で32列です。全体は32を2組で64種類となり、12種類という主張は誤りです。先頭が0の組だけでも32列あるので、合計が12という主張を反証できます。各列は先頭1桁と残り5桁で6桁になり、条件に戻しても長さが合います。
-
7桁の全列は2を7個掛けて128種類です。先頭を000に固定すると、残り4桁の選択は2を4個掛けて16通りです。固定した3桁には選択の余地がないので、そこにさらに2を掛けません。16列は全て000で始まり、残り4桁が違えば別の7桁列です。全体の128列の一部として数えられます。
手元に残す要点
- ビット数は一列の桁数、種類数は異なる完成列の個数です。
- 全列が使え、各桁を独立に選べるなら、1桁増えるごとに種類数は2倍です。
- 全部0の列も含め、先頭の0を残して重複と抜けを確かめます。
- 反例は元の条件を満たす列を使い、主張と食い違うことまで示します。
つまずいた場所を見つける
お子さまが答えを出した後は、まず「3は何の数ですか」と尋ね、その数が箱の個数なのか完成した並びの個数なのかを説明してもらいます。箱を数える説明のまま種類数を書いていれば、選択肢を組み合わせる段階を一緒にたどれます。式が合っていても、各2がどの桁の選択を表すかを言えるか確認します。
一覧を作れた場合は、0だけの列と先頭が0の列に印を付け、桁数が保たれているか見ます。さらに先頭を固定した組ごとに残りの列がそろうかを調べれば、抜けと重複のどちらで数がずれたか見分けられます。列の数を答えるときは、一列の長さから完成した並びへ視点を移します。
もう「日東駒専」を目標にしないでください。
武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。
まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。
本気になった日が、入塾の日。
お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。
電話は年中無休。365日、24時間、お電話可能。



