【挑戦】(数セミ)エレガントな解答をもとむを解く㉚

本記事の内容

本記事は『数学セミナー』(日本評論社)に掲載されている”エレガントな解答をもとむ”に出題されいている問題を1時間で解けるか、という挑戦をする記事です。

本記事を読むにあたり、前提知識は基本的に必要ありませんが、以前紹介した記事の内容を使う場合はその旨を記述することにします。

今回も「エレガントな解答をもとむ selections」に掲載されいている問題です。

前回の問題については以下の記事を御覧ください！

【挑戦】(数セミ)エレガントな解答をもとむを解く㉙

...

for-spring.com

2023.02.27

問題を明示します。

次の数列は有名なフィボナッチ数列です。
$$1,1,2,3,5,8,13,21,34,55,\cdots$$
これは最初の項を$a_0$とすると、$a_0=a_1=1$、$n>1$の一般項$a_n$は
$$a_n=a_{n-1}+a_{n-2}$$
と表すことができます。つまり、一般項は直前の2つの項の和というわけです。では、
$$\begin{eqnarray} &&1,1,2,3,3,4,5,5,6,6,6,8,8,8,10,9,10,11,11,12,12,\\ &&12,12,16,14,14,16,16,16,16,20,17,17,20,21,19,\cdots \end{eqnarray}$$
という数列の一般項はどう表現されるでしょう？

（ヒント）フィボナッチ数列ほど単純ではありませんが、最初の$a_0=a_1=1$は同じで、$a_n\ (n>1)$はそれまでに出てきた2つの項の和になっています。

数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p23.

チャレンジの結果は…？

チャレンジの結果…解けませんでした….
この数列の漸化式っぽいモノは見つけることができましたが、「本当にこれで数列を表現しきれているか」ということを示すことができませんでした。

筆者の解答を紹介します。(解けていないのであまり意味はありませんが)

恥ずかしい話

まず、最初にネタバラシをしておくと、この数列の漸化式っぽいモノを見つけられたのは本当に偶然でした。
「フィボナッチ数列が例として出ているんだから、漸化式が似てるんでしょ？」という安易な発想から、少しひねって見た結果偶然それっぽいモノが見つかったというなんとも情けない話です。

解答

まず、この数列を見たときの第一印象は「何だこりゃ。増えたり減ったりしてる。ヤバそう。」でした。
問題文にフィボナッチ数列が例として出現している以上、問題の数列は恐らく漸化式がフィボナッチ数列と似ているのだろうと予想しました。

単に「似ている」というだけでは何も始まらないのですが….

さて、問題の数列を$\{a_n\}_{n\in\mathbb{N}\cup\left\{0\right\}}$と書いたとしましょう。
恐らく、

であろう、と予想したわけです。
第3項までは、フィボナッチ数列の漸化式のままでOKです。
難しいのは第4項以降です。

そこで、$a_4=3$に注目し、この$a_4$がどのように算出されたのかを予想しました。
問題の数列を見る限り、任意の$n\mathbb{N}\cup\left\{0\right\}$に対して$a_n\in\mathbb{N}$と予想できます。
予想に予想を重ねていますが、数列のすべての項が自然数だとすると、
$$a_4=3=1+1+1,\quad a_4=3=1+2,\quad a_4=3=2+1$$
のどれかで$3$が算出されていることになります。

さて、直感的に一番可能性が低そうな$a_4=1+1+1$の場合について考えてみます。
このとき、
$$\begin{eqnarray} a_4&=&a_0+a_1+a_1\\ &=&a_0+a_0+a_1\\ &=&3a_0\\ &=&3a_1 \end{eqnarray}$$
のどれかのパターンです。

• $a_4=3a_0$の場合
  $a_5=3a_1$が成り立つはずですが、成り立ちません。
• $a_4=3a_1$の場合
  $a_5=3a_2$が成り立つはずですが、成り立ちません。
• $a_4=a_0+2a_1$の場合
  $a_5=a_1+2a_2=1+2\cdot 2=5$が成り立つはずですが、成り立ちません。
• $a_4=2a_0+a_1$の場合
  $a_5=2a_1+a_2=2+2=4$となりOKです。
  しかしながら、$a_6=2a_2+a_3=4+3=7$となり成り立ちません。

などなど、$a_4=3=1+2,\quad a_4=3=2+1$の場合も計算しましたが、成り立ちませんでした。

先程筆者が予想した漸化式(っぽい何か)を思い出してみると、「これがもし正しければ数列の値がところどころ小さくなるなんてことはなくないか？」と思いやはり間違いだったと気が付きました(最初から気づけよという話ですが)。

そうなるといよいよ分からなくなってしまいました。

そこでもう一度フィボナッチ数列の漸化式
$$a_n=a_{n-1}+a_{n-2},\quad a_0=a_1=1$$
を見てみました。
「これと似た形をしているとはいえ、どこを弄くればいいんだろうか」と思うと、やはり添字の部分しか無いわけです。
では、その添字をどうするかという話ですが、数列を再度見たとき、
$$\begin{eqnarray} &&1,1,2,3,3,4,5,5,6,6,6,8,8,8,10,9,10,11,11,12,12,\\ &&12,12,16,14,14,16,16,16,16,20,17,17,20,21,19,\cdots \end{eqnarray}$$
となっており、同じ数字が並んでいることが多い印象があります。
そこで筆者の頭が偶然冴えました。
「もしかして添字も数列だったりするんじゃないか？」と。

