OMCE003 参加記
こんばんは。
本記事では 2024/5/24 に開催された OMCE003の感想などを書いていきます。
expert回になります！前回は自分が殆ど考察していない問題に不備があっただけで、実際にはかなり微妙な出来だったので、リベンジ出来たらなと思っていました。さらに、writerにはShota_1110さんがいらっしゃって、Shota_1110さんの回は29→23→34とはっきりと苦手傾向がでているので、リベンジしたいところです（ただ、Shota_1110さんの問題が苦手というよりは、一緒に出題している他の人の問題で失敗しているかんじですが）
今回の問題ページは以下です。
参加時の動き
配点は3-4-4-4-5-7 時間は120分と、expertとしてはかなりあっさりした回が予想される。配点がいじられたのかよくわからないけど、短め早解きというのはあまり結果が出ていないので、少し不安になるが、expertというよりはregularと思って解くことで緊張を抑える。
D
aの素因子でcを割り切らないものが存在する。（しないとすると、2^10>1000でc<=1000となる範囲でa|c^10となる。）
このような素因子pを一つとると、p|aよりp|a^c+bからp|bを得る。
このpで割り切れる回数に注目する vp(a)=nとする
n+vp(b)<=vp(a^c+b)
なので、vp(b)=vp(a^c)=cn以外ありえない。
aの素因数分解をp1^e1…pk^ek*q1^f1…ql^flとし、p1~pkがcを割り切らない素因子,q1~qlがcを割り切る素因子とする。
b=p1^{ce1}…pk^{cek}*xとおく。残った条件はab|c(a^c+b)のみ(正確にはqkについての考察とbの約数のxについての考察のみ）でこれを整理していくと
ax|c((p1^{ce1}…pk^{cek}*q1^{cf1}…ql^{cel}+p1^{ce1}…pk^{cek}*x)
①q_iについて
q_i|cではあるが、指数分割り切る必要がある
②xについて
p_i達と互いに素であることに注意。
x|c*(q1^f1…ql^el)^c
である。
ここから考察を少し迷ったが、p1^{ce1}…pk^{cek}*x<=1000で、k>=1なので、そもそもcは9以下。
一方でc=9とするとp_iとしてありうるものは2のみ。
bは2^9の倍数なので512しかありえない。
残ったaについて、偶数であって
512a|9(a^9+512)を満たすもの。q1^f1…ql^flの条件より、これは9の約数である必要があるので候補が絞れる。実際a=2,6,18
a,b,c1000以下というそこそこ安直気味な解への制約を設けているので、条件の整理方法はいろいろあるが、いい問題と思った。
c<=9の証明とc=9の解算出どちらにも完全な自信を持てなかった（上のような整理を計算用紙上ではあまりちゃんと行っていなかったので…）ため、一旦別問に逃げる。ここの判断でFAを逃しているので計算用紙の使い方は気を付けないといけない。
A問題の解法がパッと浮かばなかったのでBへ
B
図示して、角の等しいところに相似を作ってみたら正三角形が出てきて、どうとでもなりそうな形になったため、こちらにチャレンジ。
実際∠AED=∠AMCなる点Eをとれば（本来は取れるかどうか議論が必要で、解説参照のこと）A,B,M,Eが共円で、しかもAMEが正三角形になる。
AE=AM=xとする。相似比から
BM=MC=16x/19,ED=19x/16 BE=AB+BM=1+16x/19,BD=1+(16/19+19/16)x
あとはxを求める。AB=1,BM=16x/19,AM=x,∠ABM=120°で余弦定理を用いてx=19/5 となりあとはこれを代入するだけ。
初等解を運よく引けたというだけであった。
Cを考えるが、複雑そうな二項係数の和に帰着してしまったため、Aで手を動かしてみる
A
Pから順に樹形図で考えてみる。
最初見たときにPを固定してQ,R,Sを考えていて分からなくなっていたが、Pにいろんな数を入れて挙動を見てみる。
すると、複数のPでQがとりうる値が常に3つで、よく見てみるとmod1110でみるなどするときれいになって、候補の6数は差が1110のペアにでき、このペアの丁度片方のみが次の候補に移ることができる。
これにより、どのPに対してもQの候補は3通りあって、R,Sについても同様の議論ができるので3^3*1110
面白い問題。性質自体は数オリでも問われそうなタイプと思った。
C
どちらも3の倍数の座標になる点の集合をAとする。Aの点Pに対して
原点からPにAの点を割けながら行く方法とPからAの集合を通らずにx+y=36まで到達する方法をかけて、これを各Ｐごとに足す、と整理したがよくわからない。
x+y=33までの近い条件の構造を活用できそうなので、x+y=3nごとの遷移を調べる。
Aの点を一つも通らない方法、Aの点を最後に通る方法、Aの点を最後以外に通る方法で遷移を記述しようとするが、端(x,yが0の点)だけ挙動が怪しそう？
（→端の点は確かに通らないが、一点ごとに見るのではなく、同じ色の点はまとめてみてしまえばよい。どこにいてもその後の遷移の倍率は変わらないので気にしなくてよい。コンテスト中は端とそうでないところで分類して数列を構築していた。）
線分x+y=3n,x,y>=0上のAでない点をBとして以下のように色を塗って考える。
黒→赤は6通り 赤→黒は3通り 赤→赤は5通り（どこにあってもそうなる）
x+y=3kまで丁度一点Aの点を通り、その点がx+y=3k上にあるものをa_k通り
x+y=3kまで丁度一点Aの点を通り、その点がx+y=3k上にないものをb_k通り
x+y=3kまでAの点を通らないものをc_k通り
とする。
a_(n+1)=3c_n
b_(n+1)=5a_n+6b_n
c_(n+1)=5c_n
あとはこれを解く。c_nは等比数列なので見た目よりは大変じゃないし、一般項を求めなくてもよい。
E
今回のキーとなる問題
ニュートンの恒等式により、解のk乗和から基本対称式を表すことができる。ただ、この係数を具体的に書き下すのは難しい。これが今回のケースだと簡単に計算できる問題ととらえ、部分的に計算してみたりするが、綺麗になるのかよくわからない。
k乗和を書くときの典型のxf'/fを見てみるも、結局基本対称式を整理しなければならず、（当たり前だけど）難しい条件の線形和に帰着してしまい、よくわからない。
状況をつかむために一旦次数を小さくして実験してみる。
次数2
x+y=5,xy=c→x^2+y^2=25-2c
次数3
x+y+z=5,x^2+y^2+z^2=13,xyz=c→x^3+y^3+z^3 =3c+35
xy+yz+zx = (5^2-13)/2=6
次数4
x+y+z+w=5,x^2+y^2+z^2+w^2=13,x^3+y^3+z^3+w^3=35,xyzw=c
→x^4+y^4+z^4+w^4 =97-4c
2次の基本対称式=6
3次の基本対称式=0
そもそもこの条件でk(<n)次の基本対称式は不変であることに気づく。さらに、3次以降だとそれが0になることにも気づき、高次の基本対称式には影響を与えないので、次数の低いところでは解を2,3,0,…,0に寄せた方程式と思ってよいこと(180D解説などを参照)などから(x-2)(x-3)x^9998+2024の解とわかる。あとはこれの10000乗和を計算。
基本対称式の値を決めるときに低次のみが寄与する（というかニュートンの恒等式がそういう主張）ということや、今回のケースでは解を疑似的に簡単なものに置き換えられること、などなどに気づかず、断片的な結果だけで解こうとしていたため相当時間を消費してしまった…
本質的な理解が無かったことが浮き彫りになってしまったが、問題がいい証拠でもあると思う。
F
問題文の理解が少し難しい。とはいえ、これよりも簡潔に書くのも難しいと思う。
まず、Ωを視覚化してみると、幅3の立方体を敷き詰めたときの辺の線を引いたものになる。（厳密には格子点なので、直線を引くのはおかしいが、見やすさのため）すべての座標がmod3で2になる点から各軸に平行に3直線を伸ばす感じ。
これをΓ内で書くと、直方体のちょうど1マス分内側に直線が引かれた形になっている。
黒線上の格子点がΩ 青点線の枠内がΓの点
これが空間上に広がっている
続いて、Γから1000個点を取って、それが満たす条件について整理する。
そもそもある格子点Xから距離が2未満になる点の集合は、その点を中心とする幅2の立方体表面及び内部の格子点となる。（つまり27個存在する）
先ほど視覚化した、幅3ごとに引いた線上の格子点（つまりΩの元）どれをとっても、その点を中心とする幅2の立方体表面及び内部にP_1~P_1000は高々一個、ということになる。
ここで、すべての座標がmod3で2になる点（視覚化したΩにおける三直線が交わっている点）を中心として幅2の立方体たちを作ると、（わかりやすさのために小立方体と呼ぶ）
・どの小立方体も互いに交わらない
・Γの座標の条件（下がmod3で1,上がmod3で0)から、このΓの点はすべてどこかの小立方体に含まれる→disjoint unionで書ける
・この小立方体は全部で21/3*33/3*39/3=1001個ある
いま、同一の小立方体から二点選択すると、条件を満たさない。したがって、各立方体からは高々一つしか選べず、1001個から1000個選ぶことから、逆に1個だけ点が選ばれない小立方体が存在する。
点が選ばれない小立方体を固定したのち、各立方体でどの点を選べるか、を計算することとなるが、まず重要な考察として、座標ごとの条件に落とせる。具体的にはある小立方体から選択する点を決定したとき、隣接する小立方体とそこに対応する座標の差が3以上という条件を考えることと同値になる。（幅が小さいので成立してる）
これを用いて各軸方向の小立方体ごとの点の取り方を決める。
たとえばx軸なら33/3*39/3=143個直線があって、点が選ばれない小立方体を含む直線が一つだけある。選ばれない小立方体が(a,b,c)の位置にあるとすると
(a+1)C2*(7+2-a)C2*(9C2)^(143-1)通りある。
よって
N=
∑∑∑(a+1)C2*(9-a)C2*(9C2)^142*(b+1)C2*(9-b)C2*(9C2)^90*(c+1)C2*(9-c)C2*(9C2)^76
∑(a+1)C2*(i+2-a)C2 a=1~i は、aを固定したときに
a-1個の〇と2個の|を並べる方法*i-a個の〇と2個の仕切り
となっているので、aの固定を解除するとa-1+i-a=i-1個のボールと2+1+2=5個の仕切りを並べる方法と同じ（まんなかのしきりによってaが決まる）
よって個の総和はi+4C5となり、Ｎの指数の和が具体的に計算できる。
解いたときには時間が終わっていた。
感想と反省
5問正解96分18秒で10位でした！
Fを時間内で倒せなかった中ではトップだったので、Fを通す以外では成績の上昇が見込めないという結果。ただ、終了2分後にFの計算が終わっていたので、Eでの時間のロスが大きかった結果となりました。
問題セットとしては、expertにしては易し目のものがそろっていましたが、クオリティは高かったと思います。ほぼ無印に感じられたので、7問目を入れるのもありだったのかなと思いました。また、全体的に模範解を引けば計算が軽いのもいいポイントなのかなと思いました。
個別の問題としては全部面白かったのですが、A,D,Fが特に面白かったです。
Aは発想一発感がありますが、こういうのもありだと思います。数オリに出そうなタイプと感じました。
Cは模範解答が面白かったです。この手の経路系の問題はいろいろ解法があるので正答者が増えやすいですよね。
Dは解の制限の仕方や剰余の与え方が人工的で一見地味ですが、剰余を丁寧に追うタイプで、4eであれば前半に仕込むといいタイプの問題かなと思いました。
Eはテクニックとしては何度も出てきていますが、自分の理解の甘さが透ける問題で（少なくとも自分にとって）教育的でよかったです。
Fは条件の整理や問題文の理解がやや難しいですが、ちょうどよい組み合わせの問題だったと思います。おそらく視覚的な設定が最初でそこから問題にしたのだと思いますが、参考になります。
初等幾何に対してはあまり明確なコメントができないですが（今回のBもたまたま運よく初等手法が思いついただけだったので）、計算もできるタイプであって、シンプルながらきれいな問題だったと思います。
この記事が気に入ったらサポートをしてみませんか？