rakki杯誘導＆感想！中編（P5〜P8）

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

こんにちは！rakkiです！今回は先日開催した自作コンテスト、rakki杯について、ヒントや誘導公開タイムの中編です！（~~厳密に解説書くの面倒くさい~~）
もしおかしな点や、これ解きたいけど誘導が足りないよ！みたいなことがあれば、Xでご気軽にDMしてください！
また、解いたから採点してー！！！ってときもDMくれたら採点するかもなので気軽にどうぞ！
問題本文はこちら、まだ解いてない方はぜひ！！

前編
 後編

本ページの使い方

・解けなかった問題や想定解がなにかきになる問題について、誘導、ヒントを見よう！
・★★★を開ける→モチベは伝えた。小問は自力で見つけてね！！
・★★、★★★を開ける→誘導に乗れれば解きやすくなってるはず。
・★、★★、★★★を開ける→本人はこれくらい誘導すれば頑張れば自力で解けるかなーなどと無責任に考えている。解けなかったらDMで文句を言いましょう()
~~どうせこんなコンテストの問題を取っておいても後に解き直す機会ないから、~~
ぜひ誘導CAして、（rakkiにとっての）300,400〜あたりの問題も、ある程度ヒント、誘導つけば解けるぞー！！！ってなってください()

rakki杯P5

★★★

mがある数未満のときの一意に特定できない例と、mがある数のときに一意に特定できる例があればオッケー。実験なども駆使して探していこう。

★★

$ (1) m\leq 90$で一意に定まらないような組が存在することを示せ。
$(4)m=91$のとき、題意が満たされることを示せ。

★

$(1.1)m=76,77,78,79,80$のとき、一意に定まらないような組を一つ求めよ。
$(1.2) m\leq 90$で一意に定まらないような組を$m$を用いて一つ表せ。
$(2.1)$ $A$の各桁の和を$S_A$、$B$の各桁の和を$S_B$、筆算時の$A+B$の繰り上がりの回数を$T$とおくと、$A+B$の各桁の和を$S_A,S_B,T$を用いて表せ。
$(2.2)$一意に特定できない組が存在するとしたら、その2数の差はいくつか。考えられるものをすべて求めよ。

作者コメント・解説

特に$m\leq 89$の証明が気持ちいい一発ゲーでした。

答え

$100+m,100+10m$ が区別不可

自信作。初見だと意外と下限がつかめない…。こういうときはやっぱり実験していくつも見つけていくうちに、これって？となれば成功です。
桁和にmod9の情報が含まれるのは抑えておくと良さげ。m=90の反例はぱっとでてくるとして、m=91だと$ 91*9=819$個は確実に区別される。区別されないやつは…感覚的に明らか桁違くない？となれば一気にゴールが見えてきます。

rakki杯P6

★★★

自由度が高すぎるからこうだったらいいな、の追加条件を入れてしまおう。桁の情報を捉えるには…？

★★

$(1)$ $2^n(4 \leq n \leq 300)$の下三桁が100通りであることを示せ。
$(2) (1)$の100通りについて、$100,10$の位の数の組が全て異なることを示せ。

★

$(1.1)$ $2^{10}=1000+25-1$に注意して、$2^{20},2^{50},2^{100} \pmod{125} $を求めよ。
$(1.2)$ 背理法を用いて$n=1,2,...,100$について、$2^n\pmod{125}$が相異なることを示せ。
$(2.1)$ 背理法を用いて$n=7,8,...,106$を用いて$2^n$と表せ、互いに100の位、10の位が等しいような整数組は存在しないことを示せ。

作者コメント・解説