非常に安直ですが、「じゃあ、添字の部分も数列にしてしまえ」ということで
$$a_n=a_{a_{n-1}}+a_{a_{n-2}},\quad a_0=a_1=1$$
ではないかと予想しました。
実際に計算してみると
$$\begin{eqnarray} a_2&=&a_{a_1}+a_{a_0}=a_1+a_1=2\longrightarrow\ {\rm OK!}\\ a_3&=&a_{a_2}+a_{a_1}=a_2+a_1=2+1=3\longrightarrow\ {\rm OK!}\\ a_4&=&a_{a_3}+a_{a_2}=a_3+a_2=3+2=5\longrightarrow\ \times\\ \end{eqnarray}$$
となってダメでした。

次に
$$a_n=a_{a_{n-1}-1}+a_{a_{n-2}-2},\quad a_0=a_1=1$$
としてみました。
つまり、フィボナッチ数列の漸化式の$n$の部分を正直に$a_n$に置き換えたということです。
しかし、これではダメだということがすぐに分かります($n=2$を考えれば歴然)。

更に
$$a_n=a_{n-a_{n-1}}+a_{n-a_{n-2}},\quad a_0=a_1=1$$
としてみました。
つまり、フィボナッチ数列の漸化式の添字の$-1$および$-2$の部分を$a_{n-1}$および$a_{n-2}$に置き換えたということです。
計算してみると、
$$\begin{eqnarray} a_2&=&a_{2-a_{1}}+a_{2-a_{0}}\\ &=&a_{2-1}+a_{2-1}=a_1+a_1=2\longrightarrow\ {\rm OK!}\\ a_3&=&a_{3-a_{2}}+a_{3-a_{1}}\\ &=&a_{3-2}+a_{3-1}=a_1+a_2=3\longrightarrow\ {\rm OK!}\\ a_4&=&a_{4-a_{3}}+a_{4-a_{2}}\\ &=&a_{4-3}+a_{4-2}=a_1+a_2=3\longrightarrow\ {\rm OK!}\\ a_5&=&a_{5-a_{4}}+a_{5-a_{3}}\\ &=&a_{5-3}+a_{5-3}=a_2+a_2=4\longrightarrow\ {\rm OK!}\\ a_6&=&a_{6-a_{5}}+a_{6-a_{4}}\\ &=&a_{6-4}+a_{6-3}=a_2+a_3=5\longrightarrow\ {\rm OK!}\\ \end{eqnarray}$$
となり、どうやら良さそうです。
本当に偶然でしたが….

ただ、「よし、証明するか」となったとこころで時間切れでした。

投稿されたエレガントな解答(今回は毛色が違いますが)

誤認していたのですが、この問題では「漸化式」を「一般項」と表現しているようです。

（前略）

答えは、第$n$項を$Q_n$と表すことにして、
$$Q_n=Q_{n-Q_{n-1}}+Q_{n-Q_{n-2}}$$
です。これは『ゲーデル、エッシャー、バッハ』で有名なダグラス・ホフスタッターが考案したので、ホフスタッター数列$Q$と呼ばれています。
　数列$Q$の正体がなんであるかを「エレガント」な方法で求めた人はいませんでした。ほとんどの人は試行錯誤や視察によって求めたようです。しかし、（中略）氏は色々な推理を行い、探索範囲を絞ってからコンピュータで調べて解を見つけました。実は出題者もこれがエレガントに見つかるとは思っていませんでした。そのタネ明かしをすることにしましょう。
　遺伝アルゴリズムというものがあります。これは1960年代末に原理が発見され、最近再評価されているものです。手短にいうと、これは多数のパラメータをもつ関数の最大値を求めるのに解析的方法が使えないとき、進化論でいう自然淘汰などのアイデアを利用して「遺伝の進化」によって解を得ようというものです。
　簡単のために$N$個のパラメータが$0$か$1$の値しか取らないとしましょう。するとパラメータは$0$と$1$からなる長さ$N$のベクトルとして表現できます。おのおののパラメータを遺伝子と思い、ベクトルをこれらの遺伝子をもった個体(または染色体)と思うことにします。最初に乱数を使って多数の個体を作り、ナベの中に泳がせます(いわゆる原始スープ)。おのおのの個体を関数に入力すると対応する会った意が求まります。これがその個体の適者生存度を表わします。つまり、値が大きいほど生き残る度合が高いわけです。
　適者生存度に応じて次の世代に生き残る個体の数の割合を決めます。まさに自然淘汰ですね。世代が変わるとき、もう一つ重要な操作があります。それが交配です。これは図1のように、適者生存度の高いもの同士がお互いの遺伝子を部分的に交換することです。人間の子供に両親の遺伝子が混ざるメカニズムと同じです。さらに、どこかの遺伝子が突然$0$から$1$に変わったりするような突然変異も考慮に入れておく必要があります。もっとも、これはあまり頻繁に起こる(起こす)ものではりません。どれもある意味で確率的なものです。つまり、遺伝アルゴリズムは確率的アルゴリズムの一種です。

