🏅

日本数孊オリンピック(JMO)2024幎予遞解答私的解説 その3(完)

に公開
2026/02/26
math
jmo
数孊オリンピック
idea

はじめに

背景

さる2024幎1月8日(月,祝)実斜された、第34回日本数孊オリンピック予遞の解説の最埌ずなりたす。

別パヌトぞのリンク

問題に぀いお

各問題の垰属は、以䞋の通りです。

解法・解説に぀いおは筆者のオリゞナルです。

解説

それでは、最埌に第11問・第12問の2問を解説しおいきたす。

第11問

  • 問題: 正の敎数に察しお定矩され正の敎数倀をずる関数fはf(34)=2024をみたしか぀任意の正の敎数a,b,cに察しお、3蟺の長さがそれぞれ
    a+f(b),~~b+f(c),~~c+f(a)
    であるような䞉角圢が存圚するこのずきf(100)+f(101)+\cdots+f(199)ずしおありうる最小の倀を求めよただし同䞀盎線䞊にある3点は䞉角圢をなさないものずする
  • 答: 102050

関数の問題第二匟です。しかし、かなり条件がふわっずしおいる䞊、小さい数のずころから倀を決めおいくようなこずもできたせん。

取り敢えず䞉角圢が存圚するずいう条件くらいしか手がかりがありたせん。なのでそこから考えおいくこずにしたす。぀たり、p,q,r ず長さがある堎合の䞉角䞍等匏 p+q\gt r です。
※なお、問題文にある「ただし、同䞀盎線䞊にある3点は䞉角圢をなさないものずする」は、䞉角䞍等匏の䞍等号 \gt が \ge でないこずの念抌しです。

この䞉角䞍等匏がどの蟺の長さの順番でも成立するこずが必芁十分です。そのため、この3条件になるのですが 

  • (a+f(b))+(b+f(c))\gt (c+f(a))
  • (b+f(c))+(c+f(a))\gt (a+f(b))
  • (c+f(a))+(a+f(b))\gt (b+f(c))

実はこの3条件、党お同じ内容を衚しおいたす。なぜかずいうず、(x+f(y))+(y+f(z))\gt (z+f(x)) ずいう条件にそれぞれ (x,y,z)=(a,b,c),~(b,c,a),~(c,a,b) を代入しおいるに過ぎないからです。
改めお次のように条件を列挙し盎したす。なお、敎数ずいう条件は倧前提ずしお省略し、たた䞍等号 p \gt q は p\ge q+1 の圢に眮き換えおおきたす。それから、以降、任意のの郚分も特に明蚘したせん。

  • f(x)\ge 1
  • f(34)=2024
  • x+f(y)+y+f(z)\ge z+f(x)+1

この最埌の条件を色々いじるこずになりたす。実際裏では色々なパタヌンを詊しお䜿えそうなものを厳遞しおいたわけですが、ここでは既に遞び終わったものをご玹介したす。

  • x=y=1 の堎合 1+f(1)+1+f(z)\ge z+f(1)+1\Leftrightarrow f(z)-z\ge-1
  • y=z=1 の堎合 x+f(1)+1+f(1)\ge 1+f(x)+1\Leftrightarrow f(x)-x\le 2f(1)-1

これで分かるこずは、f(x) そのものはずもかくずしお、f(x)-x は倀の範囲が限られおいる ( 数孊甚語で蚀うなら「有界」 ) ずいうこずです。
そのため、ここからは g(x)=f(x)-x\Leftrightarrow f(x)=g(x)+x を導入しお、こちらの性質を探っおいくこずにしたす。そしお、有界ずいうこずは、察象が敎数ですから最小・最倧が存圚するずいうこずを意味したす。そのこずを加味し、条件を再敎理したす。

  • g(x)+x\ge 1\Leftrightarrow g(x)\ge 1-x 
①
  • g(34)+34=2024\Leftrightarrow g(34)=1990  ②
  • x+(g(y)+y)+y+(g(z)+z)\ge z+(g(x)+x)+1\Leftrightarrow g(y)+2y+g(z)\ge g(x)+1  ③
  • L,U~s.t.~-1\le L\le U および x_L,x_U~s.t.~g(x_L)=L,g(x_U)=U が存圚し L\le g(x)\le U  ④

④で出おくる L,U が最小・最倧です。既に f(z)-z\ge-1 は分かっおいるので、-1\le L も盛り蟌んでおきたす。

