豊田周辺にお住まいの皆様、および武田塾生の皆様こんにちは！
逆転合格専門の予備校・個別指導塾の武田塾豊田校です！
論証問題を苦手にする人は多いと聞きます。おそらく苦手とする理由はパターン化された問題が少ないことかと思います。普段やったことをどう使いこなすか、それが見えずらいわけですね。しかし、そんな問題でこそセンスと腕の見せ所です。発想力が必要な問題が多いために思いついたときの感動があるのでやりがいは抜群なわけですよ。そんなわけでして、こういった類の問題にはどんどんぶち当たっていくことをオススメしますよ。というわけで、今回は辛口の問題と甘口の問題の２つを用意しました。問題1はちゃんと解ききって欲しいところです。問題2は難しめなので時間がかかってもOKです。では、参りましょう。
問題１
正の整数aとｂが互いに素であるとき、正の整数からなる数列｛ｘ（ｎ）｝をｘ（１）＝ｘ（２）＝１、ｘ（ｎ＋１）＝aｘ（ｎ）＋ｂｘ（ｎ－１）（ｎ≧２）で定める。このときすべての正の整数ｎに対してｘ（ｎ＋１）とｘ（ｎ）が互いに素であることを示せ。
（参考URLhttps://www.densu.jp/nagoya/04nagoyaspass.pdf）
解答1
まずx(n)とbが互いに素であることを示す。n=1とn=2で成立は明らか。とあるnとn+1での成立を仮定。このとき、もしx(n+2)とbが共通素因数をもつとすると矛盾することが仮定とaとbが互いに素であることからわかる。次にx(n)とx(n+1)が互いに素であることを示す。n=1と2での成立は自明。とあるnとn+1での成立を仮定。このとき、n+1とn+2が共通素因数をもつと 仮定すると同様に矛盾である。(終)
解答2
とある2以上のnでx(n)とx(n+1)が共通素因数pを持つと仮定する。このとき、pはbかx(n-1)の少なくとも一方を割り切る。加えて、もしx(n-1)を割り切れないとすると、bがpを因数に持つことになるのでaとbが互いに素であることからx(n-2)もpで割り切れることになり帰納的にx(2)=1がpで割り切れることになり矛盾。よってx(n-1)がpで割り切れることになり同様に帰納的に1がpで割り切れることになり矛盾。(終)
問題２
ｎ≧３とする。円周上の２ｎ－１個の異なる点の集合をEとする。Eの点のうちちょうどｋ個を黒に塗る色分けについて考える。このような色分けのうちで、次の条件を満たすものを「良い」色分けと呼ぶことにする。
「黒の2点を適当に選べば、その2点による分割でつくられる２つの弧のうち一方は、その内部にちょうどｎ個のEの点を含むようにできる。」
Eのどのｋ個の点を黒に塗っても、それがつねに「良い」色分けになるような最小のｋの値を決定せよ。
（参考URLhttps://www.imo-official.org/problems.aspx）
解答
円周上の点に0,1,・・・,2n-2として名前をつける。円周上の2点を結ぶことによって得られる適当な弧がn個の点を含むときその2点を結ぶ。2点x,yが結ばれることはx-y≡±(n-2) (mod2n-1) と同値である。n≡0,1 (mod3) のときn-2と2n-1は互いに素なので点を結ぶことによって得られるグラフは１つのサイクルをなす。よってこのとき最小のkはnである。n≡2のときは3個のサイクルに分かれるのでkの最小値はn-1である。(終)
解説
問題1のポイントはまず論証問題における重要手法の選択です。帰納法、背理法、部屋割り論法、対偶法、が主な論法です。nに関する問題なことから帰納法が最初に出てくるかと思います。しかし、単純に帰納法で解決するかと思いきや、やってみると分かりますがbとx(n)が互いに素でないと上手くいかないことに気ずくかと思います(センスのある人なら漸化式を見ただけでも気ずくでしょうね)。
問題2のポイントは異概念への帰着、今回で言えばグラフ理論のネタが使えることに気づいて欲しいところです(ただし、グラフ理論の難しい定理などは全く必要ないですしもっと言えばグラフ理論を知らなくても良いくらいです)。点を結ぶことによってそれを辿ってできるサイクルが使えそうだな、と思えばあとは解けたようなもんですね。
いずれの問題も少しトゲがあると感じた人が多いかと思いますが、解けて仕舞えばかわいい問題にしか見えなくなるでしょう。１つの問題を完璧にマスターしたと言えるのはこういうことかもしれません。
武田塾豊田校では、無料受験相談を毎日受け付けております。
目標の立て方はもちろん、勉強の仕方、志望校の決め方等些細なことでも構いませんので、
また、電話で0565-41-8558（日除く昼1時から夜10時まで）までご連絡ください！
武田塾豊田校は、自学自習を身につけていき、進化を遂げる君たちを徹底的にサポートしていきます❕
武田塾豊田校の全く新しい環境で君も目指す姿に進化しよう！
もちろん、相談会に参加されたとしても、入塾の強制、勧誘等は一切ございませんのでご安心ください。
お問い合わせはこちらまで
武田塾豊田校
〒471-0025
愛知県豊田市西町4丁目25-13
フジカケ鐵鋼ビル3階
TEL:0565-41-8558
担当：石原（13:00～22:00 日曜は除く）
