本履歴

購入した古本の履歴と時々プログラミング

数学の証明でバイナリサーチ

プログラムコンテストをやり始めて一番感心したのはバイナリサーチ
32回YES/NO Questionすれば、32ビット整数がわかってしまうなんて。
Q01.その数の最上位ビットは1ですか?
(中略)
Q32.その数の最下位ビットは1ですか?

そして、思ってもみない問題で使えたりして、ほんとうにすごいやつだ。
一般的には、ソートされている集合の中から目的の値を見つけるのに
集合を半分にして、左に入ってますか?右に入ってますか?とやっていき区間を絞っていくというアイデアが、バイナリサーチなのかな。

でも、数学学んでた時ってバイナリサーチっぽい発想無かったよなーと思って日々暮らしていたのだけど、
いやいや実際この発想を利用して証明する問題があることが分かったので、忘れないうちに書いておこう。

この前、大学数学の証明問題 発見へのプロセスを読んでいるときに出てきた問題。

有界な実数列は収束する部分列を持つことを証明せよ

有界とは{1,-1,1,-1,1,-1,...}とかある範囲に収まっている数列をいうのだけど、それが必ず収束する部分列を持つのだそうだ。
上記例では、奇数項をピックアップすれば{1,1,1,1,1,1,...}という部分列ができ、1に収束する(ことが証明できる)。
この問題自体はありがちな問題で、大学1年数学科の学生は見かけるものだと思う。
でも、私自身は大学数学の証明問題 発見へのプロセスを読んでいた時は当時どう証明したのかすっかり忘れていて、
その本の中の生徒と一緒になって考えて、正解にたどり着いた。すなわち、次のように部分列を構成すればOK:

  1. 有界なんだから下界、上界が存在するんじゃね?それをp1,q1としよう。
  2. 区間[p1,q1]を真ん中で左と右に半分にしよう。どっちかの区間には数列が無限個入っているよね? それを[p2,q2]としよう。
  3. これを繰り返していけば区間列{[pi,qi]}を作ることができる。
  4. 各区間[pi,qi]は元の数列を無限個含むので、(添字が前後しないように注意して)元数列から一つ項を選択し部分列を構成すれば、それが収束するのは数列pi,qiが収束することから明らか(はさみうち)


これって無限個の項を含む区間を求めるバイナリサーチじゃんと、本を読んでた瞬間気づいてアハ体験しました。
まあ、無限を相手にしているので、32回では終わりませんがw