　この三つの操作を繰り返して、世代を重ねていくと次第に適者の割合がが高まり、かつ交配(および突然変異)の効果により、最初の方の世代にはなかった高い適者生存度をもつ個体が現われてくるようになります(もちろん確率的に)。こうして、いつかは最大値が求まる(だろう)というわけです。こんなかんたんなことで難しい問題が結構うまく解けることがわかってきました。
　遺伝アルゴリズムを計算機プログラミングに応用したのが、遺伝プログラミングです。これはプログラムそのものを個体として扱います。プログラムはベクトルよりも複雑な構造をもっていますが、図2のような木構造でモデル化できます。遺伝子はこの木の節に相当します。自然淘汰や突然変異の仕組みは遺伝アルゴリズムから容易に類推できるでしょう。交配は図2のように、二つのプログラムの部分(正確には部分技)をそっくり入れ換えて行ないます。

　前置きが長くなってしまいいました。実は最近(1990年頃)、ホフスタッター数列$Q$の式が、ジョン・コーザという人の手による遺伝プログラミングでも止まったのです。しかも、ヒントはなく、与えたサンプルも最初の20項だけでした。遺伝子を表すコードとして与えたのは、$+,\ -,\ n,\ 0,\ 1,\ 2,\sigma$の7種類です。プログラムを表す木の中で、$+$と$-$からはかならず二つの枝が生え、$n,0,1,2$は木の末端にしか出てこないという制限は最初からつけておきます。最後の$\sigma$は、出題に沿っていえば$Q$を意味しますが、プログラムとしては再帰呼び出しを表わします。パラメータ(添え字)が1個なので、そこから出る枝は1本という制限がつきます。自然淘汰を決める適者生存度は20項のうちの正解数で表わします。結局これは、変数$Q$と$n$、加減算、定数$0,1,2$だけで、最初の20項に適合する$Q_n$を表す式を作れという問題$X$を与えたことになります。
　問題$X$を解いたけいs南紀はいわゆるワークステーション程度のもの${}^{\ast)}$で、400個からなる原始スープから出発して50世代までの進化をシミュレーションしました。これを全部で約500回足らず繰り返したのですが、そのうち1パーセントで(正解率100パーセント)プログラムが求まったということです。ただし、できたプログラム正解と等価だけれども一般に無駄のあるものになります。たとえば、単に$n$と書けばよいところに、$(n+n)/2-0$といった式は入ってしまうことがあります。これは人間のDNAにも無駄みたいな部分が多いことと符合します。
　いずれにせよ、ヒントなしで問題$X$を人間が解くことがほとんど不可能と思われることから思うと、遺伝プログラミングはなかなかたいしたものです。エレガントな解答とは無縁だったかもしれませんが、世の中ににはこんなものもあるという意味で紹介しました。

（中略）

$\ast)$　このごろ(2001年)の早いパソコンにくらべると1~2桁ほど遅いものです。

数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p199-p202.

読者の皆様への挑戦状！

今から紹介する問題の解答は来週の日曜日に挑戦します！

有理数を循環小数に展開したときの問題です。循環周期は、上に棒線をつけて表示します。$\displaystyle\left( \frac{1}{3}=0.\overline{3}\right)$
$$\frac{1}{7}=0.\overline{142857}$$
の周期を半分にわけて加えると、$142+857=999$。
$$\frac{1}{17}=0.\overline{0588235294117647}$$
でも、同様にして$99999999$になります。
　それでは一般に周期が偶数桁ならいつも正しいかというと、
$$\frac{1}{21}=0.\overline{047619}$$
ではだめです。どのような条件のもとで、偶数循環周期の有理数で、周期を半分にしたものを加えると$99\cdots9$になるのでしょうか。純循環小数と仮定してかまいません。
　ところで、$9$以外がならぶ例もあります。
$$\frac{1}{39}=0.\overline{025641}$$
では、$666$であり、$\displaystyle\frac{1}{21}$も同じでした。余裕があればこういう場合のことも考えてみて下さい。

数学セミナー編集部編（2001）『エレガントな解答をもとむ selections』日本評論社 p23-p24.

前回の問題は【１時間チャレンジシリーズ】挑戦㉙を御覧ください！

結

いかがでしたか？
今回は数セミの「エレガントな解答をもとむ」に挑戦してみる、という記事でした。

読者の皆様も是非一度挑戦してみて下さい！
そして、「読者の皆様への挑戦状」にも是非挑戦していただき、解答をコメントで教えて下さい！

質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ一週間ほどでお答えします。
(難しかったらもう少しかかるかもしれませんが…)

Twitterでもリプ、DM問わず質問、コメントを大募集しております！

他の「エレガントな解答をもとむ」の問題に挑戦してみたい方はぜひ以下の書籍をお買い求め下さい！