まだ挑戦していない方は，ぜひ先を読み進める前に挑戦してみてください。

キーワードは「ユークリッドの互除法」と「フィボナッチ数列」

今回の問題では，「⁠コンパスとハサミを使って，長方形をチョキチョキと切る」というルールが与えられています。そのルールに注意しつつ，「⁠ハサミを使う回数をできるだけ少なくするような長方形を求めなさい」という問題ですね。

このルールがいったい何を意味しているのかを見抜くことが，問題を解くうえで重要になってきます。

今回のハサミ問題のキーワードは，2つあります。

1つは「ユークリッドの互除法」⁠。

もう1つは「フィボナッチ数列」です。

ユークリッドの互除法の代わりに「互いに素」や「最大公約数」がキーワードだと思ってもよいでしょう。

コンパスとハサミの操作は「ユークリッドの互除法」になっている

「ユークリッドの互除法」は，2つの正の整数が与えられた時，その最大公約数を求めるアルゴリズムです。アルゴリズムを学ぶほとんどの人が最初に学ぶアルゴリズムであるうえ，“⁠世界で最古のアルゴリズム⁠”といってよい歴史的なものです。

ユークリッドの互除法は，以下のようなアルゴリズムです。

じつは，今回の問題の「コンパスとハサミを使った操作」は，ユークリッドの互除法そのものなのです。長方形の縦と横を「与えられた正の整数」だとし，問題文に与えられている操作を行っていくと，ハサミを使わずに終わった「最後の長方形」の短辺は，最大公約数になるのです。「⁠コンパスとハサミを使う」という図形的な操作で最大公約数が求められるというのは，おもしろいですね。

なぜ，コンパスとハサミの操作がユークリッドの互除法になっているかを，くわしく見ていきましょう。

長方形Aの長辺をmとし，短辺をnとします。短辺nを半径にして，コンパスで四分の一円を描けるだけ描き，最後に長方形Bが残ったとします。

そのとき，残った長方形Bの短辺はどうなるかというと，長方形Aの長辺mを短辺nで割ったときの「余り（m mod n）⁠」に相当します。

ですから，コンパスとハサミの操作というのは，

• （長辺, 短辺）＝（m, n）の長方形から
• （長辺, 短辺）＝（n, m mod n）の長方形を得る

操作になります。

これを，長辺がちょうど短辺の倍数になるまで繰り返すのですが，これはまさにユークリッドの互除法にほかなりません。今回の問題でいう「ハサミの回数」は，「⁠余りを求める回数（割り算の回数）⁠」に相当します。

ここまでは，アルゴリズムを学んだことのあるプログラマならばよく理解できるはずです。

しかし，ここまでの理解だけで，今回のハサミ問題を解くのは難しいでしょう。というのは，適当な長方形を作って試しても，なかなか40回という数にまで至らず，意外と少ない回数で操作が終了してしまうのです。

言い換えればこれは，ユークリッドの互除法は「非常に効率のよいアルゴリズム」ということでもあります。ハサミの回数が少ないということは，割り算の回数が少なくてすむということになるからです。

「ハサミ40回」の逆から考えるのがポイント

じつは，今回の問題を解くためには，ユークリッドの互除法を使う必要はまったくありません（！）⁠。

今回の問題を解くときには，最初から「ハサミ40回」に挑戦するのではなく，少ない回数から考えるのがポイントです。つまり逆に考えるということです。

短辺が1のとき，どんな長方形でもハサミ0回で終了します。

短辺が2のとき，長辺が3の長方形のときハサミ1回で終了します。つまり，ハサミ1回の最小長方形（a）は，2×3です。

短辺が3のとき，コンパスを1回だけ使って，残りの長方形がさっきの（a）になるようにすれば，ハサミ2回の最小長方形（b）が作れます。長辺を3＋2＝5にすればいいということです。つまり，ハサミ2回の最小長方形（b）は，3×5です。

ということは，ハサミ40回の最小長方形を作るためには

• 「コンパス1回だけ使って切り取った残りの長方形が，一歩手前の最小長方形になるような長方形を作る」

操作を繰り返していけばいいと予想できます。

それは言い換えると

• 「長辺が次の短辺になり，長辺と短辺の和が次の長辺になるような長方形を作る」

という操作の繰り返しです。言葉で説明するとわかりにくいですが，これは次の図のような「らせん」を描くことに相当します。

じつは，このような操作は「フィボナッチ数列」を作り出していることにほかなりません。これが今回の問題の2つ目のキーワードです。

フィボナッチ数列を作り出せば正解が見える

フィボナッチ数列というのは，以下の漸化式で定義された数列です。

F[1] = 1
F[2] = 1
F[k] = F[k-2] + F[k-1]
    (k = 3,4,5,...)

具体的には，フィボナッチ数列は，以下の数列になります。

1, 1, 2, 3, 5, 8, 13, ...

• ハサミ1回の最小長方形は2×3。これは，(短辺, 長辺) ＝ (F[3], F[4])に相当します。
• ハサミ2回の最小長方形は3×5。これは，(短辺, 長辺) ＝ (F[4], F[5])に相当します。

つまり，今回の問題を解くためには「フィボナッチ数列を作り出していけばいい」ということになります。以下，ハサミn回を使う長方形を列挙してみます。

よって，正解は以下になります。

267914296x433494437

この解答が最小面積になることは，数学的にも証明できます。