アメよりムチ!

豊田校・

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

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

受験生のみなさんはそろそろ新年度の生活にも慣れてきて勉強習慣の確立にもうまくいっていることかと思います。ところで皆さんは成績が上がるときとはいつなんだろうと考えたことはありませんか。受験を控えた人ならだれしも成績を上げたいと思っていることかと思います。ではどうしたら成績が上がるか、間違いなく言えるのは授業を受けているだけでは成績は上がらないということです。授業は基本的に受け身な勉強です。先生が言ったことを吸収して終わり、ですよね。このブログを読んでくださっている皆さんに声を大にして言いたいのは、どんな知識も自らの手と頭を使って苦労して苦労して初めて骨に染み込んでかつ変幻自在の武器となる、ということです。よく言われるようにわかると出来るは違うとはこのことを言っているのだと思います。つまり、苦労を伴わずに得たものは一時的であったり表面的なことにしか使えない、一方で悩んで悩んでやっと分かったり得たものはどこにいっても自分を助けてくれる武器となる、ということです。具体例をあげましょう。例えば英単語。単語帳を何度も見たり何度も書き写して覚えた単語は長文で出てきてもパッと意味を取れますよね。例えば数学の公式。とりあえず公式の型だけ覚えた人とその導出まで繰り返しやってマスターした人。応用力があるのはどちらか、明らかですよね。そんなわけで皆さんにも四苦八苦しながら問題に取り組んでほしいわけです。その経験は決して無駄ではありません。というわけで、今回はとっておきの難問を用意しました。個人的に人間を育てるのはアメよりムチだと思いますので。では、参ります。

ソース画像を表示

問題