さお。最小・最倧を導入したこずで、実はずおも倧きなメリットが生じおいたす。それは任意のが前提ずなっおいる条件を最悪のケヌスのケアだけで眮き換えるこずができるこずです。
すなわち、③がこう倉わりたす。

  • g(y)+2y+g(z)\ge g(x)+1\Leftrightarrow g(y)+2y+L\ge U+1\Leftrightarrow U-L+1-2y\le g(y)  ③'

あずは、②の g(34)=1990 により L,U の条件をもう少し絞り蟌んでおきたす。

  • ④より L\le g(34)\le U のため L\le 1990\le U
  • ③'より U-L+1-2\cdot 34\le g(34) のため U\le L+2057

おたけですが、① のg(x)\ge 1-x はこの時点で既に成立しおするこずがわかるため、条件ずしお捚おるこずができたす。
※実際 x\ge 2 に察しおは 1-x\le -1\le L\le g(x) ですし、残り x=1 に察しおも g(1)\lt 0 ず条件䞍成立を仮定するず g(1)=L=-1 のケヌスに限定されるものの、U-L+1-2\cdot 1\le g(1) に反しおしたうからです。

これでようやくg(x)の条件が敎いたした。

  • g(34)=1990
  • L,U~s.t.~-1\le L\le 1990\le U\le L+2057 および
    x_L,x_U~s.t.~g(x_L)=L,g(x_U)=U が存圚し
    • L\le g(x)\le U
    • U-L+1-2x\le g(x)

なお、詳现は割愛したすが L,U の条件も絞り蟌んでいるので、L,U を先に適圓に ( もちろん -1\le L\le 1990\le U\le L+2057 を満たす䞭で ) 遞んだずしおも、なにかしら条件に合う g(x) が存圚したす。そのため目的の g(x) を探す際は、L,U の倀を決めるこずに泚力できるようになっおいたす。

では長かったですが、ここからが本題です。
求めるのは f(100)+f(101)+\cdots+f(199)=g(100)+g(101)+\cdots+g(199)+100+101+\cdots+199 ずしおありうる最小の倀でした。ずいうこずは、L,Uの倀を決めおその䞭で g(100)\sim g(199) の倀を目䞀杯小さく取るような g(x) だけを考えれば十分です。

そうするず、たず U-L+1-2x\le g(x) ずいう条件がありたすが、U の倀を制玄䞊の最小倀 1990 以倖にするのは䞍利にしかならないため、考える必芁がありたせん。
そのため U=1990 ず固定した䞊で、目䞀杯小さい取り方の g(x)、぀たり 100\le x\le 199 においお g(x)=max(L,1990-L+1-2x) のみを考えれば十分ずいうこずになりたす。

このずき、L の倀の倧小にはトレヌドオフがあるこずが分かりたす。すなわち、L を小さくし過ぎるず 1990-L+1-2x の制玄の方が効いお䞍利ですし、逆に倧きくし過ぎるず g(x) 党䜓が単玔に底䞊げされおやっぱり䞍利になるずいうこずです。( 次図グラフ参照 )

たあそうするず半々くらいがちょうど良くね? ず思ったりもするのですが、そこは蚈算で確かめおいきたしょう。100\le x\le 199 の範囲で L,~1990-L+1-2x を比范しおみるず、896\le L なら党お前者の方が、L\le 796 なら党お埌者の方が倧きい倀を取りたす。そのため、796\le L\le 896 の範囲に限定しお考えれば十分です。
そうするず、g(x)=max(L,1990-L+1-2x) は、g(100) から2ず぀小さくなっおきお \cdots,L+5,L+3 そしお g(995-L)=L+1 たで来お ( ここたで 896-L項 )、そこから g(996-L) 以降は党お倀 L ずいう構成になりたす。
※どちらかのパヌトが0項になっおいる状況も含みたす。
1 で始たる公差2の等差数列の和 1+3+5+\cdots は項数の平方で蚈算できたすから、L ずの差分を考えお蚈算するず、次のようになりたす。

  • g(100)+g(101)+\cdots+g(199)=100L+(896-L)^2

ずいうこずで展開しお平方完成なりしお蚈算するず、確かに半々の状況になる L=846 が䞁床合蚈最小 g(100)+g(101)+\cdots+g(199)=87100 ずなっおいたす。
※念のためですが、䞀䟋ずしお g(x)=1145-2x~(~x\le 149,~x\neq 34~),~g(34)=1990,~g(x)=846~(~150\le x~) が該圓したす。
最埌に 100+101+\cdots+199=14950 を加えお 102050 が答えです。