お気に入りの一問。100の位と10の位のところが01,02,03,...,99一回ずつで循環する。面白い性質で個人的にかなり好き。
これを解くうえで、特に2つのステップがあるのもポイント。
まず、下3桁だけ見れば良いんじゃないかな…とmod1000を考える。ここで、mod合成数はmod素数のn乗に分解して考え、最後に中国剰余定理！と考えるのが定石だったりします。（mod素数だと特にできることが増え、見通しが立ちやすい。）
mod8は$n \geq 4$で0だからmod125。ここで指数のmodは循環する！（鳩ノ巣を考えれば明らか）、特に$a^0 \equiv 1$だから、循環に1が入ってる！
ということで、mod125で1になるのがいつかを考えよう！となります。
ここで、オイラーの定理によって、$2^{100}\equiv1\pmod {125}$がわかるので、一応これが位数（初めて再び1になって循環するタイミング）だと嬉しいなーとなり、それを確認。ここからこれが全て相異なることを示したい…→ないやつって5の倍数→下一桁0だよな？となればゴールです。
オイラーの定理を把握していればmod1000に飛びついても解けるんじゃ…？という見通しが立ちやすいです。
この位数の議論に入ってからラスト1議論挟むところもポイント。
ちなみに代わりに上3桁を見る、という方針もかなりセンスが良いです。
上の桁を決定づけるのは$\log_{10}2^n=n\log_{10}2$の小数部分。nをうまく調整すればこの小数部分も調整できるから上3桁が100~999を取り得ます。
ただこの方針だと$4\leqn\leq300$が突破しにくいんですよねー…。（testerの方に言われてこの方針に気づき、今回は想定の方を気に入っていたため、この解法はブロックさせてもらいました）
nの制限がつくと厳しいけど、こっちのほうが汎用性は高いです()

rakki杯P7

難化改題　$a_{10}<21000$。

★★★

n+1項間漸化式だと響きが難しすぎる…うまく文字数を減らしたい！
うまく不変量を見つけよう。
不等式だから雑に$a_{10}$の範囲がわかればオッケー！nを絞ろう！

★★

$(1)$ $a_1$から$a_n$までの総和を$S_n$と置く。$S_{n+1}$を$S_n,a_2$を用いて表せ。
$(2)$ $a_2<4$を示せ。

★

$(1.1)$$a_n$を$S_n$を用いて表せ。
$(1.2)$ $n>1,n\in \mathbb{N} $に対して$f(S_{n+1},S_{n})=f(S_n,S_{n-1})$となるような2変数関数$f(a,b)$を一つ求めよ。
$(2.1)$ $S_{n+1}>3S_n$を示せ。
$(3)$ $S_{n+1}<3S_n+2$を示せ。

作者コメント・解説

漸化式は色々な解法パターンがあると言われるけど、基本は不変量を見つけてそれを基準に考えるまたは解き方を知っているパターンに帰着が強いです。（帰納法も有用）
この問題では項数が多すぎるので項数をうまく減らした漸化式に帰着させ、不変量から文字を減らす→解く！！という流れを使います。
その後$S_n$について解いてあげると、（狭義単調増加からいくらか議論すればこの数列は一意で、）見た感じ3倍くらいずつ大きくなっていきそう…とわかります。
ここからとりあえずざっと評価すればnが絞れるから確認すればオッケー！ってことです。
裏話としては、最初の想定では$ \sqrt{a+b}< \sqrt{a} + \sqrt{b} $で上から評価して雑に上下同時に評価していたので、当初僕が$a_2=3$のときの$ a_{10}$を21870未満、までしか評価できていませんでした…
$n\leq 3$がわかってるならもっと評価できたじゃん！21870とかいうすごい意味ありげな数値設定にしなくてよかったじゃん！！
…いちいち代入するより一気に評価するほうが僕的感覚では美しいので良しにしましょう。
ちなみに不変量からーとかの議論抜きに$a_{n+1}$について解いてあげてからなんとうまい式変形&帰納法でも$2S_n< a_{n+1}<2S_n+1$が示せるらしいです。すごい。きれい。

rakki杯P8

★★★

sinの総積をどう求めるか…総積で使えそうな性質・定理は…？うまくハマらないパターンもどうにかできるパターンに持っていけないか…？

★★