n を3 以上の整数とする. 円周上のn+1 個の点を, 円周をn+1 等分するようにとる. これらの点に0 からn までの数字を1 つずつ番号付けする方法を考える. 2 つの番号付けは, 一方が他方を回転して得られるとき, 同じ番号付けとみなす. 番号付けが美しいとは, a < b < c < d かつa+d = b+cをみたすすべての番号の組(a, b, c, d) について, 番号a が付いた点と番号d が付いた点を結ぶ弦と, 番号b が付いた点と番号c が付いた点を結ぶ弦が交わらないことをいう.美しい番号付けの個数をM とし, x + y ≦ n かつx とy の最大公約数が1 であるような正の整数の
組(x, y) の個数をN とする. このとき,
M = N + 1
を示せ.(参考URLhttps://www.imo-official.org/problems.aspx)

解答

まず次の補題1を示す。

補題1

美しい番号付けがされた円周上の点を結ぶ任意の3つの弦について、その中の一つによって分けられる二つの円周(弧)の中に他の二つの弦は含まれる。

nに関する帰納法で示す。

n=3のときは四つの弦が四角形をなすので成立が確認できる。とあるn-1において成立を仮定する。この元でnのときを考える。加えて、とある三つの弦において補題の主張が成り立たないと仮定する。このときもしその弦をなす点の中にnがないと仮定するとこの点を取った番号付けにおいても成り立たない三つの弦が存在することになり帰納法の仮定に矛盾する。同様に0が含まれていない場合も矛盾する。弦の数が三つであることから端点が0とnの弦が存在することになる。よってこの三つの弦は和がnの弦である。次に0の隣にある点xとnの隣にある点yを考える(この時この二つの点が作る弦によって分けられる円周のうち0とnを含まないほうにこのふたつの点をとる)。もしx+y=nならxとyがnと0でないことに矛盾する。もしz=x+y<nなら円周上の点にzとn-zが存在しこに二つの点が0とnの間にあることが容易に確認できる。しかしこれは前半と同様に矛盾である。もしz>nであったら円周上にz-nと2n-zが存在しこれまた同様に矛盾が生じる。以上より補題が示せた。

次にもう一つ補題を示す。

補題2

n+1個のある美しい番号付けからnを取った番号付けが美しいための必要十分条件は取った後の番号付けが美しくかつ取る前の番号付けにおいて補題1の主張が成立していることである。

必要性は明らかなので十分性を以下で示す。n-1における美しい番号付けにnをくっつけた番号付けを考える。このとき仮定の元で新たに作られた番号付けが美しいことを示せば良い。任意の二つの和が等しい二つの弦をとる。この二つの弦の和がnのときは仮定から良い。nより小さいときも同様。nより大きいときは新しい番号付けにおいて補題の主張が成り立つことから特に和がnの弦らを考えるとこの弦らは全ての番号を使うことから円周上の点は等分点なこともあわせるとすべて平行になる。よってこの弦ら全てに垂直な直線がとれて、x+y=kのとき(n-x)+(n-y)=2n-kなことから、この直線に対象移動することによって前半の議論が適用できる。よって示せた。

以上を用いて命題をnに関する数学的帰納法で示す。

n=3のときは容易に確認できる。とあるn-1で命題が成立していると仮定する。これにnをくっつけたとき全てのnにおける美しい番号付けが得られることは補題1と2から確認できる。そしていくつの新しい美しい番号付けが得られるかを考える。0の隣にある二つの数をαとβとおき、α+β=tとおく。もしt=nなら αもしくわβがnにならざるを得ないので2通りに決まる。もしtがnと一致しないならば和がnの弦らが平行なことからnの場所は一つに定まる。よって新たに増える美しい番号付けの数は0とnが隣り合っているものらの個数に等しい。帰納法の仮定より新たに増える美しい番号付けの個数とx+y=nかつxとyは互いに素な正の整数の個数、すなわちnより小さくnと互いに素な正の整数の個数に等しい事を示せば良い。α+β=nを満たす美しい番号付けについて0から時計回りに i個ずれたところにある数をf(i)とおきf(-i)も同様に定義する。ただしiはmod nでみた値を持ってくる。まず和がn-1の弦らが平行なことからf(a)=n-1とおくとf(i)+f(a-i)=n-1である。つぎにこの美しい番号付けの性質からf(i)+f(-i)=nである。以上から容易に正の整数kを用いてf(-ka)=kの成立が確認できる。よってkaはkを動かすことにより0からn-1までの値を全て取れる。故にaとnは互いに素である。加えてこのとき番号付けは美しい。以上より帰納法が完結した。(終)

ソース画像を表示

さて、以下でどのようにしてこの解答にたどり着いたかを説明していきたいと思いますよ。まず美しい番号付けを満たす絵をいくつか書いてみましょう。そうすると3つの弦に注目したとき補題の主張が成り立つ場合と成り立たない場合があることにきずきますね。美しいのはどっちかなーって考えてみると補題が成り立ちそうだなって思ますね。さて本題に戻ってみると、まずは帰納法が思いつきますね。ただ、このままでは(n-1のときとnのときのつながりが必要になってくるので)帰納法のアルゴリズムに乗せにくいですね。そこで、n-1のときの美しい番号付けからどのようにnのときの美しい番号付けが得られるかを考えるわけです。そんなこんなで補題1と2が必要になってくることが見えてきます。ここまできたらもう一息です。α+β=nのときの美しい番号付けと互いに素な整数を結びつけたいわけですが、なにを手がかりにしましょうか。まずfを定義することに関しては問題ないでしょう。そこで思い出すべきは互いに素な整数の性質です。円周上の点が登場してることからmod n に注目することは定石です。これと合わせれば、解答に出てきた性質が思いつくのではないでしょうか。f(a)=n-1に注目するのもn-1のときの美しい番号付けを考えているので当たり前ですね。以上のような考察を経て解答を書き始めるわけです。もちろんたくさんの試行錯誤は必要です(筆者はこの問題を解くのに5時間かかりましたので)。

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

また、電話で0565-41-8558(日除く昼1時から夜10時まで)までご連絡ください!

武田塾豊田校は、自学自習を身につけていき、進化を遂げる君たちを徹底的にサポートしていきます❕

武田塾豊田校の全く新しい環境で君も目指す姿に進化しよう!

もちろん、相談会に参加されたとしても、入塾の強制、勧誘等は一切ございませんのでご安心ください。

 

お問い合わせはこちらまで
武田塾豊田校
〒471-0025
愛知県豊田市西町4丁目25-13
フジカケ鐵鋼ビル3階
TEL:0565-41-8558
担当:石原(13:00~22:00日曜は除く)