はじめに
背景
さる2025年11月16日(日)に実施された、第36回日本数学オリンピック予選につき、公開された問題を解いてみましたので、解説を挙げています。
今回は最後ということで、その2までで解説した残りの問題について挙げていきます。
別パートへのリンク
問題について
各問題の帰属は、以下の通りです。
解法・解説については筆者のオリジナルです。
解説
それでは、今回の「その3」では、最後の2問を解説していきます。
第11問
-
問題: 1以上20以下の整数の組(a_1,a_2,\cdots,a_{26})であって，次の条件をみたすものはいくつあるか．
1\le i\lt j\le 26をみたす整数の組(i,j)であって，
a_1+a_2+\cdots+a_i=a_j+a_{j+1}+\cdots+a_{26}
をみたすものがちょうど1つ存在する．
-
答: 9980\cdot 19^{23}個
さてこれも実は2026年絡みの問題です。とはいえ20,26という数字に特殊な性質はありません。
条件を満たす組を数え上げるにあたって、どのように場合分けしてアプローチするか、が焦点となるところです。ここで「iを変化させて、そのそれぞれでjの取りうる値が…」と考えると、多分ハマります。
ここはずばりj-iの値に応じて場合分けするのがいい手です。
問題の条件は大まかには、整数26個の組の先頭と末尾に合計が等しいかたまりがある、ということを言っています。このかたまりを、例えば先頭5個末尾1個でも、先頭3個末尾3個でも「先頭・末尾のかたまり併せて6個」というグルーピングでまとめてしまおう、というのがj-iの値に応じた場合分けです。
ここで、状況の整理のために性質 D_n, N\!d_n を導入します。
1以上20以下の整数n個の組に関して、前者は「前後で同じ合計のかたまりに二分できる」後者は「二分できない」という性質とします。
※「組」と言っていますが、順番が影響しますので「有限要素の数列」と言った方が適切かも知れません。
ただし、両者共通の前提として「中間の連続する任意のk個(1\le k\le n-2)を削除したn-k個に対してN\!d_{n-k}であること」という条件を付けておきます。
※この前提は、「(i,j)の組がちょうど1つ存在する」という問題の条件に対応したものです。
例えば、\{1,2,3\} という3個組の場合、\{1,2\},\{3\} と合計3の2組に分割できますから、これは D_3 ですし、\{1,2,4\} の場合は逆に N\!d_3 です。
しかしながら \{1,2,1\} は D_3 ではありませんが、途中の 2 を削除すると \{1,1\} で D_2 となってしまいますから「共通の前提」に反します。つまり、N\!d_3 でもない、となります。
※D_nでもN\!d_nでもないものには特に名前は付けていません。
ここまでの話で、問題の条件を満たす26個組は、
-
D_{26} であること ( j-i=1 に相当 )
-
D_{k} なk個組 ( 2\le k\le 25 ) を同じ合計になるように前後で二分して、間に N\!d_{26-k} な(26-k)個組を挟んだもの ( j-i=26-k+1 に相当 )
のいずれかで表すことができます。
例えば前者の例は \{1,\underbrace{2,\cdots,2}_{\text{12個}},1,\underbrace{2,\cdots,2}_{\text{12個}},\}、
後者の例は \{1,2,1,\underbrace{4,\cdots,4}_{\text{22個}},3\} ( D_3 な3個組 \{1,2,3\} を \{1,2\},\{3\} と分割 )
が挙げられます。
これで問題の目標が D_n, N\!d_n それぞれの性質を持つ組の個数へと移りました。そこでその個数を a_n, b_n と置きます。
ちゃんと書くと、
-
a_n: 1以上20以下の整数n個 ( n\ge 2 ) の組であって、D_n であるものの個数
-
b_n: 1以上20以下の整数n個 ( n\ge 1 ) の組であって、N\!d_n であるものの個数
- 求める答えは a_{26}+\sum_{k=2}^{25} a_{k}b_{26-k}
ということです。
※答えの計算では「D_k なk個組を同じ合計になるように前後で二分」が、1通りに決まることを暗黙のうちに使っています。
ただ、依然として「前半が何個で後半が何個なんだろう…」と悩んでいては状況は改善していません。
そこで二の矢として、「与えられたn個の数を、先頭・末尾のかたまりの合計がバランスするように並び替えてn個組を構成する」と考えます。
例えば、\{1,5,\underbrace{\cdots}_{\text{未定}},4\} と並びが決まっているところに次に 3 が来たら、末尾の合計の方が小さいのでそちらに充当して \{1,5,\underbrace{\cdots}_{\text{未定}},3,4\} とする、そうすると今度は先頭の方が小さいので次は…といった感じです。
なお、既にバランスが取れている、つまり先頭と末尾の合計が等しい場合は、先頭に優先して充当するようにします。なので、最初の数は必ず先頭に来ます。
例として、1,2,3,4,5 という順で5個の数が来たら \{1,3,5,4,2\} という構成となりこれは N\!d_5 です。
逆に 5,4,3,2,1 という順なら \{5,2,1,3,4\} ですが、これだと 2 が来た時点で一旦合計が同じ7になってしまうので、D_5 でも N\!d_5 でもありません。
※中間の1を削除した4個組が D_4 であり、上で設定した「共通の前提」を満たさないため
5,4,3,1,1 という順であれば \{5,1,1,3,4\} という構成になって、これは D_5 です。
この構成法を考えることで嬉しい点は2つあり、1つは「n個組を一対一対応を保ったまま別の並び順に置き換えられること」そしてもう1つは「N\!d_nな構成からD_{n+1},N\!d_{n+1}な構成への拡張が容易なこと」です。
※D_nな構成の次はD_{n+1},N\!d_{n+1}どちらにも拡張できないので、そのまま捨ててしまって構いません。
例えば 1,2,3,4 という順の4個の数から \{1,3|4,2\} という N\!d_4 な構成を行ったとして ( 合計をバランスさせるための区切りを | としています )、これは末尾の合計の方が 2 大きい状態なので、次に 2 を持ってきて \{1,3,2|4,2\} とすれば D_5 ですし、2以外の \{1,3,x|4,2\}~(x\ne 2) であれば N\!d_5 です。
そして、合計をバランスさせているという前提から、合計の差は必ず 1～20 の範囲で収まっていますから、N\!d_n な構成からは、必ず 1通りの D_{n+1} な構成と 19通りの N\!d_{n+1} な構成が産まれます。
すなわち、これで a_{n+1}=b_n,~b_{n+1}=19b_n~~(n\ge 1) が分かります。
※N\!dでない構成の先にD,N\!dな構成はできませんから、これで十分です。
あとは、1個だけの構成が必ず N\!d_1 になることから b_1=20 という条件を併せれば、これで a_n=20\cdot 19^{n-2}~(n\ge 2),~b_n=20\cdot 19^{n-1}~(n\ge 1) が確定します。驚くほど単純な形になりました。
最終的に答えは、
\begin{align*}
~&a_{26}+\sum_{k=2}^{25} a_{k}b_{26-k} \\
=&20\cdot 19^{24}+\sum_{k=2}^{25} 20\cdot 19^{k-2}\cdot 20\cdot 19^{25-k} \\
=&20\cdot 19^{24}+20\cdot 20\cdot 19^{23}(25-2+1) \\
=&9980\cdot 19^{23}
\end{align*}
となります。
数え上げのための分類・構成法をうまく思いつけるかどうかで、くっきりと明暗が分かれる問題かと思います。
第12問
- 問題: 正の整数x,y,zはx^x\cdot y^y=z^{20x+26y}をみたしている．\frac{x}{z^{25}}が整数であり，\frac{y}{z^{25}}が整数でないとき，zとしてありうる最小の値をもとめよ．
- 答: 2^{127}\cdot 641^{641}
いよいよ最終問題です。何気にこちらも2026年絡みです。
式の形自体は単純ですが、どうしたものかはさっぱりわかりません。流石です。
式の条件だけなら、適当な a に対して (x,y,z)=(a^{20},a^{26},a) がtrivialな解としてありますが、これは他の条件を満たさないため使えません。
一筋縄でいく問題ではありませんから、途中何度も考えを再整理する必要がありました。そこで、本記事では大きく4段階に分けて解説します。なお、基本的に出てくる数は特にことわりがなければ全て整数です。
第一段階
取り敢えずは状況を整理するところから始めましょう。対象は整数なので、素因数分解して各素因数の指数の関係で見ることにします。明らかに z=1 は解にならないので、1つ以上の素数 \{p_k\} の組に対し、z の素因数の指数部分が r_{3,k}\ge 1 であるものとします。そうして、x,y にも同じように指数部分 r_{1,k},r_{2,k} を定めます。
すなわち、
- x=\prod_k p_k^{r_{1,k}},~y=\prod_k p_k^{r_{2,k}},~z=\prod_k p_k^{r_{3,k}}
- \forall k.~r_{1,k}\ge 0,~r_{2,k}\ge 0,~r_{3,k}\ge 1
そうすると、問題の条件は各素因数の指数部分の関係として、以下のように書き換えることができます。
※分数が整数になる/ならないは、指数部分の大小 ( 約分したとき、分子・分母どちらに素因数が残るか ) として見られることに注意してください。
- \forall k.~xr_{1,k}+yr_{2,k}=(20x+26y)r_{3,k}
-
\forall k.~r_{1,k}\ge 25r_{3,k} 特に r_{1,k}\ge 25
-
\exists k.~r_{2,k}\lt 25r_{3,k} 特に r_{2,k}\lt r_{1,k}
さて、最終的にほしいのは z そのための r_{3,k} ですが、とても現時点でなんとかなる気がしません。なので、最初は解を持つ場合の x,y の条件を分析していくことにします。
上の条件から r_{3,k} を消して、x,y,r_{1,k},r_{2,k} の条件に絞っていきます。
- \forall k.~xr_{1,k}+yr_{2,k}\equiv 0 ~\mod~20x+26y
-
r_{1,k}\ge 25r_{3,k}\Leftrightarrow (20x+26y)r_{1,k}\ge 25(20x+26y)r_{3,k}=25(xr_{1,k}+yr_{2,k})
\Leftrightarrow (26y-5x)r_{1,k}\ge 25yr_{2,k} のため、
\forall k.~(26y-5x)r_{1,k}\ge 25yr_{2,k}
-
r_{2,k}\lt 25r_{3,k}\Leftrightarrow (20x+26y)r_{2,k}\lt 25(20x+26y)r_{3,k}=25(xr_{1,k}+yr_{2,k})
\Leftrightarrow (20x+y)r_{2,k}\lt 25xr_{1,k} のため、
\exists k.~(20x+y)r_{2,k}\lt 25xr_{1,k}
まだ先行きは分かりませんが、とりあえず次のことは分かります。
そして怪しいのが y と 5x の大小関係です。これは、y=5x が2番目の条件の不等式での両辺の係数 26y-5x と 25y がちょうど揃うところになっていることから来ています。
で、実際調べてみると y\gt 5x という大小関係であることが分かります。y\le 5x と仮定して背理法で示します。
y\le 5x と仮定すると 26y-5x\ge 26y-y=25y
よって、\forall k に対し (26y-5x)r_{1,k}\ge 25yr_{2,k}\Rightarrow 25yr_{1,k}\ge 25yr_{2,k}\Leftrightarrow r_{1,k}\ge r_{2,k}
これは x,y の全ての素因数での指数の大小関係であるため、x\ge y が導かれる。
改めて \forall k に対して
~(26y-5x)r_{1,k}\ge 25yr_{2,k}\Rightarrow r_{2,k}\le \frac{21}{25}\cdot r_{1,k}\Rightarrow r_{1,k}-r_{2,k}\ge \frac{4}{25}r_{1,k}
更に \forall k.~r_{1,k}\ge 25 という条件もあったため、\forall k.~r_{1,k}-r_{2,k}\ge 4
指数に4以上の差がつくということは、最も比がマシな場合を考えても x\ge 2^4\cdot y
これは 26y-5x\ge 0 に反する。
こうして y\gt 5x ということが分かりましたので、\exists k.~r_{2,k}\gt r_{1,k}
一方で \exists k.~r_{2,k}\lt r_{1,k} という条件もありました。
つまり、x の方の指数が勝る素因数も、y の方の指数が勝る素因数も両方あるということです。
想像はしていましたが、なかなか単純にはいきません。なので、ここで少し方針転換を図ります。
これまでの話から、G=gcd(x,y), x=XG, y=YG~(~gcd(X,Y)=1~) とすると、X,Y\gt 1 であることが分かります。この X,Y は、x,y それぞれで指数が勝る素因数に対応しています。
なので逆に、X,Y が先に決まっている状態から G として取りうる値の条件、また X,Y 自体の関係を探ることにします。
第二段階
ということで、改めて x,y を別の形で表します。
X,Y の持つ素因数を \{p_{1,i}\},\{p_{2,j}\} ( 共に1つ以上の素数を含み、かつ両者に共通の素数はない )、それぞれに対する指数を d_{1,i},d_{2,j} とします。
すなわち、
- X=\prod_i p_{1,i}^{d_{1,i}},~Y=\prod_j p_{2,i}^{d_{2,i}}
- \forall i.~d_{1,i}\ge 1,~\forall j.~d_{2,j}\ge 1
-
\{p_{1,i}\}\cap \{p_{2,j}\}=\phi 別の言い方をすれば gcd(X,Y)=1
さてでは、G=gcd(x,y) に関して、これは X,Y どちらの素因数も持ちうるわけですが、実はそれ以外の素因数は無視することができます。
詳細は割愛しますが、G が上記 p_{1,i},p_{2,j} 以外の素因数を持つ場合、z が大きくなる派生の解が生成されるだけだからです。
ということで、G は指数を c_{1,i},c_{2,j} と置くことで、次のように表現することができます。
- G=\prod_i p_{1,i}^{c_{1,i}}\cdot \prod_j p_{2,j}^{c_{2,j}}
- \forall i.~c_{1,i}\ge 0,~\forall j.~c_{2,j}\ge 0
- x=XG,~y=YG
これで x,y に関する条件を置き換えます。
-
y\gt 5x より、以下が成立する。
-
\forall k.~xr_{1,k}+yr_{2,k}\equiv 0 ~\mod~20x+26y より、以下が共に成立する。
- \forall i.~XG(d_{1,i}+c_{1,i})+YGc_{1,i}\equiv 0~\mod 20XG+26YG
- \forall j.~XGc_{2,j}+YG(d_{2,j}+c_{2,j})\equiv 0~\mod 20XG+26YG
-
\forall k.~(26y-5x)r_{1,k}\ge 25yr_{2,k} より、以下が共に成立する。
- \forall i.~(26YG-5XG)(d_{1,i}+c_{1,i})\ge 25YGc_{1,i}
- \forall j.~(26YG-5XG)c_{2,j}\ge 25YG(d_{2,j}+c_{2,j})
-
\exists k.~(20x+y)r_{2,k}\lt 25xr_{1,k} より、以下のいずれかが成立する。
- \exists i.~(20XG+YG)c_{1,i}\lt 25XG(d_{1,i}+c_{1,i})
- \exists j.~(20XG+YG)(d_{2,j}+c_{2,j})\lt 25XGc_{2,j}
ここから意味のない情報を間引いたり、G を消去して整理します。
※ a\equiv b~\mod~c\Leftrightarrow aG\equiv bG~\mod~cG も利用しています。
- Y\gt 5X
-
\forall i.~X(d_{1,i}+c_{1,i})+Yc_{1,i}\equiv 0~\mod 20X+26Y すなわち
\forall i.~(X+Y)c_{1,i}\equiv -Xd_{1,i}~\mod 20X+26Y
-
\forall j.~Xc_{2,j}+Y(d_{2,j}+c_{2,j})\equiv 0~\mod 20X+26Y すなわち
\forall j.~(X+Y)c_{2,j}\equiv -Yd_{2,j}~\mod 20X+26Y
-
\forall j.~(26Y-5X)c_{2,j}\ge 25Y(d_{2,j}+c_{2,j}) すなわち
\forall j.~(Y-5X)c_{2,j}\ge 25Yd_{2,j}
-
\exists i.~(20X+Y)c_{1,i}\lt 25X(d_{1,i}+c_{1,i}) すなわち
\exists i.~(Y-5X)c_{1,i}\lt 25Xd_{1,i}
ここまで分かると、X,Y から合同式を解くことで、具体的に G を決定することができるようになります。
例えば、X=2^1, Y=11^1 から G=2^{50}\cdot 11^{275}、(x,y,z)=(2^{51}\cdot 11^{275},2^{50}\cdot 11^{276},2^2\cdot 11^{11}) は、上の5条件のうち最後を除く4条件を満たす解の例です。
これで大分迫って来たように思いますが、色々な X,Y の組を試してみると、思いのほか最後の条件を満たすものが見つかりません。また、解を決定したとしても最終的な「zの最小値」をどう判断するかという問題も残っています。この2点が課題です。
しかし、色々試してみると、最後の2条件の不等号がやたらと等号成立になることに気付きます。これは偶然ではありません。ここが最後の突破口になります。
等号成立のからくりは次のようなものです。
\begin{align*}
~& (X+Y)c_{1,i}\equiv -Xd_{1,i}~\mod 20X+26Y \\
\Rightarrow& -25(X+Y)c_{1,i}\equiv 25Xd_{1,i}~\mod 20X+26Y \\
\Leftrightarrow& ((20X+26Y)-25(X+Y))c_{1,i}\equiv 25Xd_{1,i}~\mod 20X+26Y \\
\Leftrightarrow& (Y-5X)c_{1,i}\equiv 25Xd_{1,i}~\mod 20X+26Y \\
\end{align*}
これと (Y-5X)c_{1,i}\lt 25Xd_{1,i} を見比べることで、
(X+Y)c_{1,i}\equiv -Xd_{1,i}~\mod 20X+26Y
\Rightarrow \exists m.~(Y-5X)c_{1,i}=25Xd_{1,i}+m(20X+26Y)
という m を導入して、不等式条件はこの m の大きさで見積もることができます。
第三段階
ということで、このmに相当するものとして、\{m_{1,i}\},\{m_{2,j}\} を導入します。
そしていよいよ z の指数として \{e_{1,i}\},\{e_{2,j}\} を導入して z の値を見積もっていきます。
改めて条件を整理します。
- X=\prod_i p_{1,i}^{d_{1,i}},~Y=\prod_j p_{2,j}^{d_{2,j}},~z=\prod_i p_{1,i}^{e_{1,i}}\cdot\prod_j p_{2,j}^{e_{2,j}}
- Y\gt 5X
-
\forall i.~(Y-5X)c_{1,i}=25Xd_{1,i}+(20X+26Y)m_{1,i}
加えて \exists i.~m_{1,i}\lt 0
また \forall i に対して c_{1,i}\ge 0 より 25Xd_{1,i}+(20X+26Y)m_{1,i}\ge 0
-
\forall j.~(Y-5X)c_{2,i}=25Yd_{2,j}+(20X+26Y)m_{2,i}
加えて \forall j.~m_{2,j}\ge 0
※自動的に \forall j.~c_{2,j}\ge 0 も成立する
- \forall i.~(20X+26Y)e_{1,i}=(X+Y)c_{1,i}+Xd_{1,i}
- \forall j.~(20X+26Y)e_{2,j}=(X+Y)c_{2,j}+Yd_{2,j}
ここから、まず e_{1,i},e_{2,j} を確定させます。\forall i に対して、
\begin{align*}
~&(20X+26Y)e_{1,i}=(X+Y)c_{1,i}+Xd_{1,i}~\text{かつ}~(Y-5X)c_{1,i}=25Xd_{1,i}+(20X+26Y)m_{1,i} \\
\Rightarrow&(20X+26Y)(Y-5X)e_{1,i}=(X+Y)(25Xd_{1,i}+(20X+26Y)m_{1,i})+(Y-5X)Xd_{1,i} \\
\Leftrightarrow&(20X+26Y)(Y-5X)e_{1,i}=(20X+26Y)(Xd_{1,i}+(X+Y)m_{1,i}) \\
\Leftrightarrow&(Y-5X)e_{1,i}=Xd_{1,i}+(X+Y)m_{1,i}
\end{align*}
e_{2,j}に対しても同じような計算ができます。まとめると、
- \forall i.~(Y-5X)e_{1,i}=Xd_{1,i}+(X+Y)m_{1,i}
- \forall j.~(Y-5X)e_{2,j}=Yd_{2,j}+(X+Y)m_{2,j}
ということで、Y-5X \gt 0 が各所に現れるため、u=Y-5X とします。なお、gcd(X,Y)=1 より gcd(X,u)=1 です。
分かり易さのため、u=1 のケースを見てみましょう。
\exists i.~m_{1,i}\lt 0 に対して最低限の設定として、m_{i,1}=-1 と仮定したとき、その i に対しても 25Xd_{1,i}+(20X+26Y)m_{1,i}\ge 0 であるため、
Y=5X+u=5X+1 で Y を消去して、
\begin{align*}
~&25Xd_{1,i}+(20X+26(5X+1))\cdot(-1)\ge 0 \\
\Leftrightarrow&25X(d_{1,i}-6)\ge 26 \\
\Rightarrow&d_{1,i}\gt 6
\end{align*}
このように、Xの素因数の指数の下限を見積もることができました。
各値をなるべく小さく抑えるようにすると、
- X=2^7~( p_{1,1}=2,d_{1,1}=7 )
- Y=5X+1=641~( p_{2,1}=641,d_{2,1}=1 )
- m_{1,1}=-1, m_{2,1}=0
- e_{1,1}=Xd_{1,1}+(X+Y)m_{1,1}=127, e_{2,1}=Yd_{2,1}+(X+Y)m_{2,1}=641
ということで、z=2^{127}\cdot 641^{641} という条件を満たす z が見つかります。
これが実は最小の z ということで答えになります。
第四段階
最後は、先ほど見つけた z の候補 2^{127}\cdot 641^{641} ( これを z_0 とします ) が最小であることを確認します。
先ほどは、u=1,m_{1,1}=-1 を決め打ちしていますから、他の候補での z の範囲を見積もることにします。その際、X 由来の素因数、\prod_i p_{1,i}^{e_{1,i}} 部分は見積もるのが難しいので、Y 由来の素因数のみで片づけます。
こちらは、\forall j.~m_{2,j}\ge 0 から見積もり易いためです。
\forall j.~(Y-5X)e_{2,j}=Yd_{2,j}+(X+Y)m_{2,j} から \forall j.~ue_{2,j}\ge Yd_{2,j}
よって、
z=\prod_i p_{1,i}^{e_{1,i}}\cdot \prod_j p_{2,j}^{e_{2,j}}\gt\prod_j p_{2,j}^{e_{2,j}}\ge\prod_j p_{2,j}^{Yd_{2,j}/u}=(\prod_j p_{2,j}^{d_{2,j}})^{Y/u}=Y^{Y/u}
ということで、Y の大きさによって z を見積もることができます。
まず u=1, m_{1,i}\lt -1 の場合、
25Xd_{1,i}+(20X+26Y)m_{1,i}\ge 0 から、今度は d_{1,i}\ge 13 が分かるため、
z_0 を導出した時と同じように、X\ge 2^{13}=8192 連動して Y=5X+u\ge 40961
そのため、z\gt Y^{Y/u}\ge 40961^{40961}\gt z_0
残るは u\ge 2 のケースです。特に、/u が指数に効いてきますから、適切な大きさの u を設定することで z を小さく抑えられる可能性が排除しきれないためです。特に u=5 あたりが厄介なところです。これは、前に25をかけて行った式変形が同値変形とは限らないことにも由来しています。
ということで、その式変形を更に吟味します。
(Y-5X)c_{1,i}=25Xd_{1,i}+(20X+26Y)m_{1,i} を (X+Y)c_{1,i}\equiv -Xd_{1,i}~\mod 20X+26Y に適用して再度整理します。
\begin{align*}
~&(X+Y)c_{1,i}\equiv -Xd_{1,i}~\mod 20X+26Y \\
\Rightarrow&(X+Y)\cdot\frac{25Xd_{1,i}+(20X+26Y)m_{1,i}}{Y-5X}+Xd_{1,i}\equiv 0~\mod 20X+26Y~(\text{分数部分は整数})\\
\Rightarrow&\frac{(X+Y)(25Xd_{1,i}+(20X+26Y)m_{1,i})+(Y-5X)Xd_{1,i}}{Y-5X}\equiv 0~\mod 20X+26Y~(\text{分数部分は整数})\\
\Rightarrow&\frac{(20X+26Y)(Xd_{1,i}+(X+Y)m_{1,i})}{Y-5X}\equiv 0~\mod 20X+26Y~(\text{分数部分は整数})\\
\end{align*}
これは、\frac{Xd_{1,i}+(X+Y)m_{1,i}}{Y-5X} が整数であることに他なりません。
すなわち、Xd_{1,i}+(X+Y)m_{1,i}\equiv 0~\mod~Y-5X
ここで、Y\equiv 5X~\mod Y-5X であることから、
\begin{align*}
~&Xd_{1,i}+(X+Y)m_{1,i}\equiv 0~\mod~Y-5X \\
\Leftrightarrow&Xd_{1,i}+(X+5X)m_{1,i}\equiv 0~\mod~u \\
\Leftrightarrow&X(d_{1,i}+6m_{1,i})\equiv 0~\mod~u \\
\Leftrightarrow&d_{1,i}+6m_{1,i}\equiv 0~\mod~u~~(\because gcd(X,u)=1) \\
\end{align*}
m_{1,i}\lt 0 である i に対し、詳細は省きますがこれまでと同じような計算で
d_{1,i}+6m_{1,i}\gt 0 が分かりますから、上の (\text{略})\equiv 0~\mod~u と併せて、
d_{1,i}\ge 6+u です。
これにより、X\ge 2^{6+u},~Y=5X+u\ge 5\cdot 2^{6+u}+u と Y の大きさを見積もることができました。
Y=uY' ( この Y' に関しては整数とは限りません ) と置くと、
z\gt Y^{Y/u}=(uY')^{Y'}=u^{Y'}\cdot Y'^{Y'} で、
Y'=\frac{Y}{u}\ge \frac{5\cdot 2^{6+u}}{u}+1=\frac{640\cdot 2^{u-1}}{u}+1\ge 641
最終的に、z\gt u^{Y'}\cdot Y'^{Y'}\ge 2^{641}\cdot 641^{641}\gt z_0 ということで、やはり z_0 が答えである最小の z ということが言えました。
具体的な解を求める方法だけでなく、他の解の大きさを見積もるのがなかなか大変でしたが、段階に分けて整理することで何とかなりました。
おわりに
今回で最後の2問も終わりました。
全体を通じてやや楽めかなという印象でしたが、最後だけはかなり大変でした。それでもなんとか解けてよかったと安心しているところです。
今年も12問解説できましたので、皆さんの参考になれば幸いです。
来年ももし全問解ければ、また解説を挙げたいと思います。
Discussion