解3(3)-2016年京都大学特色入試の類題の解答
さて……
問3(3)の解説を始めようと思います.
(2)の解説はかなり長かったと思いますが,この記事が最後ですので引き続きお付き合いください.
(3)は(2)と考え方は同じですが,少し面倒な論証があります.
(3)は(2)に対して初期条件がただ1つに定まっているので解き易いと感じてしまいそうですが,皆さんはどうだったですか?
個人的には,(2)より難しいと感じました.
難度Eです.
aが素数であれば解けた人もいるかもしれません.
しかし,aが2以上の整数に一般化されたことにより,aが合成数のときについても考えないといけなくなりました.
では,早速この問題について考えていきましょう.
初期配置がすべてのカードに1と書かれた状態から有限回の操作後に2と書かれた状態にできるとき,どのような条件が生まれるでしょう?
その条件を数式で表してみましょう.
初期配置がすべてのカードに1と書かれた状態から有限回の操作後に2と書かれた状態にするためには,t回の操作でカードを総計n+sa枚選ばなければなりません(s,tは整数).
すなわち,n+sa=tkが成り立たなければなりません.
この方程式が問題を解くカギとなるのですが,この方程式をどう解くか分かりますか?
ちなみに,(3)でも(2)で用いた補題を用います.ここに再掲します.
証明は解3(2)をご覧ください.
では,以下解答です.
★解答★
★★★★
これで,問3のすべての問題を解けました.
お疲れさまでした.
以下,問3全体の解説です.
(1)は一般入試で出題されてもおかしくないので,解けなかった方は復習しておきましょう.
円順列の問題としては難しいですが,回転して同一になる並べ方がどのようなものなのか?を丁寧に調べれば解くことができます.
(2)は数字を書き換えるという操作の性質を調べることが解法の要でした.性質を見つけたとしても,(2)で示した補題がひらめかないと解けません.
一次不定方程式が解を持つための必要十分条件ですが,これの証明を知っている人はあまりいないのでは?
この機会にぜひ覚えておきましょう.
(3)は組合せの問題というよりも整数の問題でした.
(2)と同じようにグループ分けしても,整数方程式を解くことは簡単ではなかったでしょう
十分性の証明では,1+saがaと互いに素であることに気づけば,n,kがaで何回割れるのかについて場合分けをすれば何か分かるのでは?と思考できるでしょう.
それが(3)を解くうえで最も大切なポイントになるのですが,皆さんは気づけましたか?
最後に.
興味のある方はぜひ勉強してみてください.