噂によると文理共通問題のくせに屈指の難問らしい。文系が解くことを想定している問題を理系が解けないわけがないため難問であるはずはない。一体どんな問題だったのだろうか？
なるほど。新規性が高く厄介そうです。今回はこれを解いてみましょう。
まず状況を整理しましょう。問題文の言っている意味は分かっているでしょうか。まずこういうのは小さい数で実験。数学ってすげえんですよ。物理や化学は試験中に実験なんてできないけど、数学は試験中に実験が出来るんだぜ。何故これを皆嫌うのかが不思議で仕方がありません。
まずそもそもa(n,k)とは何ぞやというところから話がスタートするのですが、これはn個の数字
1,2,4,8,16…
からk個を選び掛け合わせたものの総和です。
例に出ているように、a(4,3)というのは、4つの数字
1,2,4,8
から3つを選ぶ
1,2,4 1,2,8 1,4,8 2,4,8
これの積をとる
8 16 32 64
全部足す
120
ということです。
勘のいい人はもうこの時点で漸化式が見えているのかもしれません。
a(5,3)を考えると、最初の数字に16が追加されます。この場合1,2,4,8から3つ選んだものの総和というのは変わらず存在し、そこに16と残り2つを選んだものの総和が追加されるはずです。
そして、残り2つの総和とは何ぞやと言いますと、a(4,2)に他なりません。これに16 (=2^(n-1))を掛けているため…
a(5,3)＝a(4,3)＋2^(n-1)・a(4,2)
一般のn,kでこれを表すと
という漸化式が導かれます。
ちょっと待って、今何の話しているの？
うるさいな、今いいところなんだ。黙っててくれ。概要を掴むためにとりあえず例を追っていたらなんか脱線して漸化式が出てしまったんだ。しかし考えてみてほしい。
どうすればいいのかがわからないような数列を目の前に出されたところに漸化式が出るって明らかな前進です。俺は今この数列を解き明かすにおいて何らかの手がかりを掴んだのである。少なくともこの問題を理解する上において全く無駄であるとは到底思えません。
とか言って、東大数学は時間制限が厳しいのでそろそろ設問でも読みましょうか。
(1)
ふむ、a(n,2)を求めよと。これは今出した漸化式にk＝2でも入れてみましょうか。
a(n+1,2)＝a(n,2)＋2^n・a(n,1)
a(n,1)ってそれ1+2+4+…+2^(n-1)のことなんだから2^n－1じゃね？
というわけで、k=2のほうの添え字は省略すると
緊急事態発生！ 先生！ これどうやって解くんですか！？
2分ほど考えて、階差を取ればいいことに気付く。階差の和が等比数列の和なのである。
(1)からムズいなおい。
(2)
またしても小さいnで実験。
なるほど、答えは予想ついた。ではどう示そうか。
どうも、最初に出した漸化式
はこの問題の本質を捉えているように俺は思う。少なくともこの漸化式がk＝2を代入しただけで終わるはずはない。これを用いてf_n+1(x)をf_n(x)で表すことを試みよう。
うおおおおおおおおおおお！！！！！！！！
なんと、まとめるだけで示せてしまった。やるじゃないか漸化式。やはり本質を突いていたじゃないか漸化式。
なお、ここではa(n,0)とa(n.n+1)という範囲外の項は＝0であると約束しなければならない。
そして、もう片方は
これで帰納法で示せる。
(3)
次数について連立させればOK。
とか言ってサービス問題かというと微妙にそうではないという。
なんか知らんがここで15分くらいかかったw
……
35分かかりました。
ラップタイム
漸化式が出る…3分
(1)が解ける…10分
(2)で方針が立つ…15分
(2)の答えが出る…20分
(3)で係数比較すればいいことに気付く…30分
(3)の答えが出る…35分
基本的に解法パターン暗記に頼ってないせいか、そこ詰まないだろみたいなところに思考時間を費やしたりすることがあるｗ
こういう新規性が高い問題は、条件を整理するとか、それにより直ちに求まる何らかの性質を導くことが正答に至る鍵になることが多いです。何故なら、初めて見る問題に課されたハードルが、直ちに求まる性質により越えられないほど高かったら誰も解けないからです。
今回は条件を整理するときに、問題を一瞥しただけでは非自明な漸化式を出すことができ、この漸化式を中心に議論を進めればある程度のところまで辿り着けるかなという確信を持つことができました。そして、(2)の前半部分の結論が漸化式から直ちに求まるためこれで漸化式の出番は終了した (容易に同値変形できるため、もうこの漸化式から新たに得られることは無いと想定できる) のですが、最近こういうのをやっていなかったため、(3)で漸化式をうんうん眺めて時間を無駄にしてしまいました。なので僕にとっては(2)より(3)のほうが難しかったです。
なお、大数評価はC (少し易しい) らしい。そんなはずはない。絶対D。
(参考) 大数評価
A：とんでもなく易しい
B：易しい
C：少し易しい
D：ふつう
