日本数学オリンピック(JMO)2025年予選解答私的解説 その2
はじめに
背景
さる2025年1月13日(月,祝)実施された、第35回日本数学オリンピック予選につき、公開された問題を解いてみましたので、解説を挙げています。
予選は全部で12問あり、1つの記事にまとめると長くなるため、3回くらいにわけて解説しています。
参考情報
- その1 … https://zenn.dev/angel_p_57/articles/673cd22d4bd0b6
- その3 … https://zenn.dev/angel_p_57/articles/40b8189a34918c
- 問題公開先 … https://www.imojp.org/archive/mo2025/jmo/problems/jmo35yqa.pdf
解説
それでは、今回の「その2」では、後半の問7~10の4問を解説していきます。
第7問
-
問題: 縦20マス、横25マスのマス目があり、はじめどのマスにも何も書かれていない。太郎さんはこのマス目を使いゲームを行った。ゲームは何回かのターンに分けて行い、
回目のターンには以下の操作を行う。n - 正の整数
と、何も書かれていないk 個のマスk であって、任意の1以上A_1,A_2,\dots,A_k 以下の整数k-1 に対してi がA_{i+1} の右または上に隣接するようなものを選ぶ。これらA_i マスすべてにk を書き込む。n
すべてのマスに数が書き込まれたときゲームを終了する。太郎さんがゲーム終了までのターン数をなるべく少なくするように行動するとき、ゲームが終了したときの数字の書き込まれ方としてありうるものは何通りあるか。
ただし、回転や裏返しによって一致する書き込まれ方も異なるものとして数える。 - 正の整数
-
答え:
通り20!^3
さて、後半最初の問題ですが、実はこれも2025年絡みの問題になっています。
とは言え、20マス・25マスにそれ以上の特別な意味はなく、問題規模が大きくなっているだけなので、一旦縦5マス、横8マスくらいの小規模で考えてみます。
最初に考えるのはマスのかたまり
ここで「ターン数をなるべく少なく」という条件があるため、逆に「1つのかたまりでどれだけマスを埋められるか」が重要になってくるわけですが、
この図のように、
- 1つのかたまりでは1行を削るのが精いっぱい
- 5行分埋めるのにかたまり5個必要
ということで、5×8マスの規模に直した状況ではかたまり5つというのが最小ターン数に対応します。
※列でなくて行で考えているのは、横の方が長いためです。
さてそうすると、1つのかたまりが各行に対応するわけですが、先ほどの図の一番上の行(紫色)を見れば分かるように、「行全部を埋める」という必要はありません。別の行を担当するかたまりが一部肩代わりするケースもあるからです。
となると、次の図のように中央の色がついている部分は担当が確定しますが、右上と左下の隅は未確定となります。ここで右上は置いておいて左下に着目します。
この未確定部分について、各行を担当するかたまりがどこまで下に伸びてきて埋めるか。それは一番上の行の担当なら5マス分まで高さを伸ばせますし、一番下の行の担当は既に決まっている1マスの高さから伸ばすことはできません。
つまり、選択肢としては一番上の行担当が5通り、二番目は4通り、三番目は3通り、4番目は2通り、五番目の一番下は1通りということです。
ここで実は何マスまで高さを伸ばすかを決めれば全体の埋め方が一意に決まるということに気付けるかどうかが鍵となります。
次の図は例えば、各行の担当が高さ2,3,3,1,1マスになるものですが、端が余らないように埋めることを考えるとやり方は1つに決まるのです。
※逆に、範囲内でどう高さを組み合わせても「埋められない」という状況は発生しません。
まあ、ここらへんの埋め方は数式化できないこともないのですが、そこは割愛します。問題を解く上では、結局ここの埋め方が何通りあるかが大事であって、それは結局高さの決め方
そして、これは左下隅だけでなく右上隅でも全く同じ話になり、ここでも
これで埋め方、つまりかたまりの配置の仕方は分かりました。
残りは
結局、「数字の書き込み方」としてはこの3種類のパターン数全ての積
ということで、5×8マスの小規模での問題が解けました。
今回の問題の 20×25マスにしても同じ考え方で計算ができますから、数字だけ差し替えて
小規模で状況を整理するというのが大事という好例のような問題であると思います。
第8問
-
問題: 3以上の整数
に対し、整数からなる列n が美しい列であるとは、次の条件をすべてみたすことをいう。a_1,a_2,\dots,a_n 0=a_1\lt a_2\lt\cdots\lt a_n -
をみたす1以上a_i=2025 以下の整数n が存在する。i - 任意の
をみたす1以上i\lt j\lt k 以下の整数n に対し、i,j,k が成り立つ。\frac{a_i+a_k}{2}\le a_j
美しい列の長さとしてありうる最大の値を
とおく。長さN の美しい列N について、a_1,a_2,\dots,a_N としてありうる最小の値を求めよ。a_N
ただし、整数からなる列 の長さはa_1,x_2,\dots,x_l である。l -
答え: 2057
今回最後の2025年関連問題で、有限の長さの数列に関するものとなっています。
取り敢えず鍵になるのは、もちろん3番目の条件
-
ただしa_k\le \underset{1\le i\lt j\lt k}{min} (2a_j-a_i) k\ge 3
つまり、「全てのケースで○○以下」という条件を「○○の最小値以下」という考え方をするわけです。
このとき、問題の最初の条件から数列
-
ただしa_k\le \underset{2\le j\lt k}{min} (2a_j-a_{j-1}) k\ge 3
ここでmin(最小)を使って嬉しいことは、帰納的な決め方ができるところです。
どういうことかと言うと、一般的な話として、「
これを今回の「美しい列」の作り方に適用するとどういうことかと言うと、
-
を決める。a_1=0,~a_2=a~(a\gt 0) -
を計算する。m=a_2=a,~M=2a_2-a_1=2a -
の範囲でm\lt x\le M を選び、x とする。a_3=x -
を計算する。m'=x,~M'=min(M, 2x-m) -
を新たなm',M' とする。m,M
という手順を考え、以下3~5を同じように
この作り方が分かった時点で、
が、それ以上に選択の幅これを
では、この
- 手順3で
となるx\lt\frac{m+M}{2} を選択した場合x
であるため、2x-m\lt M です。M'=2x-m
すなわち次の幅 はw'=M'-m' と半分未満になります。w'=2x-m-x=x-m\lt\frac{M-m}{2}=\frac{w}{2} - 手順3で
となるx\ge\frac{m+M}{2} を選択した場合x
であるため、2x-m\ge M です。M'=M
すなわち次の幅 はw'=M'-m' と半分以下になります。w'=M-x\le\frac{M-m}{2}=\frac{w}{2}
いずれにせよ、
ここで、「美しい列の長さとしてありうる最大」が問題の条件で指定されていることから、実際に最大の長さで作ってみます。美しい列には2025という値を含む必要がありますから、
- 0, 2025, 3038, 3544, 3797, 3924, 3987, 4019, 4035, 4043, 4047, 4049, 4050
つまり、最長の列で長さ
ところでこの問題で最終的に求めるのは、この
- なるべく列の後ろの方に 2025 の値を配置し、
- そこからなるべく小さく値を増やしていって列を構成する。
ということで、
まず、長さ13の列を2025を含む条件を外してなるべく小さく構成すると、
- 0, 1024, 1536, 1792, 1920, 1984, 2016, 2032, 2040, 2044, 2046, 2047, 2048
これは丁度
そうすると、長さ13という条件では
そして、
つまり、
-
として、そのときa_7=2025 を確保しておき、w\ge 32 -
とする。a_{13}=a_{7}+32
このときa_8=a_7+16,~a_9=a_8+8,~a_{10}=a_9+4,~a_{11}=a_{10}+2,~a_{12}=a_{11}+1,~a_{13}=a_{12}+1
ということで、この時点で答えは
実際にそのような構成ができるのか? という点は気になるでしょうが、実際に次のように構成することができるため問題ありません。
- 0, 1033, 1545, 1801, 1929, 1993, 2025, 2041, 2049, 2053, 2055, 2056, 2057
※ は初期値1033、以降は512,256,128,…と2のべき乗で半減w
minで条件を表現したうえで、なるべく長く列を構成する方法を探れば、答えに辿り着くのは難しくはないと思います。
第9問
- 問題: 鋭角三角形
があり、その外心をABC とする。O から辺A におろした垂線の足をBC とすると、D が成立した。\angle AOD=90\degree,~OD=4\sqrt{7} から辺D におろした垂線の足をそれぞれAB,AC とおくと、線分E,F と線分AO が点EF で交わった。P のとき、線分AP=11 の長さを求めよ。EF
ただし、 で線分XY の長さを表すものとする。XY - 答え:
2\sqrt{61}
今回2問目の図形の問題で、後半ともなると図は載っていません。
自分でどのように図を描いて情報を整理するか、そこから力が問われるところとなります。
なお、筆者はそれほど幾何が得意ではないので、ある程度情報を整理した後は基本的に三角比の計算でなんとかします。もっと幾何でエレガントに解く方法もありえると思いますが、悪しからずご了承ください。
まず、至るところに直角が現れるので、それに絡んだ円が (
なんとこの図のとおり、
ここで、
※この図では
さて、それで長さの条件を色々整備すると、
-
…①AB=\frac{h}{\cos\alpha} -
…②AC=\frac{h}{\cos\beta} -
これとOD=h\sin\theta からOD=4\sqrt{7} …③h\sin\theta=4\sqrt{7} -
…④AO=h\cos\theta -
…⑤AF=h\cos\beta -
…⑥EF=h\sin(\alpha+\beta)
ひとまずここで話を変えて、今度は
その条件をどう利用するかですが、「外心は各辺の垂直二等分線の交点」ということで、
すなわち、上の図のような状況で、
AM=\frac{1}{2}AB=AO\cos(\alpha+\theta) AN=\frac{1}{2}AC=AO\cos(\beta-\theta)
が成立します。
この条件と、先に挙げた①,②,⑥を組み合わせると、
\cos\alpha\cos\theta\cos(\alpha+\theta)=\frac{1}{2} \cos\beta\cos\theta\cos(\beta-\theta)=\frac{1}{2}
この2条件が分かります。
更に、この2条件を眺めていると、両方とも値
ちゃんと示そうと思ったら
ともかく、
-
…⑦\theta=\beta-\alpha -
…⑧\cos\alpha\cos\beta\cos(\beta-\alpha)=\frac{1}{2}
の2条件に整理し直すことができました。
-
…⑨h\sin(\beta-\alpha)=4\sqrt{7}
が、それはそれとして改めて図に戻ります。
このように、
ここから、
AP=AF\cos\alpha
もともと問題で
-
…⑩h\cos\alpha\cos\beta=11
という条件になります。
これで条件は出揃いました。改めて挙げると以下の4条件で、最後の
-
…⑨h\sin(\beta-\alpha)=4\sqrt{7} -
…⑩h\cos\alpha\cos\beta=11 -
…⑧\cos\alpha\cos\beta\cos(\beta-\alpha)=\frac{1}{2} -
…⑥EF=h\sin(\alpha+\beta)
後は計算を頑張ればなんとかなります。
⑨÷⑩×⑧×2 から、
続いて
※このcosの値は負になる可能性もあるのですが、その場合後の計算で破綻が起きますので ( 詳細は割愛します ) 正の方で話を進めます。
今度は、倍角のcosが分かったので半角の計算をして、
この sin の値と⑨,⑩を組み合わせて、
そこから
ここまで来たら後は大詰めです。
ということで答えが求まります。
最後の三角比の計算、もっと短縮できないものかとも思いますが、まあ答えが出たからヨシ! ということにしておきます。
第10問
- 問題:
とおく。S={0,1,2,\dots,8} 上で定義されS に値をとる関数S であって、任意のf の要素S に対して、x,y,z が9の倍数ならばx+y-z も9の倍数であるようなものはいくつあるか。f(x)f(y)-f(f(z)) - 答え: 858個
関数の問題ですが、いよいよ終盤ともなるとなかなか掴みどころがないところです。
取り敢えず「9の倍数」が出てくるので、計算を全て
例えば「
そうすると、問題の条件「
- 任意の
に対し、x,y\in S …①f(f(x+y))=f(x)f(y)
※別バージョンとして、任意の に対しz,x\in S …② も同値です。f(f(z))=f(x)f(z-x)
条件これだけかよ、と思わなくもないですが、ここから整理を始めるより他ありません。
ここで、
当然、
改めて書き直すと、
-
ならばa,b\in V …③ab\in V
ここから派生して、次のことも帰納的に分かります。
-
ならば、1以上の整数a\in V に対しr …④a^r\in V
※冒頭で「計算を全て の世界で考える」と言ったのですが、すみません。指数の部分だけは一緒くたにできないので、そこだけ普通の整数の演算で考えてください。\mod 9
さて。ここまで来たところで、今回
すなわち、通常の掛け算であれば
このゼロ因子 ( またはゼロそのもの ) が絡んでくるかどうかで状況が大きく変わるため、場合分けして整理していきます。
-
がゼロ/ゼロ因子 ( 0,3,6 ) のいずれかを含む場合V
今回ゼロ因子はべき乗すると ( というか、2乗するだけで ) ゼロになる、つまり という性質を持っているため、条件④から3^2=6^2=0^1=0 が確定します。0\in V
そうすると、条件② でf(f(z))=f(x)f(z-x) となるf(x)=0 を考えると、実は任意のx でz という強力な条件が得られます。f(f(z))=0
これは言い方を変えると、 ならばx\in V ということでもあります。0 はf(x)=0 の要素であることが確定してますからV も確定します。f(0)=0
また、①の条件を見直すと、実は ということも分かります。表現を替えると、f(x)f(y)=f(f(x+y))=0 ならばa,b\in V ということです。ab=0
だとすると条件③に照らし合わせて、掛け合わせても 0 にならない非ゼロ/ゼロ因子の要素 1,2,4,5,7,8 は実はどれも に含まれません。つまり、V の要素はゼロ/ゼロ因子に限られる (V ) というところまで確定します。V\subset \{0,3,6\}
後は更に細かく場合分けして整理していきます。-
の場合f(0)=f(3)=f(6)=0
に対してx\neq 0,3,6 で問題の条件を満たします。このようなf(x)=0~or~3~or~6 はf 個あります。3^6 -
の場合f(0)=f(3)=0,~f(6)=3
を満たすためにはf(f(z))=0 となるようなf(x)=6 は存在できません。x
そのため、 に対してx\neq 0,3,6 が必要で、またこれであれば十分問題の条件を満たします。このようなf(x)=0~or~3 はf 個あります。2^6 -
の場合f(0)=f(6)=0,~f(3)=6
直前と 3,6 をひっくり返しただけなので、 に対してx\neq 0,3,6 で問題の条件を満たします。このようなf(x)=0~or~6 はf 個あります。2^6
これ以外のケース、例えば
等ではf(3)=3 を一部満たせなくなるため、ゼロ/ゼロ因子を含むケースはこれで全てとなります。f(f(z))=0 -
-
がゼロ/ゼロ因子 ( 0,3,6 ) を含まない場合V
この場合、 の要素の候補は 1,2,4,5,7,8 になるわけですが、これもべき乗してみると同じ条件に辿り着きます。V
それは、 ( 今更ですが1^1=2^6=4^3=5^6=7^3=8^2=1 での話です ) と全てべき乗で 1 になる要素であることから、条件④より\mod~9 が言えるということです。1\in V
次に、 に着目します。a=f(0)\in V
条件①で のケースを考えると、y=0 となりますが、これはf(f(x))=f(x)f(0)=af(x) で置き換えると、z=f(x) ならばz\in V ということでもあります。ここから、次のことが分かります。f(z)=az -
であるため1\in V f(1)=a\cdot 1=a -
は非ゼロ/ゼロ因子であるためa が存在し、a^{-1} であれば、f(f(x))=b f(x)=a^{-1}b
ここまで整理したならば、今度は条件①で
のケースに着目し、先ほどの条件と組み合わせます。y=1 -
これによりf(f(x+1))=f(x)f(1)=af(x) f(x+1)=a^{-1}\cdot af(x)=f(x)
この条件により、帰納法の要領と同じで、
とf(0)=f(1)=\cdots=f(7)=f(8) の全ての値が同一、つまりf が定数関数と確定することになります。ここでf であることから これは1\in V 以外にはありえません。f(x)=1
逆に定数関数 であれば、容易に問題の条件を満たすことが分かりますから、このf(x)=1 1個分も答えに算入することになります。f -
ということで両ケースの整理が終わりました。
結局条件を満たす
こうして書き挙げてみると単純そうではありますが、限られた条件から話を広げていくところ、なかなか骨が折れる問題かと思います。
おわりに
ということで、後半の4問を解説しました。分かってしまえばそう難しくはないとも言えるのですが、解説の分量が結構嵩んでいるように、ちゃんと整理するのはやはり大変になっています。
最後の難関2問については次で解説します。
Discussion