乱列など、離散数学のトピックスを紹介する。 目次は次の通り。
乱列の紹介があったので購入した。 乱列の詳しいことは[Liu, 71]を見よ、 とあるが、 具体的な名称はどこにも書いていない。まったくう。 おそらく共立全書の C.L.LIU 著、伊理正夫、伊理由美 共訳 の「組合せ数学入門」の(1) か (2) を表しているのだとは思う。ただし、どちらも 1972 年出版である。
各章に必ず一つあるマンガを書いた主は誰なのだろう。 ちなみに、このマンガの位置がずれている。筋からいえば、 p.8 と p.150 のマンガは入れ替えるべきだろう。
24 ページから 26 ページに練習問題がある。10 番の問題は次のとおり。
`2k` 個の整数の集合 `{1,2,3, ... ,2k}`から `k + 1` 個の整数をとり出すと， そのうちの1個の整数は必ずもう1つの整数の倍数となっていることを示せ．
そのうち、が指すそのうちは、先に取り出した` k + 1 ` 個の取り出した数たちだろう。 では、もう1つというのはどれだろうか。先に取り出した数を `a` とすると、 ` k + 1 ` 個の取り出した数のうち、`a` を除いた数で、しかも `a` の約数になっているだろう。 つまり取り出したもう一つの整数を `b` とすると、`a` は `b` の倍数であるということを言っている。 言い換えれば、`b` は `a` の約数となるように選ぶということだ。 勝手にとった２個ではそうはいかない。だから、ことばを足すとこうなるかと思う。
`2k` 個の整数の集合 `{1,2,3, ... ,2k}`から `k + 1` 個の整数を適当に選び、この集合を `A` とする。 `A` のなかに一方がもう一方の倍数になる２数が存在する。
これは鳩の巣原理で解く問題と思われる（同書では鳩巣原理と表記）。どうすればいいのだろう。 どれが鳩で、どれが鳩の巣なのかを見極めるのが訓練のしどころである。 同書での解答は略となっていて、考えてもわからない。 どうも偶数と奇数がカギになっていそうだ。たとえば、k = 5 のとき、A={2,3,5,7,X} のときに、 どんな X でもほかの4つの数の倍数/約数の関係になってしまうのだ。
考えてもわからなかったので、 http://www.fz.dis.titech.ac.jp/~murofusi/DST/pigeon.html を見てごまかす。
まず、任意の正の整数 `m` は，0 以上の整数 `k` と 正の奇数 `q` を用いて `m = 2^k q` とあらわされる。 さて， `A` の `n+1` 個の要素を `m_1, m_2, ... , m_(n+1)` とし， 各 `m_i` を上記のように表したものを `2^(k_i) q_i` とする． 各 `q_i` は `2n` 以下の正の奇数であり，`2n` 以下の正の奇数は全部で `n` 個なので， 鳩の巣原理から `q_1, q_2, ... , q_(n+1)` の中に互いに等しい 2 数がある． それらを `q_i` と `q_j` とする． つまり，`q_i=q_j , i != j` 。すると，`k_i < k_j` または `k_i > k_j` なので， 前者なら `m_i` が `m_j` の約数であり， 後者なら `m_j` が `m_i` の約数である．証明終わり。
この問題は、以前買った「入試数学 伝説の良問100」 にあった。見逃していた。
鳩の巣原理にはいろいろな表記と名称がある。
このページの数式は ASCIIMathML で記述している。
| 書名 | パワーアップ離散数学 |
| 著者 | 大山 達雄 |
| 発行日 | 年 月 日 |
| 発行元 | 共立出版 |
| 定価 | （本体） |
| サイズ | A5 版 ページ |
| ISBN | 978-4320015296 |
| NDC |
まりんきょ学問所 ＞ 数学の本 ＞ 大山 達雄：パワーアップ離散数学