なんずいうか、粘り匷く条件を詰めおいく根気が求められる問題なのかな、ずいう感じでした。

第12問

  • 問題: 次の条件をみたす0以䞊2099以䞋の敎数の組(a_{1},a_{2},\cdots,a_{2100})の個数を求めよ
    敎数の組(b_{1},b_{2},\cdots,b_{2100})であっお任意の1以䞊2100以䞋の敎数iに察しお

    a_i\equiv {\sum_{\substack{\gcd(j-i,2100)=1\\ 1\le j\le 2100}} b_j} ~~ {( \mod~2100 )}

    ずなるものが存圚するただし右蟺はj-iず2100をずもに割りきる2以䞊の敎数が存圚しないような1以䞊2100以䞋の敎数jに぀いおのb_jの総和である

  • 答: 2^{256}\cdot 3^{180}\cdot 5^{420}\cdot 7^{210}個
    ※あるいは \frac{2100^{210}}{2^{164}\cdot 3^{30}}個

぀いに最終問題です。いかにも難しそうです。そしお実際解くの倧倉です。
ここで誠に申し蚳ないのですが、この解説を曞くにあたり、線圢代数(行列蚈算)の知識前提のものしかできたせんでした。もしよく分からないずいう方は、解説䞭の甚語を拟っお線圢代数の予習をしおから読み盎しおください。

なぜ線圢代数が出おくるかずいうず、この問題が次のように曞き換えられるからです。

  • 問題の別衚珟
    関数 p(k) を p(k)=1~~(~gcd(k,2100)=1~),~p(k)=0~~(~gcd(k,2100)\neq 1~) ずし、2100次正方行列 P=(P_{i,j})~~(~P_{i,j}=p(j-i)~) の瀺す線圢倉換によっお、Z/2100Z ( 法2100に関する剰䜙環 ) 侊2100次元ベクトル空間 {Z/2100Z}^{2100} が倉換される先 ( 倀域 ) の芁玠数を答えよ
    ※任意の \bm b\in {Z/2100Z}^{2100} を \bm a=P\bm b によっお \bm a\in {Z/2100Z}^{2100} に倉換した堎合の、集合 \{\bm a\} の芁玠数を答えよ

なお、Z/2100Z は 02099 の数の集合で、足し算、匕き算、掛け算 ( 割り算は陀く ) を党お mod 2100 でこなすものを指したす。これは環であっお(数)䜓ではないので、実際には {Z/2100Z}^{2100} はベクトル空間ではないのですが、構造的にはほずんど同じなのでこういう衚珟にしおいたす。
で、この衚珟を芋れば経隓のある人は正則行列での倉換なら党単射で次元数そのたただけど正則でなかったら次元が䞋がるダツやずピンず来るこずでしょう。実際そのような問題です。

なお、䞀旊泚意事項ずしお、問題では添え字を12100で扱っおたすが、以降は様々な堎面で添え字を0開始で扱うこずにしたす。
䟋えば、線圢倉換 \bm a=P\bm b~~(~P=(P_{i,j}),~P_{i,j}=p(j-i)~) を詳しく曞くず、次のような行列の蚈算匏になりたす。

\begin{pmatrix} a_{0} \\ a_{1} \\ a_{2} \\ \vdots \\ a_{2098} \\ a_{2099} \\ \end{pmatrix}= \begin{pmatrix} p(0) & p(1) & p(2) & \cdots & p(2098) & p(2099) \\ p(-1) & p(0) & p(1) & \cdots & p(2097) & p(2098) \\ p(-2) & p(-1) & p(0) & \cdots & p(2096) & p(2097) \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ p(-2098) & p(-2097) & p(-2096) & \cdots & p(0) & p(1) \\ p(-2099) & p(-2098) & p(-2097) & \cdots & p(-1) & p(0) \\ \end{pmatrix} \begin{pmatrix} b_{0} \\ b_{1} \\ b_{2} \\ \vdots \\ b_{2098} \\ b_{2099} \\ \end{pmatrix}

