4

JMO予選12番を単因子論で解く

701
0

表題の通りです. https://mathlog.info/articles/J9UQTOoRHts6LWMW8jZc と本質的に同じな気もします.

問題

問題は https://www.imojp.org/archive/mo2024/problems/jmo34yqa.pdf  から引用した.

JMO2024年 予選12番

次の条件をみたす0以上2099以下の整数の組(a1,a2,,a2100)の個数を求めよ.

整数の組(b1,b2,,b2100)であって, 任意の1以上2100以下の整数iに対して
aigcd(ji,2100)=11j2100bj(mod2100)
となるものが存在する.
ここで, 右辺はji2100をともに割りきる2以上の整数が存在しないような1以上2100以下の整数jについてのbjの総和である.

解答

初等的考察

すこし, 初等的な考察をする. gcd(k,2100)=1gcd(k,210)=1なので, ai=ai+210が成立する. ここで, ci=bi+bi+210++bi+1890と置くと,
aigcd(ji,210)=11j210cj(mod2100)
が成立する. 逆に, このようなaiが条件を満たすのはほぼ自明. (ci0拡張してbiにすればよい.) よって, a,bの長さは210として解いてよい.

言い換え

まず, 問題を環上の加群の話に置き換える.
R=Z/2100Z, と置く.
自然数nに対し, Rnの標準基底をei(0i<n)と置き, この添え字はmodnで考える.
R線形写像fn:RnRnを,
eigcd(j,n)=10j<nej+i
となるように定める.
このとき問題は#Im(f210)を求めることに帰着される.

テンソル積への分解

次に, f210をテンソル積に分解することを考える.
R線形写像ι:R210R2R3R5R7を,
eieieieiei
と定める. 中国剰余定理よりιは, 全単射. さらに, (f2f3f5f7)ι=ιf210が成立する. 実際, 両辺のR線形より,eiを代入して等しければよい. これは次のように確かめられる:
(f2f3f5f7)ι(ei)=f2(ei)f3(ei)f5(ei)f7(ei)=gcd(p,2)=1,gcd(q,3)=1,gcd(r,5)=1,gcd(s,7)=1ei+pei+qei+rei+s=gcd(j,210)=1ei+jei+jei+jei+j=gcd(j,210)=1ι(ei+j)=f210(ei)
ここで, j0から209, p0から1, q0から2,r0から4, s0から6を渡る. 3番目の等式では, 中国剰余定理と, gcd(k,210)=1gcd(k,p)=1(p{2,3,5,7})を用いた.
ιが全単射だったことを思い出すと, Im(f210)=Im(f2f3f5f7)である.

fpの単因子

次にfp(pは素数)の単因子を求める. Rpの元の列t0tp1, およびu0,u1,up1を次のように定める.
ti={i=0p1eii=0eii>0
ui={i=0p1eii=0f(ei)i>0
(ti)iRnの生成元であることはあきらか. (ui)iも, u0ui=eiに注意すると, Rnを生成することがわかる. Rnが有限集合であることから, 結局(ti)i,(ui)iRnの基底である.
よって, f(e0)=(p1)u0に注意すると, fpの単因子は(p1,1,1)である.

答え

最後にここまでをまとめ, 答えを出す.
一般にfの単因子が(ai)i, gの単因子が(bj)jのとき, fgの単因子は(aibj)i,jである.
よって, f2f3f5f7の単因子は(2δq,0+2δr,0+δs,03δs,0)p,q,r,sとなる. (p,q,r,sの渡る範囲は前のと同じ. ) R=Z/2100Zでは, 4,8,16は同伴である. よって, 単因子としてありうるのは, 1,2,4,3,6,12のどれか.

21回割れる単因子の数

(q,r,s)の中に01個以上あることと同値.
2×3×5×72×2×4×6=114個.

22回割れる単因子の数

r=0またはq=s=0と同値.
r=0となるのが, 2×3×1×7=42個.
q=s=0となるのが, 2×1×5×1=10個.
かぶりが2個あるので, 42+102=52個.

31回割れる単因子の数

s=0と同値. 2×3×5×1=30

よって, 21002102114252330=2256318054207210が答え.

感想

過去に予選で, 本質的にV4の話をする問題が出たことはあったりするんですが, ここまで大学数学が刺さる予選問題もでるんですね.
2100という数, 作者の勘で答えを当てさせない気概を感じます. 平方因子をもちつつ, ϕ(2100)2100なので. あと2256が出てくるのがややウケますね.

投稿日:2024110
更新日:2024827
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

bd
66
14379

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 問題
  2. 解答
  3. 初等的考察
  4. 言い換え
  5. テンソル積への分解
  6. fpの単因子
  7. 答え
  8. 感想