ブログ建てました - 水田単作地帯

勉強したことをアウトプットしようと思って始めました。

浅学非才の身でありますので、ご覧になった方からのご指摘お待ちしております。

数学科を目指しておりますが、情報系の学科で経済と法律を勉強しています。

遊びに行く友達もいないので、春休みは勉強に勤しんでおります。

今日は(日付変わったので厳密には昨日は)塾でした。

以下の3問を通じて、鳩の巣原理による組み合わせ論の解法を教えました。

mを2および5と互いに素な自然数とする。mの倍数で

111....11(各桁が全て1)

なるものが存在する。

座標平面の任意の格子点を赤、黄、青のいずれかで塗る。
このとき、4つの格子点を頂点とする(任意の辺がx軸またはy軸と平行な)長方形で全頂点が同じ色に塗られているものがある。

ある大学にて20人の生徒が6つの講義をとる。
どの生徒も6つの中から自由に受ける講義を選択できる(全部受けないこともできる)。
このとき、ある5人の生徒と2つの講義A,Bを選びいずれかが成り立つようにできるだろうか。

・5人とも講義A,Bをとっている。

・5人とも講義A,Bをとっていない。

これらを通じて、組み合わせの大局的(爆発的)な性質を鳩の巣原理に帰着することで簡単にできることを教えました。

ちなみに次の問題は授業の2日前から格闘してるのですがまだ解けてません。エレガントな(そうでなくてももちろんいいです)解答またはヒント誰か教えて下さい。

明日は、O'REILLYの「GNUソフトウェアプログラミング」を読んだ感想か確率微分方程式か代数幾何の記事を書きます。

あるパーティで1,2,3,...,1977,1978で番号付けられた人がいる。6つの国があり、どの人もそれぞれその6つの国の中から来たという。

このとき、ある人の番号はその人の国から来た2人の番号の和になるか、その人の国から来た1人の番号の2倍になる。

以上です。

以下答です。

1
11
111
：
11....11(m桁)

をmで割った余りを考える。

この中にmで割った余りが0のものがあれば自明。したがってmで割った余りがそれぞれ1,2,...,(m-2),(m-1)のいずれかであるとしてよい。

鳩の巣原理より、上のm個の数のうち異なる2数で、mで割った余りが同じものが存在する。

その2数のうち大きい方から小さい方を引けば111....11 $\times$ (10のべき乗)になる。また2数のmで割った余りは同じなのでその111....11 $\times$ (10のべき乗)はmで割り切れる。

mは2,5と互いに素なので、上の111....11はmで割り切れる。

無限にある11....111の中から有限個に注目すればよい。これを通して、有限な範囲で考えれば解けることがあると教えた。

鳩の巣原理より、{(0,0),(0,1),(0,2),(0,3)}のうちある二組は同じ色に塗られている。

同じ理由で、{(1,0),(1,1),(1,2),(1,3)},{(2,0),(2,1),(2,2),(2,3)},...,{(18,0),(18,1),(18,2),(18,3)}に対しても同じことが言える。

4つの頂点のうち2つがある色で塗られているとして、その場所と色の種類の選び方は ${}_4C_2\times$ 3=18種類。

鳩の巣原理より、 {(0,0),(0,1),(0,2),(0,3)},{(1,0),(1,1),(1,2),(1,3)},...,{(18,0),(18,1),(18,2),(18,3)}の中である2つの組があり、その中のある4頂点は同じ色で塗られており、長方形をなす。

縦の辺で色を揃えてから、横の辺を揃える解き方をした。鳩の巣一発で解けないときは、複数回使って途中のパターンにたどり着かせることも大切だと教えた。

証明してみよう。

生徒aが講義P,Qを取っているときY(a,{P,Q})と書き、またaが講義P,Qを取ってないときN(a,{P,Q})と書く。このようなY,Nの書き方の種類はそれぞれ20 $\times {}_6C_2$ =300種類ある。

Y(-,{P,Q})(もしくはN(-,{P,Q}))の形のものが(同じ{P,Q}に対し)5個以上成り立つことを言えばよい。

鳩の巣原理より、Y(-,-)とN(-,-)あわせて2 $\times$ 4 $\times {}_6C_2$ =120より大きい数成り立っていれば上が言える。

いま、1人の生徒aの6つの講義の取り方のうち、一番Y(a,-),N(a,-)が成り立つ個数が少ない取り方は、3つ講義を受け残りの3つは取らないという取り方であり、このときY(a,-),N(a,-)は総じて2 $\times {}_3C_2$ =6個成り立つ。

これを20人全員がすると、Y(-,-)とN(-,-)あわせてちょうど120個成り立つ。

ここで何かを察する。

6つの講義のうち、3つ講義を受け残りの3つは取らないという取り方は ${}_6C_3$ =20通りである。20人がそれぞれ異なるその20通りの取り方をすれば、命題は成り立たないことがわかる。

「巣」の作り方がしばしば難しいことを教えた。