$(1) \cos{nθ}+i\sin{nθ}=(\cos{θ}+i\sin{θ})^n$を数学的帰納法を用いて証明せよ。
$(2)n$を奇数とする。$\sinθ=s$としたとき、$\sin{nθ}$をsの多項式で表せるので、定数項と$s$の係数、$s^n$の係数の絶対値をそれぞれ求めよ。
$(3)$ $\displaystyle \prod_{m=1}^{n-1}\sin{\frac{mπ}{n}}= 2^{n-1}\prod_{m=1}^{2n-1}\sin{\frac{mπ}{2n}} $を示せ。 (ただし$n$を奇数とする。)

★

$(2.1) $ $\displaystyle \sum_{1\leq k \leq n,k \equiv 1 \pmod{2} } {}_n \mathrm{ C }_k =\frac{(1+1)^n+(1-1)^n}{2} $を示せ。
$(3.1)\sin{2θ}=2\sin{θ}\sin{\frac{π-2θ}{2}}$を示せ。
$(4)s$を$(1)$同様に定義し、$(1)$で得た式を$f(s)$とおく。(すなわち$ f(s)=\sin{nθ}$)
$f(x)=0$の解を$θ$を用いて全て表せ。
$(5)$ 非負整数$s$と奇数$t$を用いて$n=2^st$とおく。$s$についての数学的帰納法を用いて、$n\geq2$について、$\displaystyle \prod_{m=0}^{n-1} \sin{\frac{mπ}{n}}=\frac{n}{2^{n-1}}$を示せ。なお、$n=2$で明らかに成り立つことや、$0<θ<π \Longrightarrow \sin{θ}>0$にも留意するとよい。
$(6) 1,2,3,...,600$のなかに、2の倍数、4の倍数、8の倍数はそれぞれ何個あるか。

作者コメント・解説

(5)の式の証明ができるかの一問。ちゃんと典型だったっぽいこともあり、（大学入試でも誘導付きで似たやつが出ているらしい）後半の中で圧倒的にCA者が多い一問でした（下手したら前半問題くらい解かれてる）。
想定解でのCAはいませんでしたが、ド・モアブル→解と係数で奇数verを証明→帰納法と倍角公式で偶数verを証明。の流れが結構きれいで個人的にかなり好きです。
解と係数とチェビシェフのコンボで奇数はいけるけど偶数はどう処理する…？というのがポイントでした。$2^st$($t$は奇数)みたいな置換、特に2で割り切れる回数とかの議論で結構便利なので、片隅にはとどめとくと良いかも。
さておき、多くの人は1の原始n乗根ωを用いて($x^{2n}-1=0$の解だから、因数定理で)、$\displaystyle 1+x+...+x^{n-1}=\prod_{k=1}^{n-1}(x-ω^k)$に$x=1$を代入して、$n=\prod_{k=1}^{n-1}(1-ω^k)$が成り立つこと、$\sin{\frac{2kπ}{n}}=\frac{ω^k-ω^{-k}}{2i}$などを利用して解いていました。（僕はこの方針使えなかったけど）一個目の式は1の原始n乗根の性質として、使う場面を見かけます。
原始n乗根の性質の一つなので片隅に置いとくと良いかも。
さらに、二個目の式も代数的に処理するのがやや厄介な三角関数を性質を持った複素数に置換して、解くことができるので強いです。この置換も三角関数を含む代数っぽい問題では割と見かけます。
どちらもこういう三角関数&代数処理みたいな雰囲気の問題では頻出。
代数チックな処理でも解けるようになりたい…
ところで、n倍角公式の導出に(nが大きくなると特に)ド・モアブルが刺さるというのもポイントかもですね。証明に帰納法を含んでいるのもあり、加法定理連打より簡単に示せます。
また、(2.1)で扱った変形はちょっとしたroots of unity filterみたいな感じですね。偶数だけ、奇数だけの${}_n \mathrm{ C }_k$を求めるテクニック(任意の数の倍数でもいける)で、これも便利です。

P5〜P8の解説？は以上です。若干雑になってきて、これヒント解説全部見て、多くの人が解答までたどり着けるんか？という感じですが、言われたら内容を追加するので、遠慮なくお伝え下さい！ここまで読んでいただきありがとうございました！後編もぜひ！
後編

投稿日：20時間前

更新日：18時間前