解3(3)-2016年京都大学特色入試の類題の解答
さて……
問3(3)の解説を始めようと思います．
(2)の解説はかなり長かったと思いますが，この記事が最後ですので引き続きお付き合いください．
(3)は(2)と考え方は同じですが，少し面倒な論証があります．
(3)は(2)に対して初期条件がただ１つに定まっているので解き易いと感じてしまいそうですが，皆さんはどうだったですか？
個人的には，(2)より難しいと感じました．
難度Eです．
aが素数であれば解けた人もいるかもしれません．
しかし，aが２以上の整数に一般化されたことにより，aが合成数のときについても考えないといけなくなりました．
では，早速この問題について考えていきましょう．
初期配置がすべてのカードに１と書かれた状態から有限回の操作後に２と書かれた状態にできるとき，どのような条件が生まれるでしょう？
その条件を数式で表してみましょう．
初期配置がすべてのカードに１と書かれた状態から有限回の操作後に２と書かれた状態にするためには，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)を解くうえで最も大切なポイントになるのですが，皆さんは気づけましたか？
最後に．
興味のある方はぜひ勉強してみてください．
解3(2)-2016年京都大学特色入試の類題の解答
さて……
問3(2)の解説を始めますが，この問題の解説は(1)以上に長くなります．
読者の方々は覚悟を持って読んでください．
筆者が特色入試の問題を読んだとき，「任意の初期配置でカードに書かれた整数を１にできる？そんなことありえるの？」が第一声でした．
組合せの問題で任意の状態を考えるとなると，気分が萎えますよね．
(2)は難度Dです．
この問題のポイントは，問3を紹介する記事でも書いたように，連続して並ぶk枚を選ぶときに生まれる性質です．
解3(1)の解説で用いたx(1),x(2),...,x(n)をここでも使います．
まず，有限回の操作をしてもすべてのカードに１と書かれた状態にすることができない初期状態が生じるとき，n,kはどんな値になっているでしょう？
恐らく，最初に思いつくのはnがkの倍数になっているときでしょう．
これが一番考えやすい条件です．
……では，「nがkの倍数」という条件を緩和して，「nとkが１以外の公約数を持つ」となったら，有限回の操作後にすべてのカードに１と書かれた状態にできない初期状態は生じるでしょうか？
そこで，次のようにx(1),x(2),...,x(n)をグループ分けします．
G(1),...,G(g)は集合です．
こうしてグループ分けしたときに操作を行うとどうなるでしょう？
……実は，操作を一度行うとそれぞれのグループでk/g枚のカードの数が書き換わります．
当たり前の事実ですが，これがこの問題を解くカギとなります．
なぜなら，各グループの要素の数は等しく，その上操作を行うと各グループで同数のカードの数が書き換わるという事実がとても重要なのです．
極端な例を考えてみましょう．
x(1)=a,x(2)=x(3)=...=x(n)=1で，n=6,k=2としましょう．このとき，g=2です．aはいくつでもいいです．
このとき，一回の操作を行うとそれぞれのグループで２枚のカードの数が書き換わります．
しかし，何度操作を行ってもG(1)とG(2)の全要素を同時に1にすることはできません．
実際に実験してみるとわかります．
同様に，x(1)=a,x(2)=x(3)=...=x(n)=1,n=n'g,k=k'gで，g≥2のとき何度操作を行ってもG(1)とG(2)の全要素を同時に1にすることはできません．
これが解答の指針になります．
すなわち，nとkが１以外の公約数を持つならば，有限回の操作をしてもカードすべての数字を1にすることができない初期配置が存在すると予想できます．
そして，もう１つ別のグループ分けを考えてみましょう．
このときも先ほどと同様に，操作を一度行うとそれぞれのグループでk/g枚のカードの数が書き換わります．
このときについても極端な例を考えてみましょう．
x(1)=a,x(2)=x(3)=...=x(n)=1で，k=6,a=4としましょう．すると，g=2です．nはいくつでもいいです．
そして，G(1)の要素の数をi，G(2)の要素の数をi'とします．
このとき，一回の操作を行うとそれぞれのグループで６枚のカードの数が書き換わります．
操作をu回行ったとします．
すると，各グループは合計6u枚のカードに操作が行われます．
そして，G(1)のカードをすべて１にするためには合計で1+4si枚のカードに対して操作が行われる必要があります（sは整数）．
同様に，G(2)のカードをすべて１にするためには合計で4ti'枚のカードに対して操作が行われる必要があります（tは整数）．
これらはどちらも3uに等しいので，1+4si=4ti'となります．
しかし，これを満たすs,tは存在しませんので，このa,kの条件下ではすべてのカードを１にすることはできません．
同様にして，aとkが互いに素でなければ，有限回の操作をしてもカードすべての数字を1にすることができない初期配置が存在するとよそうできます．
以上の２つの場合を見てきましたが，
- nとkが互いに素ではない
- aとkが互いに素ではない
とき，すべてのカードを１にすることはできないと予想できます．
では逆に，これら以外のときは任意の初期配置ですべてのカードを１にすることができるのでしょうか？
……結論から言うとできます．
それを示すには次の補題が必要になります．
これは，解3(1)で示した次の補題から示せます．
解3(1)で示した補題は，m,pを互いに素な整数としても成り立ちます．証明は全く同じなので，各自で確認しましょう．
そこで，任意の整数nに対してkm≡nとなるkが存在するので，n=1として整数lを用いてkm=lp+1と表されます．
よって，任意の互いに素なm,pに対してmk-pl=1を満たすk,lが存在する．
ここで，m=a,p=bとする．
すると，任意の整数tに対してa(k+tb)-b(l+ta)=1が成り立つので，m,nに関する不定方程式am-bn=1は無限個の解を持つ．
したがって，今回示したい補題は示されました．
この補題が十分性を示すうえで重要になります．
それでは，以下解答．
解答中のGCD(p,q)は，pとqの最大公約数を意味します．
★解答★
★★★★
こうして問3(2)は解けました．
いやぁ……長かったですね．
(3)も同じくらい長いかと思いますが，ぜひ最後までお付き合いください．
解3(1)-2016年京都大学特色入試の類題の解答
どうも．
としなかです．
今回の解説はとても長いです．
ですので，小問ごとに解説を投稿しようと思います．
というわけで，早速問3の解説を始めましょう．
皆さんは解けたでしょうか？
かなり難しかったでしょう．
実際の入試に出題されたら，この大問の平均点は1/10になるでしょうね．（笑）
特色入試では誘導があったので，恐らく6/18くらいは平均点があったと思いますが……（数学好きの猛者の平均点で6/18はあまりにも低いけど）
今回は(1)の解説です．
(2),(3)に比べて幾分か簡単ではありますが，それでもかなり難しかったはずです．
(1)は難度Cです．
それでは解説を始めましょう．
適当なa,nで実験してみて気づいたでしょうか？
まずはa=5,n=5のときについて考えてみましょう．
下のような並びのとき，重複度5になります．（重複度とは，回転して同じ並べ方になるようなものの総数）
実際に，上の並びを回転して同じになるものは以下の４つがあります．
また，次の並びは重複度1です．
他の場合も考えたらわかりますが，a=5,n=5のときは重複度1のものと重複度5のものしかありません．
それに対して，a=5,n=6のときについて考えてみましょう．
このとき，重複度1のものと重複度6の並べ方も存在しますが，次の並びは重複度3になります．
実際に，上の並びと回転して同じになるものは以下の２つがあります．
さて……
n=5のときは重複度は1と重複度5の２つしかありませんが，n=6のときは重複度1と重複度6以外にも重複度3が存在します．
その違いはいったい何でしょうか……？
それはnが素数であるか否かであります．
dをnの約数とすると，重複度dとなる並びが存在します．
すなわち，nが素数のとき，重複度は1とnしか存在しません．
これを指針に解答しましょう．
解答に入る前に，１つ補題を示しておきましょう．
★証明★
まず，m,2m,...,pmのそれぞれをpで割った余りが異なることを示す．
次の式を満たす異なる整数a,bが存在すると仮定する．
このとき，式変形をすると次のようになる．
mはpの倍数ではないので，
となり，1≤a<b≤pであることから，a=bとなる．
よって，m,2m,...,pmのそれぞれをpで割った余りは異なる．
m,2m,...,pmはp個の整数であり，pで割った余りは0～p-1のp種類あるので，任意の整数n' (0≤n'≤p-1)に対してkm≡n'となる整数k (1≤k≤p)が存在する．よって，題意は示された．
★★★★
問3(1)を解く際にこの補題が必要になります．
では，以下解答．
★解答★
ある１枚のカードに書かれている数字をx(1)とし，それから左回りにx(2),x(3),...,x(n)とする．
左にm個回転して同じ配列になるようなものを考える．ただし，1≤m<nである．
このとき，次の式が成り立つ．
このとき，x(1+m)を左にm個回転させたものx(1+2m)もx(1+m)と等しくなるので，x(1)=x(1+m)=x(1+2m)=...となる．
ここで，先ほどの補題より1+km≡0 (mod n)となるkが存在するので，x(1)=x(1+km)=x(n)となる．
よって，x(1)=x(n)である．
同様にして，任意のi=1,2,...,n-1についてx(i)=x(n)となる．
すなわち，重複度nでない並び方は重複度1しか存在しない．
重複度1の並び方はa通りしかない．
以上より，求める場合の数は，
である．
★★★★
これで(1)は求まりました．
(1)でこのボリュームって……と萎えてしまいそうですが，引き続き(2)の解説もご覧ください．
E問3-2016年京都大学特色入試の類題
どうも．
としなかです．
梅雨も本番になり，雨の日が続きますがいかがしていますか？
頭痛もちの人にはつらい日々かもしれません．
体調にはお気をつけて．
というわけで，早速今日の一問．
今日の問題は2016年京都大学理学部特色入試第３問を一般化したもの＋αです．
2016年は京都大学で特色入試が行われた最初の年で，理学部の試験が４時間４問というあまりにも長い試験時間であり，かつ内容が難しすぎると当時話題になりました．
今でも京大理学部の特色入試は凶悪な問題が出揃っており，「日本一数学の問題が難しい大学入試」といっても過言ではないでしょう．
その上，定員５名の入試に毎年約80人が出願するので，倍率もものすごく高いです．
ちなみに，筆者も現役のとき受験しました．（結果はボロボロでした）
というわけで，今日の問題はこちら．
特色入試ではa=2のときについて小問３つに分けて出題されました．(1),(2)がk,nが具体的な値のときについての問い，(3)が本問における(2)でa=2のときについて出題されました．
その問題を今回はaを2以上の整数として一般化し，ついでに(3)も作ってみました．
まぁ，一般化しても解法の本質は変わらないのですが……
ちなみに，(1)はもののついでに挿入した問題です．
(2),(3)とはあまり関係のない問題なので，悪しからず．
本問の解説は長くなるので，投稿するまで時間がかかるかもしれません．
以下，この問題のヒントとなります．
(1)については，多くを語ると解けてしまいそうなのであまり語らないことにします．
回転して同じ並べ方になるのはどのような並べ方なのか，それがいくつあるのか具体的なa,nの値で実験してみるといいでしょう．
(2)について．
連続して並ぶk枚を選ぶとき，その選び方にどのような性質が生まれるのか？
その性質がこの問題を解くカギになります．
(3)について．
これは，「すべてのカードに１と書かれた状態から２と書かれた状態にすることが可能なのはどういったときなのか？」を何らかの形で表現できたら解けます．
解2-cosの積の和の計算の解説
さて……
問2の解説をしていきます．
ぜひ最後までお付き合いください．
今回の問題は任意の異なるcosの積の和を計算するもの．
この問題は気づけばそう難しくありません．
難度Bといったところでしょうか？
とりあえず，解答．
★解答★
上の展開公式より，次の式が得られる．
ここで，0<θ<πのときcosθ+cos(π-θ)=0なので，nが奇数のときと偶数のときに分けて計算すると，
であることがわかる．ここで，
として次の式を計算する．
よって，
であるので，
と求まった．
★★★★
の計算が技巧的でしたが，cosの位相が等差数列であるものの和の計算は有名で，大学入試でもよく出題されます．
解答と同じようにして次の式も計算できるので確認しましょう．
さて……
問2は三角関数の知識だけで解けましたが，次の式はそうもいきません．
というのも，展開公式を使おうとすると計算が煩雑になってしまうからです．
難度Cです．
そこで，今回は次のように考えます．
方程式の解と係数の関係を使って解きます．
ちなみに，問2も次のようにして計算できます．
そして，この計算をするうえで大切な式がChebyshevの多項式（チェビシェフの多項式）です．
まず，次の式を考えます．
このとき，
が成り立つので，この両辺をsin xで割ると，
という漸化式が得られる．
なので，任意のnに対してf_n(x)はcos xのn次式になることが帰納的にわかる．
そこで，次の式でg_n(x)を定める．
すると，g_n(x)はxのn次式となる．
このg_n(x)をChebyshevの多項式と言います．
Chebyshevの多項式には様々な性質がありますが，まずはf_(n-1)(x)=0の解xがどのようなものか調べてみましょう．
f_(n-1)(x)=0かつsin x≠0のとき，
なので，
となる．すなわち，方程式g_(n-1)(x)=0の解は，
となるので，Chebyshevの多項式を調べればこの問題は解けます．
そしてもう１つ．
Chebyshevの多項式を列挙してみましょう．
４つ列挙しましたが，何か気づきましたか？
……実は，
- nが偶数のとき，xの奇数乗の係数は0．
- nが奇数のとき，xの偶数乗の係数は0．
となっているのです！
これは帰納法で示すことができます．
すなわち！！
となっているのです．
ちなみに，
となっているので，ぜひ確かめてみてください．（漸化式から計算できます）
C問2-cosの積の和の計算
どうも．
としなかです．
今日はとても暑いですね．
そんなこんなで，今日の一問はこちら．
高校の授業ではほとんど見かけないシグマの表記ですが，分かりやすく書くと次のようになります．
明日には解答をアップする予定です．
解けた人は次の式も計算してみてください．
これらは高校数学で解けますので，ぜひ考えてみてください．
ちなみに，以下のような等式も成り立ちます．
これは比較的有名な等式なので，検索したら出てくると思います．
（検索先に問2に似た等式が見つかり，その導出過程からこの問題の解法がひらめくかもしれません）
解1-回転体の体積の最小値を求める問題の解説
さて......
朝に投稿した問題の解説をしようと思います．
これは，f(x)の積分を用いてf(x)^2の積分を評価する問題です．
このサイトで投稿する問題としては，簡単な問題に分類されるかな？
とりあえず，難度Bとします．（A～Eの五段階評価）
というわけで，まずは解答．
★解答★
まず，次の不等式が成り立つ．
これを展開すると，次のようになる．
よって，
となり，回転体の体積は少なくともπ以上である．
ここで，f(x)=1とすると，
となるので，回転体の体積の最小値はπである．
★★★★
こうして，問題は解けました．
以下，解説です．
この問題の背景には次の不等式があります．
これは，Schwarz不等式（シュワルツの不等式）と呼ばれます．
この不等式でg(x)=1とすると，今回の問題で使うことができます．
この不等式は，Cauchy-Schwarz不等式（コーシー・シュワルツの不等式）と本質に変わりはありません．
Cauchy-Schwarz不等式は知っている人も多いと思います．
高校数学では，n=2,3のときについての証明がよく取り上げられます．
とても有名な不等式のため多くのサイトで取り上げられているので，証明を知りたい人は検索するといいでしょう．
今回は，積分形のSchwarz不等式を示したいと思います．
★証明★
tを実数とする．このとき，次の不等式が成り立つ．
これを積分して展開すると次のようになる．
これをtについての二次方程式とみると，これは重解を持つか，虚数解を持つかのどちらかである．よって，判別式は0以下となる．したがって，
となり，与式は示された．
★★★★
積分形のSchwarz不等式を使う場面は多くはありませんが，Chauchy-Schwarzと一緒に覚えていてもいいでしょう．