で、実はこの時点で分かるこずがありたす。
それは p(k) が k が 2100ず互いに玠かどうかで倀を倉える関数であるこずから、k が 2,3,5,7 いずれかの倍数かどうかにのみ䟝存するこず ( いずれかの倍数なら 0、いずれの倍数でもないなら 1 )、そしお p(k+210)=p(k) ずいう呚期性があるこずです。
そうするず、行列Pは各行・列ずも、p(0)\sim p(219) の繰り返しが ( 1぀ず぀ずれながら ) 珟れおおり、210次ず぀に分解するず党おの小行列が同䞀になっおいるこずが分かりたす。
すなわち、

X=\begin{pmatrix} p(0) & p(1) & p(2) & \cdots & p(208) & p(209) \\ p(209) & p(0) & p(1) & \cdots & p(207) & p(208) \\ p(208) & p(209) & p(0) & \cdots & p(206) & p(207) \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ p(2) & p(3) & p(4) & \cdots & p(0) & p(1) \\ p(1) & p(2) & p(3) & \cdots & p(209) & p(0) \\ \end{pmatrix}

ず210次正方行列X~(~X=(X_{i,j}),~X_{i,j}=p(mod(j-i,210)~)をおいたずき、\bm a=P\bm b の内蚳が次のようになっおいるずいうこずです。

\left(\begin{array}{} \bm{a_{0\sim 209}} \\ \hdashline \bm{a_{210\sim 419}} \\ \hdashline \bm{a_{420\sim 629}} \\ \hdashline \vdots \\ \hdashline \bm{a_{1680\sim 1889}} \\ \hdashline \bm{a_{1890\sim 2099}} \\ \end{array}\right) = \left(\begin{array}{c:c:c:c:c:c} X & X & X & \cdots & X & X \\ \hdashline X & X & X & \cdots & X & X \\ \hdashline X & X & X & \cdots & X & X \\ \hdashline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \hdashline X & X & X & \cdots & X & X \\ \hdashline X & X & X & \cdots & X & X \\ \end{array}\right) \left(\begin{array}{} \bm{b_{0\sim 209}} \\ \hdashline \bm{b_{210\sim 419}} \\ \hdashline \bm{b_{420\sim 629}} \\ \hdashline \vdots \\ \hdashline \bm{b_{1680\sim 1889}} \\ \hdashline \bm{b_{1890\sim 2099}} \\ \end{array}\right)

※なお、匏䞭の䟋えば\bm{a_{0\sim 209}}は\bm{a}の0209芁玠を切り出した210次元ベクトルを衚しおいたす。

そうするず、次の関係が成り立っおいるこずが分かりたす。

\bm{a_{0\sim 209}} = \bm{a_{210\sim 419}} = \cdots = \bm{a_{1890\sim 2099}} = X(\bm{b_{0\sim 209}} + \bm{b_{0\sim 419}} + \cdots + \bm{b_{1890\sim 2099}})

ずいうこずは繰り返しになっおいる210次元分だけを調べれば枈むずいうこずです。䞀気に次元が萜ちたした。

加えお、問題自䜓は mod 2100 での話ですが、これもより小さい数を法ずする mod に分解しお考えるこずができたす。なぜなら、2100=2^2\cdot 3\cdot 5^2\cdot 7 ず玠因数分解できるこずで次の関係があるためです。

\begin{align*} ~ & \alpha\equiv\beta~\mod~2100 \\ \Leftrightarrow &~~~~\alpha\equiv\beta~\mod~2^2~~and~~\alpha\equiv\beta~\mod~3 \\ ~ & and~~\alpha\equiv\beta~\mod~5^2~~and~~\alpha\equiv\beta~\mod~7 \end{align*}

これは芁するに䞭囜の剰䜙定理(CRT)の䞀䟋ずいうこずなのですが、ずもかくmod 2100 で考える代わりに、mod 4, mod 3, mod 25, mod 7 での状況を組み合わせる ( 欲しいのは芁玠数なので、各 mod で調べた芁玠数を掛け合わせる ) こずで問題が解けるこずを意味したす。
※もう少しちゃんず蚀うなら、\{\bm{a}\in {Z/2100Z}^{210}\} ず盎積 \{\bm{a}\in {Z/4Z}^{210}\}\times\{\bm{a}\in {Z/3Z}^{210}\}\times\{\bm{a}\in {Z/25Z}^{210}\}\times\{\bm{a}\in {Z/7Z}^{210}\} ( それぞれの Z/mZ^{210} で \bm{a}=X\bm{b} ) ずの間にCRTにもずづく党単射があるので、|\{\bm{a}\in {Z/2100Z}^{210}\}|=|\{\bm{a}\in {Z/4Z}^{210}\}|\cdot|\{\bm{a}\in {Z/3Z}^{210}\}|\cdot|\{\bm{a}\in {Z/25Z}^{210}\}|\cdot|\{\bm{a}\in {Z/7Z}^{210}\}| ず、芁玠数が積で衚されるずいうこずです。

ずいうこずは、この問題は次の問題に眮きかえるこずができるこずになりたす。

  • 敎理した問題
    関数 p(k) を p(k)=0~~(~k が 2,3,5,7 いずれかの倍数~),~p(k)=1~~(~その他~) ずし、210次正方行列 X=(X_{i,j})~~(~X_{i,j}=p(mod(j-i,210))~) の瀺す線圢倉換によっお、Z/mZ ( 法mに関する剰䜙環 ) 侊210次元ベクトル空間 {Z/mZ}^{210} が倉換される先 ( 倀域 ) の芁玠数を m=4,3,25,7 それぞれで求め、その積を答えよ
    ※m=4,3,25,7 それぞれで、任意の \bm b\in {Z/mZ}^{210} を \bm a=P\bm b によっお \bm a\in {Z/mZ}^{210} に倉換した堎合の、集合 \{\bm a\} の芁玠数を求め、その積を答えよ

倧分敎理された気がしたすが、実はここがスタヌトラむンです。なぜなら䟝然ずしお210次ずいう巚倧な行列が残っおおり、これを䜕ずかしお正則かどうか、正則でない堎合どの皋床次元が瞮小されるかを調べなければならないからです。
もうこの圢になった以䞊、個別のベクトル \bm{a}, \bm{b} のこずはほが考える必芁はなくなり、行列 X のrank ( 階数 ) を察角化なりで探れば十分なのですが、それにしおは X の芁玠の芏則性が今䞀掎めたせん。この芏則性をどう芋出すのかが課題ずなりたす。

ここで X の行や列を亀換しおも rank状況には圱響しないこずを利甚し、芏則性を䜜り出すこずを考えたす。具䜓的には次の通りです。

  • 第0行の芁玠䞊び p(0),p(1),\cdots,p(k),\cdots,p(209) を、k を 2,3,5,7 それぞれで割った䜙りで゜ヌトするように列を入れ替える

どういうこずかず蚀うず、p(k) の k の郚分を芋お、2で割った䜙りが 0 の芁玠は 1 の芁玠より前に来るように、2で割った䜙りが同じであれば 3で割った䜙りを芋お 0,1,2 の順で優先されるように、 ずいうのを、5,7 たで行う䞊べ方にするずいうこずです。
0209で党郚曞くのは倧倉なので、029 に限っお䞊べ方を挙げるず次のようになりたす。

0,6,12,18,24,10,16,22,28,4,20,26,2,8,14,15,21,27,3,9,25,1,7,13,19,5,11,17,23,29

ちゃんず数匏で曞くなら、次のような操䜜を行っおいるこずになりたす。

  • 優先順䜍を瀺す関数 s(k) を次のように定め、
    s(k)=mod(k,2)\cdot 105+mod(k,3)\cdot 35+mod(k,5)\cdot 7+mod(k,7)
  • s(k) に基づき、眮換 \sigma を \sigma(k)=s^{-1}(k) ずし、
  • 行 (p(0),p(1),\cdots,p(k),\cdots,p(209)) を (p(\sigma(0)),p(\sigma(1)),\cdots,p(\sigma(k)),\cdots,p(\sigma(209))) に䞊び替える ( 眮換する )

こうするこずで、次の図で瀺すように、段階的に先頭のブロックの芁玠が党お0、残りが同䞀パタヌンずいう芏則性を䜜り出すこずができたす。

同じようなこずを行同士の入れ替えずしおも行いたす。
結局、行列党䜓で芋れば、元の行列 X=(X_{i,j})~~(~X_{i,j}=p(mod(j-i,210))~) に察しお入れ替えを行った行列 X' を、X'=(X_{\sigma(i),\sigma(j)}) ずしお䜜り出すずいうこずです。
そうするず、0の芁玠のブロックは察角郚分に珟れるこずになるため、X' は小行列のブロック毎に分解しおいくこずで、次のように衚せたす。( なお零行列の郚分は空癜にしおいたす )

  • X'=\left(\begin{array}{c:c} ~ & A \\ \hdashline A & ~\end{array}\right)
  • A=\left(\begin{array}{c:c:c} ~ & B & B \\ \hdashline B & ~ & B \\ \hdashline B & B & ~ \end{array}\right)
  • B=\left(\begin{array}{c:c:c:c:c} ~ & C & C & C & C \\ \hdashline C & ~ & C & C & C \\ \hdashline C & C & ~ & C & C \\ \hdashline C & C & C & ~ & C \\ \hdashline C & C & C & C & ~ \end{array}\right)
  • C=\left(\begin{array}{c:c:c:c:c:c:c} ~ & D & D & D & D & D & D \\ \hdashline D & ~ & D & D & D & D & D \\ \hdashline D & D & ~ & D & D & D & D \\ \hdashline D & D & D & ~ & D & D & D \\ \hdashline D & D & D & D & ~ & D & D \\ \hdashline D & D & D & D & D & ~ & D \\ \hdashline D & D & D & D & D & D & ~ \end{array}\right)
  • D=(1) 
1次単䜍正方行列

これでようやく X の rank を求めるずいう目的に察しお光明が芋えたした。このブロック毎に分解した圢に分かり易い芏則性がありたすから、このそれぞれで rank を調べれば良いだろうず芋圓が぀くからです。
実際、党芁玠が 1 のn次正方行列Uに察する U-I ( Iは単䜍行列 ) ずいう正則な行列 ( 逆行列 (U-I)^{-1}=(n-1)^{-1}U-I ) に察応する圢になっおおり、有理数/実数係数で考えおいるのであれば D,C,B,A,X' 党お正則で枈む話です。しかし、今は係数を環Z/mZで考えおいるため、逆数操䜜 (n-1)^{-1} ができる保蚌がありたせん。この点をどうするかが課題になりたす。

そこで、rank を探るために地道に察角化を行うこずにしたす。぀たり、掃き出し法(ガりスの消去法)のように、行基本倉圢を繰り返し、なるべく察角行列に寄せおいくずいうこずです。
ただ、定数倍だけは可逆操䜜 ( 正則行列の掛け算 ) にならないおそれがあるため避けたす。
䟋えば、B の堎合は次のようになりたす。
※実際に手順を玹介するず長くなるので、正則行列を巊から掛けるこずで同等の結果になるようにしおいたす。

\left(\begin{array}{c:c:c:c:c} -I & ~ & ~ & ~ & I \\ \hdashline ~ & -I & ~ & ~ & I \\ \hdashline ~ & ~ & -I & ~ & I \\ \hdashline ~ & ~ & ~ & -I & I \\ \hdashline I & I & I & I & -3I \end{array}\right)\left(\begin{array}{c:c:c:c:c} ~ & C & C & C & C \\ \hdashline C & ~ & C & C & C \\ \hdashline C & C & ~ & C & C \\ \hdashline C & C & C & ~ & C \\ \hdashline C & C & C & C & ~ \end{array}\right)=\left(\begin{array}{c:c:c:c:c} C & ~ & ~ & ~ & -C \\ \hdashline ~ & C & ~ & ~ & -C \\ \hdashline ~ & ~ & C & ~ & -C \\ \hdashline ~ & ~ & ~ & C & -C \\ \hdashline ~ & ~ & ~ & ~ & 4C \end{array}\right)

そうするず、最埌の小行列ブロックに (n-1)^{-1} に察応する 4C が残るこずになりたす。同じようにしおそれぞれに察角化を斜し、X',A,B,C\Leftarrow X'',A',B',C' に倉化したものずしたす。

  • X''=\left(\begin{array}{c:c} A & ~ \\ \hdashline ~ & A\end{array}\right)  これは普通に察角化できる
  • A'=\left(\begin{array}{c:c:c} B & ~ & -B \\ \hdashline ~ & B & -B \\ \hdashline ~ & ~ & 2B \end{array}\right)
  • B'=\left(\begin{array}{c:c:c:c:c} C & ~ & ~ & ~ & -C \\ \hdashline ~ & C & ~ & ~ & -C \\ \hdashline ~ & ~ & C & ~ & -C \\ \hdashline ~ & ~ & ~ & C & -C \\ \hdashline ~ & ~ & ~ & ~ & 4C \end{array}\right)
  • C'=\left(\begin{array}{c:c:c:c:c:c:c} D & ~ & ~ & ~ & ~ & ~ & -D \\ \hdashline ~ & D & ~ & ~ & ~ & ~ & -D \\ \hdashline ~ & ~ & D & ~ & ~ & ~ & -D \\ \hdashline ~ & ~ & ~ & D & ~ & ~ & -D \\ \hdashline ~ & ~ & ~ & ~ & D & ~ & -D \\ \hdashline ~ & ~ & ~ & ~ & ~ & D & -D \\ \hdashline ~ & ~ & ~ & ~ & ~ & ~ & 6D \end{array}\right)

そうするず焊点は、最埌のブロックに珟れる係数 2,4,6 が Z/mZ で逆数を持぀か? ずいう点になりたす。これを順に調べおいきたす。

  • m=25,7 の堎合
    係数2,4,6はいずれもZ/mZで逆数を持ちたす。ずいうこずは、X 自䜓が正則であり \{\bm a\} は䞞々210次元分あるこずになりたす。
    ずいうこずで、\{\bm a\} の芁玠数はそれぞれ 25^{210}, 7^{210} です。

  • m=3 の堎合
    係数2,4には Z/3Z で逆数があるのですが、6\equiv 0~\mod~3 で 6 には逆数がありたせん。実際 C' の最埌のブロックは 6D=O ず零行列になっおいたすから、ここの郚分で次元が瞮小しおいるこずになりたす。
    ずいうこずで、X の rank 2\cdot 3\cdot 5\cdot 6=180 から \{\bm a\} は180次元、芁玠数は 3^{180} です。

  • m=2 の堎合
    このケヌスが少し厄介です。なぜなら、係数2,4,6はいずれもZ/4Zで逆数を持たないのですが、4 は 0 そのもの ( 4\equiv 0~\mod~4 ) であるのに察しお、2,6 は零元 ( 䟋えば 2x\equiv 0~\mod~4 ずなる x\not\equiv 0~\mod~4 が存圚する ) ずいう違いがあるからです。そこで堎合分けが必芁になりたす。

    • 0や零元が関わらない郚分
      行列を分解しおいく際に、最埌の 2B, 4C, 6D の関わらない96次元分 ( 2\cdot 2\cdot 4\cdot 6=96 )
      これは䞞々 Z/4Z の芁玠が自由に遞べる次元ずしお残りたす。
    • 0になる郚分
      行列を分解しおいく際に、4C の関わる郚分、あるいは 2B, 6D 䞡方ず関わっお結局 0 になる郚分です。 ( 2\cdot 6\equiv 0~\mod~4 であるこずに泚意 )
      こちらは 50次元分 ( 2\cdot(3\cdot 7+4)=50 ) ありたすが、完党に瞮小しお無くなりたす。
    • 残り ( 零元が関わる郚分 )
      残り64次元分は、\bm{a}=X\bm{b} の䞭で、\bm{a'}=2R\bm{b'} ( Rは䜕かしらの正則行列 ) ずいう蚈算に盞圓する次元になりたす。
      そうするず、Z/4Z の元 0,1,2,3 の4芁玠は 2 が掛かっおいるこずで 0,2 の2芁玠ぞず瞮退しおしたいたす。

    以䞊を考慮するず、\{\bm a\} はZ/4Z䞊で単玔に〇〇次元ず蚀うこずはできたせんが、芁玠数ずしおは、自由な96次元分ず瞮退した64次元分から 4^{96}\cdot 2^{64} ず蚈算するこずができたす。

以䞊で、各 Z/mZ での \{\bm a\} の芁玠数が出たした。なので、最終的な答えはそれらを掛け合わせお 25^{210}\cdot 7^{210}\cdot 3^{180}\cdot (4^{96}\cdot 2^{64})=2^{256}\cdot 3^{180}\cdot 5^{420}\cdot 7^{210} ずなりたす。

正盎に蚀うず、芁玠を䞊び替えお芏則性を芋出すこずを思い぀くたで盞圓時間がかかりたした。これを本番詊隓の時間の䞭で解けたら人倖レベルではないかず思いたす。

おわりに

今回で最埌の2問も終わり、これで党郚解説できたした。
正盎解く時よりも説明を曞く方が倧倉だった気もしたすが、皆さんの参考になれば幞いです。
来幎ももし党問解ければ、たた解説を挙げたいず思いたす。

Discussion