方針
漸化式の分岐を後ろから逆算する。ではの場合が不可能なのでを得る。さらに、、へ順に戻り、とりうる範囲の最大・最小を読む。
解答
(問1)
の式から、なら、ならである。したがってである。
でとする。なら、ならである。よって数学的帰納法により、以上の自然数に対してである。
(問2)
ならとなり、に反する。したがってでありである。で、左辺はで増加するからである。
次にならとなるので不適である。よってかつでありである。
(問3)
となるを求める。ならであり、ならよりである。したがってである。よってである。
またならとなり不適である。したがってで、である。上のの範囲からである。よってである。したがってである。
別解
解法2(逆像の木を作る)
方針
各段の値を作る直前の値(逆像)を列挙する。からを一意に戻し、の逆像を、さらにの逆像をとして集合で整理する。
解答
(問1)
なら、ならなのでである。さらになら、の枝では、の枝ではである。帰納法により(問2)
ならとなってに反する。よってで、左辺はで狭義単調増加であり、が解なのでの逆像を調べると、の枝はとなるため不適であり、から(問3)
の逆像はしたがってである。次にならとなり上の集合に入らない。ではだからよってである。以上から
総評
難度6、計算量5、想定25分。条件付き漸化式は前向きに追わず、から逆算する。解法1は枝を順に場合分けし、解法2は各値の逆像の集合を作った。、という区間と孤立値を混同しないことが重要で、最終値は31で一致する。