大山達雄：パワーアップ離散数学

概要

乱列など、離散数学のトピックスを紹介する。 目次は次の通り。

1. 集合
2. 関係
3. 順列と組合せ
4. 母関数と差分方程式
5. 代数的構造
6. グラフ理論
7. 組合せ最適化

感想

乱列の紹介があったので購入した。 乱列の詳しいことは[Liu, 71]を見よ、 とあるが、 具体的な名称はどこにも書いていない。まったくう。 おそらく共立全書の C.L.LIU 著、伊理正夫、伊理由美　共訳　の「組合せ数学入門」の(1) か (2) を表しているのだとは思う。ただし、どちらも 1972 年出版である。原著の C. L. Liu : Introduction to combinatorial mathematics は 1968 年出版である。

各章に必ず一つあるマンガを書いた主は誰なのだろう。 ちなみに、このマンガの位置がずれている。筋からいえば、 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つの数の倍数/約数の関係になってしまうのだ。

考えてもわからなかったので、 室伏俊明先生の鳩の巣原理(web.archive.org)を見て、 以下まとめる。

まず、任意の正の整数 `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」 にあった。見逃していた。

表記と名称

鳩の巣原理にはいろいろな表記と名称がある。

• (鳩の巣|鳩ノ巣|鳩巣) 原理（pigeonhole principle)
• ディリクレの(箱入れ|引出し)+ 原理 (Dirichlet's (box|drawer)+ principle) （箱入れ|引出し）がある場合は、ディリクレの名前が省略されることがある。
• 部屋割り論法

数式記述

このページの数式は ASCIIMathML で記述している。

書誌情報