整数と場合の数 - 予備校なら武田塾豊田校

豊田周辺の皆様、および武田塾生の皆様こんにちは。

逆転合格専門の予備校・個別指導塾の武田塾豊田校です。

今回の記事では苦手な人が多いと聞く整数問題と場合の数の問題を紹介しようと思います。
たしかにこの分野はパターン化がしにくいため難問率の高い分野です。しかしですよ、その場の思考力が問われる問題こそ腕の見せ所ですね。大学側にみなさんの実力を見せつけてるいい機会なわけです。というわけでみなさんの実力を伸ばすのにうってつけ、つまり知識ありきではなく本物の思考力が問われる良問に取り組んで頂きたいと思います。難しめですが解けたときの感動は折り紙つきですよ。

ではまず整数問題から、参りましょう。

問題1

^{すべての正整数に対して定義され正整数値をとる関数f、gがつねにf(g(n))＝f(n)＋1、g(f(n))＝g(n)＋1の２つの等式を満たす時、すべての正整数についてf(n)＝g(n)が成り立つことを示せ。}

(参考URLhttps://www.imo-official.org/problems/IMO2010SL.pdf)

解答1

まず以下の主張が成り立つことに注意する。(kとは正整数を表すものとする)

(1)f(g_k(n)＝f(n)＋k、g(f_k(n)＝g(n)＋k (ただしg_k(n)とはたとえばg₂(n)＝g(g(n))などを表す)

(2)f(g(n)＋k)＝f_k＋1(n)＋1、g(f(n)＋k)＝g_k＋1(n)＋1

(3)f(n)＝f(m)とg(n)＝g(m)とは同値である

(4)g_k(n)＝g_k(m)のときg(n)＝g(m)となる (fについてもまったく同様)

(5)f(n)≧n＋1かn-1≧f(n)のいずれか一方が必ず成り立つ

(6)fの値域の最小値をa、gの値域の最小値をbとするとf、はａ以上のすべての整数を、

gはb以上のすべての整数を取れる

(7)f_k(a)=a＋kかつg_k(a)=a＋kならばf_k+1(a)=a＋k＋1かつg_k＋1(a)=a＋k＋1が成り立ち、このときf(a＋k)=a＋k＋1かつg(a＋k)=a＋k＋1も成立が確認できる。

(8)正整数Aがa＝f (A)をみたすとき1≦ A≦a-1である。(gでも全く同様)

(1)と(2)はkによる数学的帰納法で簡単に示せる。(3)、(8)は問題文の条件式からすぐわかる。(4)は(1)と(3)を組み合わせるだけである。(5)は背理法で一発。(6)は(1)からすぐわかる。(7)もkによる数学的帰納法と(2)を組み合わせれば良い。以上を用いてとき進めていく。

まずa≦bとしても一般性は失わない。(5)よりf(a)≧a＋1が成り立つので(6)とあわせてとある正整数sが存在してf(a)=f(s)＋1となるのでf(a)=f(g(s))がわかり(6)と(4)を合わせてa＝g(s)となるのでa＝bがわかる。つぎにf(a)≧a＋2を仮定する。このとき(6)よりf(a)=f(t)+2を満たす正整数tが存在するのでf(a)＝f(g(g(t))が成り立つことと(3)よりg(a)=g₃(t)がわかるので(4)よりa＝g(g(t))となるが(8)よりこれは矛盾。よってf(a)=a＋1がわかる。全く同様にg(a)=a＋1である。よって(7)より任意の非負整数jについてf(a＋j)＝a＋j＋1、g(a＋j)＝a＋j＋1の成立が不可避となる。よってn≧aならばf(n)=g(n)＝n+1となる。1≦n≦a-1のときはf(n)+1=f(g(n))=g(n)+1すなわちf(n)=g(n)が任意の正整数で成立することの論証が完了した。(終)

条件はシンプルで面倒な場合分けや計算も必要ない。くわえて背景知識の有り無しで差がつくわけでもない。しかし何をしたらいいかわかりづらく柔軟な思考力が問われる。まさに良問ですね。^_^

では次に手の出しにくいタイプの問題を。

問題2

正四面体を底面に平行なn-1枚の平面で高さをn等分するように切る。残りの面に関しても同様に切ると正四面体は幾つの部分に分かれるか、個数を求めよ。（東工大）

解答2

ひとつの底面に平行なn-1枚の平面をうえから1枚目、2枚目と数えていくときk-1枚目とk枚目にはさまれた正四面体の部分をk段目と言うことにする(ただし0枚目とは四面体の頂点のひとつをさすこととする)。求めるものをh(n)とおくことにしてl(n)=h(n)-h(n-1)(ただしこの時はn≧2)とおいたときl(n)を以下でもとめていく。l(n)とはn段目に入ってる四面体の分けられた部分集合の要素数である。またこの部分集合の形ついては正四面体の面を平行移動したものから構成されること、平面が等間隔で引かれていることらを考慮すればその部分集合である立体の頂点は定ベクトルを使って表せる。以上のことからその立体の側面は三角形に限られる。つまり小さな正四面体になるか、正八面体に限られる。また底面の三角形はその辺に平行な線分によってn²個の合同な三角形に分けられる。底面の三角形と同じ向きの三角形の外心を通り底面の三角形に垂直な直線とn-1枚目の平面との交点を頂点とし同じ向きの三角形を底面とする正四面体は1+2+・・・+n=n(n+1)/2となる。底面と逆向きの三角形を底面をするものは正八面体の側面となるものであるからこの数は1+2+・・・+(n-1)=(n-1)n/2となる。のこりのn段目を埋めるのは逆向きをした正四面体でありこの数は三角形内部にある平行線分らの交点の数を数えて1+2+・・・+(n-2)=(n-2)(n-1)/2となる。すなわちl(n)=(3n²-3n)/2+1となるので、h(n)=l(n)+l(n-1)+・・・l(1)=(n³+n)/2・・・(答)

化学の単位立法格子の考えがあるとわかりやすかったでしょうか。

今回の問題らはあえて解放に至るまでの思考プロセスは述べないでおきました。皆さん自身が四苦八苦しながら問題に食らいついて欲しいからです。自分で苦労して身につけたものは必ず武器になってくれます。すこし考えてわからないとしても粘り強く考えてください。

出来ることなら筆者の想像してなかった美しい別解に出会えるのを楽しみにしてます。

どうしても、なんでそうやったか分からん！どうしたらその解放に至るのか、知りたい方は是非武田塾豊田校までお越しください。みなさんの力になれるのなら我々講師は助力を惜しみません。

武田塾豊田校では、無料受験相談を毎日受け付けております。
目標の立て方はもちろん、勉強の仕方、志望校の決め方等些細なことでも構いませんので、