川渡りのパズル。

2人のパズル王，サム・ロイドとデュードニーの本に川渡りのパズルが載っている。

サム・ロイドの方は一種類しか取り上げていないが，デュードニーの方はバリエーションをいくつか紹介している。

日本の著名なパズル研究家の一人，高木茂男氏の著作もweb上で公開されており，ちょっと涙が出てきそうなほど嬉しいことである。
その中に，「渡船問題（川渡りの問題）」という章が設けられており，このジャンルにおける古典的な問題が紹介されている。

この手の問題でもっとも有名なのは農夫と狼とヤギとキャベツの問題（Dudeney によれば Alcuin によるものが知られている中でもっとも古いらしい）であろう。

川の一方の岸にキャベツを抱えた農夫と狼とヤギがいる。
ボートを使って向こう岸にすべて移動したいが，あいにくボートにはこぎ手の農夫の他に，どれかひとつしか乗せることができない。
しかも，農夫がいないと，狼はヤギを襲い，ヤギはキャベツを食べてしまう。
果たしてヤギとキャベツが無事なまま向こう岸にすべてを移動することができるだろうか。

もちろん，そのような操作が可能でなければこの問題は面白くない。
そして，ボートに乗る回数を最小にするような運び方にしか興味はない。

高木氏の本には，このパズルの回答が図入りで解説されている。
そこには解が二通りあると述べられているが，そのうちのひとつしか書かれていない。
もうひとつの解について，下に白字で答えを書いておく。

ヤギを向こう岸に連れて行って戻ったとき，次に狼を渡すかキャベツを渡すかはどちらでもよい。そしてそのどちらを選んだとしても残りの工程は一意的に決まってしまうので，これらが二通りの解だということである。

さて，なぜこのパズルを調べたかというと，友人のGK氏に，この問題のあるバージョンを解いてくるようにとGWの宿題を出されたからである。
その問題の条件をメモっていなかったため，ネットで調べたのである。
そのとき，有名なパズル王の著作を覗いてみようという気になり，2人のパズル王を調べたというわけである。

ただ，GK氏が教えてくれたバージョンの問題はまだ見つけていない。
メールで教えてもらうことにしよう。
それか，この記事を読んだらコメントで教えてください。＞GK君

あと，この手の問題をPrologに解かせるというのも，ある意味長年の夢のひとつであるが，これについてもうってつけのサイトが見つかった。
それについては，機会があれば改めて紹介したい。

ふたりのパズル王。

ゆえあって，19世紀半ばから20世紀初頭にかけて活躍した二大パズル作家，アメリカのサム・ロイドとイギリスのデュードニーについて調べた。

このふたりの名は，現代の数理パズル研究の大家，マーチン・ガードナー氏の著作で知ったのだったと思う。
ふたりとも，幼少時にチェスでパズルの面白さにはまったという類似の体験を持っているようだ。
そうすると，日本にも詰め将棋などでパズルに目覚めたパズル作家やパズル愛好家がたくさんいるのかもしれない。

そういえば，10年以上前に，イギリスの片田舎のある大学の図書館で，確かデュードニーの著作を偶然発見したときには，これを日本に持って帰れたらと心底思ったものである。

しかしいまやそのような思いをすることもない。

サム・ロイドの代表的な著作とデュードニーの代表的な著作はどちらもネットで無償で閲覧可能である。

つくづくありがたいことである。

新しいPC.

Windows7マシン，ついに稼動である。
いらなそうな機能をブロックしたり，余計なことをするポインティングデバイスの設定を変更したりと，初手は上々である。

画面がちょうどA4ほどの大きさのノートパソコンなので，とりあえず電子文書を読むのに使うつもりである。
できればパソコンの画面を縦にして使いたいところであるが，おそらくそれは使いづらいだろう。

Windows7の機能はほとんど知らないが，「付箋」というアプリケーションは便利そうである。
UbuntuというLinuxのディストリビューションのひとつにはデフォルトでついていたんだっけかなぁ。
そういう，他のOSで人気のある便利ツールを導入するのは一ユーザとしては大いに歓迎である。

ちょっと思ったんだけどね。

正接関数 tan(x) の加法定理というのは，次のような2変数関数がベースとなっている：
F(s,t)=(s+t)/(1-st).

形式的には，tanθ=t とおくと，正接の n 倍角の公式，つまり tan(nθ) は以下のような漸化式を満たす：

tan((n+1)θ)=F(tan(nθ),t).

さて，多項式 f_n(t)，g_n(t) を次のように定める：
f₁(t)=t かつ g₁(t)=1;
f_n+1(t)=f_n(t)+tg_n(t),
g_n+1(t)=g_n(t)-tf_n(t).

このとき，ちょうど
f_n+1(t)/g_n+1(t)=F(f_n(t)/g_n(t),t)
であって，tan(nθ)=f_n(t)/g_n(t) が成り立つ。

この漸化式に基づけば，tan(nθ) の分母と分子の多項式の次数が n によってどう変化するかを調べられるだろう。

ところで，なんとなく f_n(t) と g_n(t) とは互いに素，つまり，f_n(t)/g_n(t) は約分して簡単にすることはできないのではないかという予想が立てられる。

これは果たして本当だろうか？


こんな風に，正接の加法定理ひとつとっても，それを元手に，ちょっと気になる未知の問題を簡単に作ることができる。


あと，a_k=tanθ_k とおくとき，
tan(θ₁+θ₂+・・・+θ_n) は，分子が a_k たちからなる奇数次の対称式の交代和，すなわち，m を n 以下の奇数として，
(1次対称式)-(3次対称式)+(5次対称式)-・・・+(-1)^k-1((2k-1)次対称式)+・・・+(-1)^(m-1)/2(m 次対称式)
という形の和であり，分母は a_k たちからなる偶数次の対称式の交代和，すなわち p を n 以下の偶数として，
1-(2次対称式)+(4次対称式)-・・・+(-1)^k(2k 次対称式)+・・・+(-1)^p/2(p 次対称式)
という形の和になっている，と推測される。

これを証明するのはそれほど難しくはないだろう。


このように，正接の加法定理はなかなか遊びがいのある玩具（おもちゃ）である。


※　ちなみに，次のような小さな問題も派生した。

派生問題

実数 x に対して，x 以下の整数のうち，最大のものを [x] と表すことにする。
この記号を用いて，自然数 n 以下の最大の奇数や偶数を表す式を作れ。

この [x] という関数は，実数 x が正の数の時には，x を小数表示したときの小数点以下を切り捨てるという操作に対応する。
このような意味をきちんと認識すれば，派生問題の答えは見出しやすくなるだろう。