Fussy's Diary

囲碁棋士の井山裕太さんが七冠達成するかというニュースを見たのが少し前。そして最近、ついに達成したとのニュースが流れ、新聞でも大きく報じられていました。師匠からは「自由に打て」と指導されていたというので、おそらくその天賦の才能を見抜いていたんじゃないでしょうか。その代わり礼儀にはかなり厳しかったそうです。グーグルの AlphaGo との対戦を見てみたいものです。

囲碁のルール、実は全く知りません。NHK で囲碁の対局をやっていて、たまに見ることがあるんですけどやっぱり何をやっているのか全く把握できません。いや、見ているうちに何となくわかるんじゃないかと期待したのですが無理でした。それならルールを覚えればいいじゃないかと言われそうですが、そこまで興味もなく。

話は変わって、アルゴリズムのコーナーを更新しました。ウェーブレット変換の後半部になりますが、今回は JPEG2000 で使われている変換方法についても新たに追加しています。かなり見直しをしていますので、興味のある方はぜひご覧ください。

リンク先 ... 圧縮アルゴリズム (9) ウェーブレット変換 -2-

囲碁にちなんでこんな問題を選んでみました。

-----

白石 180 個と黒石 181 個、計 361 個の石が横に一列に並んでいる。石がどう並んでいても、以下の条件を満たす黒の石が少なくとも一つあることを示せ。「その黒の石とそれより右にある石をすべて除くと、残りは白黒同数となる。ただし、石が一つも残らない場合も同数とみなす。」 ( 01 東大文系 )

黒石が先頭にあるとその石以降を取り除けば同数となるので、先頭は必ず白石であると仮定できます。また、黒石が末尾にあると、それを取り除けばどちらも同数の 180 個になるので、末尾もやはり白石と仮定できます。
白・黒の石の並び方に関係なく、黒石のある箇所で白石の数を黒石が超えれば条件を満たすことになるので、条件を満たさずに並べるためには黒石の数が白石の数を超えないように並べなければなりません。白石の数は 180 個なので、黒石も 180 個までは条件を満たさないように並べることができます(簡単な例としては、最初に白石を 180 個、その後に黒石を 180 個並べた場合です)。しかし、最後に黒石が一つ余ってしまうため、それを並べてしまえば条件を満たしてしまいます。なお、白石が末尾になるように白・黒同数の 180 個を条件を満たさずに並べることはできません。なぜなら、白石が末尾にあるときはその前にある黒石の数が白石の数を超えてしまい、条件を満たしてしまうからです。よって、命題が証明されました。

この問題は、白石の数を任意の N 個とし、黒石の数を N + 1 個とした場合でも成り立ちます。これは帰納法で証明できます。
N = 1 のときは、黒石がどちらかの端にならないように並べることが不可能なので、命題が成り立ちます。N 個の場合に命題が成り立つと仮定した時、これに白・黒ひとつずつの石を加える事を考えます。条件を満たす黒石の位置(これを P と名付けます)に対し、加える石を両方とも P より先頭側か末尾側のどちらか一方に任意に入れた場合は P の位置で条件が成り立ってしまうため、条件を満たさないようにしたければ、それぞれの石は異なる側に置く必要があります。白を P より先頭側においた場合、P の位置で白・黒同数となり、それ以降は黒石が一つだけ多い状態になります。その部分は白石の数が N 以下なので、条件を満たす位置が新たに見つかることになります。逆に黒石を P より先頭側においた場合、P を含めた末尾側が白・黒同数となり、P を除いた先頭側が黒の一個多い状態となります。これも白石の数は N 個以下なので条件を満たす黒石が見つかり条件を満たすことになります。
よって、命題が証明されました。