NF杯2023かんそう
ぴーで呼ばれてるのかshino_pで呼ばれてるのか気になっている@shinoshino_pです お久しぶりです
今回はOMCで行われたNF杯(by:京都大学作問サークルさん)の解説を書きます
文化祭数学は得意なので頑張りたい
問題は自分で見てください→
K問題
@学校だったので帰ったらやるか〜と思っていたが一時間目の物理の授業でまさかの10分自習時間が出来たのでとりあえず問題をざーっと見て、一問は通したいと思ってた
僕がOMCで一番好きな108(E)にかなり似ていたので解法も思いつきこれにした。サイクルが3以下なので3のサイクルが何個か、6,12がどのサイクルに入るかの議論をする感じ。
いろいろ考え落として2ペナしたが2時間目が始まるまでに通せてよかった。
B問題
家に帰ってきて今日中に600点くらいは取りたいと思った。
$${(2^{65}+1)^{2024}\mod 2^{130}+1}$$を求めてみる。二項定理で偶数次の交代和が出てきて(1+i)^n+(1-i)^nを思い浮かべたのは良かった(どっかで見たことあった)。計算すると$${2^{1012}}$$なので1012を提出し1ペナ
$${2^{130}+1|2^{1012}+2^n}$$なので$${n=882}$$を提出し1ペナ。ようやく$${2^{102}(2^{910}+1)}$$に気づいてCA。
C問題
f(-1)=0より、奇数次と偶数次に分けると係数の和が同じ(=1~6)なので全部足す。
M問題
学校でトレッキングがあったのでその間ずっと考えてた問題。
n!が約数をいっぱい持つので制約は厳しくなりそう
$${\phi(2n+3)}$$がn!の約数だとだめなので2n+3は素数。gcd(2n+2,n!+1)が1以上なのでn+1は素数。おっ！安全素数じゃん！とテンションが上がってた
2n+3=pとおくと$${2^{\frac{p-1}{2}}\equiv 1(mod p)}$$となり、OMCで見たことある覚えがあったので過去問を全探索。これを最初に見たときは結構印象に残ってたので覚えてた。OMC168Fに感謝ですね
整理するとn+1≡3(mod4)となり、2n+3が素数であることも合わせて素数表を探索する。n+1=51を入れてしまい1ペナ
ペナルティが5分だったので結構誤答に優しかった印象。
E問題
漸化式たてて順に計算していく問題っぽい。最初の操作で場合分けするとa_{n-1}とa_{n-2}で表せる。最初$${a_n=a_{n-1}+a_{n-2}(a_{n-2}+1)}$$としてしまい、n=5まで成り立ったので1ペナ。ミスに気づくまでめっちゃ時間かかった
A問題
想定解と同じ。全球の体積を$${\pi}$$と思い込み1ペナ。1/8を忘れさらに1ペナ
G問題
$${ord (F_n)}$$って求められるのか〜まぁLTE使えそうだし確かに求められそうだな〜とじゅんにーさんの記事を熟読していないのを後悔していました
$${F_{2n}=F_n(F_{n+1}+F_{n-1})=F_n(F_n+2F_{n-1})}$$を使うと$${ord_2(F_{2n})=1+ord_2(F_n)}$$(nは偶数)となり、初項(?)は$${F_{36}}$$まで書き出して予想。ord_2(F_N)=99だろう。
再びあの加法定理を使ってord_3を頑張るとord_2と同じ漸化式になりそう。初項はF_36までを見ても微妙だったのでそんなデカくはならなさそうということでord_3(F_N)=48,49を試して1ペナCA。
F問題
ポロロッカで見たことあったので解法は思いついていた。
a,b,cの重複をOKとすると簡単。逆元とかの考察をした。いろいろペナしてなんとかCA。
H問題
え？？何だこの関数？？？求まるのか？？？？となった
$${\sqrt{x}}$$の小数部分がと0.5との比較なんだけど…と詰まり、f^n(1),f^n(100)を試すもまぁそうだよねという感じ。
$${\lfloor\sqrt{x}\rfloor=n}$$とするとx→f(x)の増加分はn or n+1なので$${\sqrt{x}+\dfrac{1}{2}\geq n+1}$$を考えてみると$${x\geq n^2+n+\dfrac{1}{4}}$$なのでここが境界！うぉぉぉ求まった！
f^n(x)の挙動がn,n+k,n+k+k,n+k+k+(k+1),…なのかn,n+k,n+k+k,n+k+k+(k+1),…なのかで場合分けをしてごりごり計算。計算ミスで2ペナしたときは考察が間違っているのかと不安だったがただの計算ミスで良かった(?)
結構好きな問題でした
一日目終了
I問題
二日目。1000点取れればいいかなと言う感じ。
上式から$${x=cos\dfrac{k\pi}{1012}-isin\dfrac{k\pi}{1012}}$$とおき、下式に代入して実部と虚部を比較、それぞれの２乗和を考えるとうまくnが消えてくれて$${cos\dfrac{k\pi}{1012}=cos\dfrac{23k\pi}{1012}}$$となりk=253k'かk=92k'で場合分けすると$${x^{23}}$$がうまくxや1/xになってくれて$${x^{n+1}=-1とかx^n=1}$$みたいな感じになる。11と1012が互いに素だと思いこんで3ペナするもなんとかCA！
ふりかえり
10完28位でした！ なんとか1000点行けてよかったです
見てみると幾何以外の問題(ただしNは除く)を全部解けたので嬉しい
MとHがかなり好きでした。あとでNは頑張って理解しようと思います(主張が綺麗で好き)
あと強い人って計算ミスをあんまりしないですよね。克服したいなぁ
ここまでお読みいただきありがとうございました 多分今度の記事はAMCです〜