NS I 数学の構造

期末試験 :

• ２０００年度期末試験 ： Page 1, Page 2, Page 3 (REVISED)

• １９９８年度期末試験

１９９８年度期末試験

Final

• 以下において、グラフはすべて有限無向単純グラフ（点の数は有限個で、向きがなく、ループや多重辺がないグラフ）とします。
• グラフの点の次数とは、その点から出ている辺の本数です。次数が一定のグラフを正則グラフと言います。例えば、７正則グラフは各点の次数がすべて７であるグラフのことです。
• ハミルトングラフは各都市を丁度一回ずつ一周して戻って来ることができるグラフ。すなわち、連結な２正則全域部分グラフを含むグラフのことです。
• オイラーグラフは、出発点に戻ることのできるひと筆書きができるグラフです。
• 平面グラフは、辺と辺が交叉しないように平面に書いたグラフで、平面的グラフは平面グラフに書くことができるグラフです。
• 平面グラフの面とは辺で囲まれた部分のことですが、一番外側も一つの面と考えます。
• 木とは、連結な（つながっている）グラフで閉路（おなじ点を通らずに一周して戻ってくることができるような道）がないものです。

1. 正しいものには ○、誤っているものには × を解答欄に記入せよ。（4pts×10）
   1. 各点の次数がすべて偶数の連結なグラフは、ハミルトングラフである。

   2. 一筆書きはできるが、オイラーグラフではないグラフには、奇数次数の点が必ず2個ある。

   3. 10点上の7正則グラフは少なくとも一つはある。

   4. 今回のNSIは、147人が受講している。受講者の中で、お互いに知っている人の数を調べるとする。すると、奇数人と知り合いの受講者は、必ず偶数人いる。

   5. 連結な平面グラフの辺の数を e、面の数を f とすると、常に、2e ≧ 3f が成り立つ。

   6. 図1のグラフは平面的グラフである。

      

   7. 図2のグラフはハミルトングラフである。

   8. 合計で10人の男女がダンスをした。男性は女性と、女性は男性とのみダンスをした。それぞれが、丁度4回ずつダンスをしたとすると、男性の数と、女性の数は必ず同数でなければならない。

   9. 7点上の木は10種類以上ある。

   10. 高校以上（高校も含みます）の数学は必要だと思う人だけ勉強すれば良い。

2. 答えのみ解答欄に記入せよ。答えに、_nC_m があっても良い。(6pts×10)
   1. 14個入りのキャラメルを一箱買って、守、悟、望、喜子、悦子の、5人の兄弟に分けたい。それぞれが最低1個はもらえるようにすると、何通りの分け方があるか。

   2. 14個入りのキャラメルを一箱買って、守、悟、望、喜子、悦子の、5人の兄弟に分けたい。1個ももらえない子どもがいてもよいとすると、何通りの分け方があるか。

   3. 15両編成の東京発岡山行き19:12発ひかりには、11月1日、164人が乗車していた。このとき、何号車かには、必ず n 人以上の乗客がいたと結論出来る最大の自然数 n を求めよ。

   4. 京都八条口の、コインロッカーは4段24列並んでいる。 このコインロッカーが m 個しか使用されていなければ、必ず、ある段か、ある列に2個続けて使用されていないロッカーがある。このようにいつでも判断できる最大の自然数 m を求めよ。
      

   5. 1 から 1500 = 2²・3・ 5³ までの自然数のうち、2、3、5のいずれかで割り切れるものは全部で、いくつあるか求めよ。

   6. ある連結な k-正則平面グラフには、面が32あり、それらは、三角形20個と、5角形12個であるという。このとき、k はいくつか。

   7. 下の様な 4×6 の格子の中に長方形（正方形も含む）はいくつあるか。
      
   8. 右上の12の点を結ぶネットワークを作る。辺の数字は、その線を建設する価値を点数で表したものとする。一本の線の建設費は全て同じとする。このとき、全ての点が間接的には、全てつながり、一番建設費は少ないが、価値の合計点は、最大にしようと思う。このとき、考えうるもので、価値の合計点が最大であるものは、その合計点がいくつになるか。

   9. 10人の人が互いに握手を交わした。そのうちの 9人の人の握手した回数は、それぞれ、0, 1, 2, 3, 4, 5, 6, 7, 8 回であった。残りの一人の握手した回数が決まればその数を、決まらなければ「決まらない」と書け。

   10. 授業で学んだ符号（Hamming (7,3,1) 符号）を用いて、通信をし、1101110 を受信した。検査行列を下のものとする時、発信したもの（2進7桁）は何であったと考えるのが妥当か。
       

       H =	0	0	0	1	1	1	1
       	0	1	1	0	0	1	1
       	1	0	1	0	1	0	1

3. 下の7問の中から5問選択し解答せよ。（10pts×5）
   1. 8×8 の普通のチェス盤は、白と黒で市松模様にぬってある。このとき、白2マスを除外したものは、その2マスがどの2マスであっても、それ以外の部分を 1×2 の板を、縦又は、横におくことによって敷き詰めることはできないことを示せ。

   2. 8×8 の普通のチェス盤は、白と黒で市松模様にぬってある。このとき、白1マス、黒1マスを除外したものは、その2マスがどの2マスであっても、1×2 の板を、縦又は、横におくことによって敷き詰めることができることを示せ。

   3. 今年のNSIの授業は、28時間あり、毎時間最低１問は問題を考える。ただし、全部で、45問は越さない（45問以下）ものとする。このとき、「丁度10問考える期間がある。」（例えば、3時間目から15時間目に考えた問題をあわせると丁度10問と言うような期間が必ずあるということです。）ことを示せ。

   4. 今年のNSIの授業は、28時間あり、毎時間最低１問は問題を考える。ただし、全部で、45問は越さない（45問以下）ものとする。このとき、「丁度28問考える期間がある。」（例えば、3時間目から15時間目に考えた問題をあわせると丁度28問と言うような期間が必ずあるということです。）ことを示せ。

   5. 3次元空間の格子点（座標がすべて整数である点）に9点が与えられているとき、これらの点を結ぶ線分の中点のうちどれかは格子点上にあることを示せ。

   6. サイズが、2ⁿ×2ⁿ (n≧1) の盤から、単位正方形を一つ抜き取ったものを B_n とする。どのように抜き取っても、B_n は、B₁ で、敷き詰めることが出来ることを示せ。
      例：B₃ ★ のところを抜き取ったもの。
      

   7. K_3,3（下の図参照）は平面的グラフではないことを証明せよ。