🏅

日本数学オリンピック(JMO)2025年予選解答私的解説 その2

2025/01/20に公開

はじめに

背景

さる2025年1月13日(月,祝)実施された、第35回日本数学オリンピック予選につき、公開された問題を解いてみましたので、解説を挙げています。
予選は全部で12問あり、1つの記事にまとめると長くなるため、3回くらいにわけて解説しています。

参考情報

解説

それでは、今回の「その2」では、後半の問7~10の4問を解説していきます。

第7問

  • 問題: 縦20マス、横25マスのマス目があり、はじめどのマスにも何も書かれていない。太郎さんはこのマス目を使いゲームを行った。ゲームは何回かのターンに分けて行い、n回目のターンには以下の操作を行う。

    • 正の整数kと、何も書かれていないk個のマスA_1,A_2,\dots,A_kであって、任意の1以上k-1以下の整数iに対してA_{i+1}A_iの右または上に隣接するようなものを選ぶ。これらkマスすべてにnを書き込む。

    すべてのマスに数が書き込まれたときゲームを終了する。太郎さんがゲーム終了までのターン数をなるべく少なくするように行動するとき、ゲームが終了したときの数字の書き込まれ方としてありうるものは何通りあるか。
    ただし、回転や裏返しによって一致する書き込まれ方も異なるものとして数える。

  • 答え: 20!^3通り

さて、後半最初の問題ですが、実はこれも2025年絡みの問題になっています。
とは言え、20マス・25マスにそれ以上の特別な意味はなく、問題規模が大きくなっているだけなので、一旦縦5マス、横8マスくらいの小規模で考えてみます。

最初に考えるのはマスのかたまり\{A_i\}のことです。取り敢えず書きこむ数字 n のことは置いておいて、このかたまりはどういうものかと言うと、結局は次の図のように「幅1 (2×2のダンゴがない) で右下がりでない ( 右上がり、もしくは横一列 ) 道」となっているものを指しています。

ここで「ターン数をなるべく少なく」という条件があるため、逆に「1つのかたまりでどれだけマスを埋められるか」が重要になってくるわけですが、

この図のように、

  • 1つのかたまりでは1行を削るのが精いっぱい
  • 5行分埋めるのにかたまり5個必要

ということで、5×8マスの規模に直した状況ではかたまり5つというのが最小ターン数に対応します。
※列でなくて行で考えているのは、横の方が長いためです。

さてそうすると、1つのかたまりが各行に対応するわけですが、先ほどの図の一番上の行(紫色)を見れば分かるように、「行全部を埋める」という必要はありません。別の行を担当するかたまりが一部肩代わりするケースもあるからです。
となると、次の図のように中央の色がついている部分は担当が確定しますが、右上と左下の隅は未確定となります。ここで右上は置いておいて左下に着目します。

この未確定部分について、各行を担当するかたまりがどこまで下に伸びてきて埋めるか。それは一番上の行の担当なら5マス分まで高さを伸ばせますし、一番下の行の担当は既に決まっている1マスの高さから伸ばすことはできません。
つまり、選択肢としては一番上の行担当が5通り、二番目は4通り、三番目は3通り、4番目は2通り、五番目の一番下は1通りということです。

ここで実は何マスまで高さを伸ばすかを決めれば全体の埋め方が一意に決まるということに気付けるかどうかが鍵となります。
次の図は例えば、各行の担当が高さ2,3,3,1,1マスになるものですが、端が余らないように埋めることを考えるとやり方は1つに決まるのです。
※逆に、範囲内でどう高さを組み合わせても「埋められない」という状況は発生しません。

まあ、ここらへんの埋め方は数式化できないこともないのですが、そこは割愛します。問題を解く上では、結局ここの埋め方が何通りあるかが大事であって、それは結局高さの決め方 5! 通りで計算できるというところがポイントです。
そして、これは左下隅だけでなく右上隅でも全く同じ話になり、ここでも 5!通りになります。

これで埋め方、つまりかたまりの配置の仕方は分かりました。
残りは n の書き込みかたですが、これはどのかたまりが 1~5 を担当するかで 5! 通りです。
結局、「数字の書き込み方」としてはこの3種類のパターン数全ての積 5!^3 を計算したものになります。

ということで、5×8マスの小規模での問題が解けました。
今回の問題の 20×25マスにしても同じ考え方で計算ができますから、数字だけ差し替えて 20!^3 で答えが出ます。

小規模で状況を整理するというのが大事という好例のような問題であると思います。

第8問

  • 問題: 3以上の整数nに対し、整数からなる列a_1,a_2,\dots,a_n美しい列であるとは、次の条件をすべてみたすことをいう。

    • 0=a_1\lt a_2\lt\cdots\lt a_n
    • a_i=2025をみたす1以上n以下の整数iが存在する。
    • 任意の i\lt j\lt kをみたす1以上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番目の条件 \frac{a_i+a_k}{2}\le a_j ですので、これをどう料理するかですが、次のように変形するのがミソです。

  • a_k\le \underset{1\le i\lt j\lt k}{min} (2a_j-a_i) ただし k\ge 3

つまり、「全てのケースで○○以下」という条件を「○○の最小値以下」という考え方をするわけです。
このとき、問題の最初の条件から数列\{a_k\}は単調増加なので、i,j の組み合わせのうち i=j-1 の場合だけ見れば十分です。すなわち、

  • a_k\le \underset{2\le j\lt k}{min} (2a_j-a_{j-1}) ただし k\ge 3

ここでmin(最小)を使って嬉しいことは、帰納的な決め方ができるところです。
どういうことかと言うと、一般的な話として、「x_1,x_2,\cdots,x_n~(n\ge 2)の最小値」は「x_1,x_2,\cdots,x_{n-1}の最小値とx_{n}の最小値」として決めることができる、ということで、これは数列を伸ばしていく時に毎回全部の値を見ずに「直前までで決まった値」を利用すれば済むという強みがあります。

これを今回の「美しい列」の作り方に適用するとどういうことかと言うと、

  1. a_1=0,~a_2=a~(a\gt 0) を決める。
  2. m=a_2=a,~M=2a_2-a_1=2a を計算する。
  3. m\lt x\le M の範囲で x を選び、a_3=x とする。
  4. m'=x,~M'=min(M, 2x-m) を計算する。
  5. m',M' を新たな m,M とする。

という手順を考え、以下3~5を同じように a_4,a_5,\cdots に対して繰り返すことで、2025の条件を除いて「美しい列」が構成できるということです。

この作り方が分かった時点で、a_k の値を選択する下限の m は増加していくこと、上限の M は増加しないこと、この2点から列の長さが有限であることも分かります。
が、それ以上に選択の幅これを w=M-m とした場合、この幅は非常に急速に狭くなっていくことにも気づきます。それは、a_k を小さくすれば m の増加は小さく済むものの、M が大幅に減少してしまうこと、a_k を大きくすれば逆に M は値が維持できるものの、m の増加も大きくなるというトレードオフがあるためです。

では、この w=M-m の変化を見積もってみます。場合分けとしては、M の値が維持されるか減少するかというところになります。

  • 手順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} と半分以下になります。

いずれにせよ、w はどんどん半減以下になるよう変化し、その変化をなるべく緩やかに抑えるには \frac{m+M}{2} に近い値として x を選択する必要があると分かります。
ここで、「美しい列の長さとしてありうる最大」が問題の条件で指定されていることから、実際に最大の長さで作ってみます。美しい列には2025という値を含む必要がありますから、\{a_k\} が単調増加であることから a=a_1\le 2025 が必要で、a を決定した時に w の初期値として w=a\le 2025 も決まります。w がどんどん半分以下になっていき w\le 0 となるとそこで終わるわけなので、最長の美しい列として次が作れます。

  • 0, 2025, 3038, 3544, 3797, 3924, 3987, 4019, 4035, 4043, 4047, 4049, 4050

つまり、最長の列で長さN=13 ということで、これは a=20252^{13-3}\le a\lt 2^{14-3} の範囲にあるところから来ています。
ところでこの問題で最終的に求めるのは、このN=13 に対する a_N の最小値です。ということは、a_N=4050 の例が分かっただけではもちろん不十分で、

  • なるべく列の後ろの方に 2025 の値を配置し、
  • そこからなるべく小さく値を増やしていって列を構成する。

ということで、a_N が最小になる列を考える必要があります。
まず、長さ13の列を2025を含む条件を外してなるべく小さく構成すると、a=1024 で次のようになります。

  • 0, 1024, 1536, 1792, 1920, 1984, 2016, 2032, 2040, 2044, 2046, 2047, 2048

これは丁度w が2のべき乗で半減していく例です。
そうすると、長さ13という条件では a_8\ge 2032\gt 2025 となるので、列の中で2025が現れるのはなるべく後ろにしても a_7 が限界です。
そして、a_7 から a_{13} へなるべく小さく値を増やしていくとすると、上の a=1024 の例を見ても分かりますが +32 が最小です。
つまり、a_N を最小とするには、次の構成となることが分かります。

  • 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

ということで、この時点で答えは 2025+32=2057 と分かります。
実際にそのような構成ができるのか? という点は気になるでしょうが、実際に次のように構成することができるため問題ありません。

  • 0, 1033, 1545, 1801, 1929, 1993, 2025, 2041, 2049, 2053, 2055, 2056, 2057
    wは初期値1033、以降は512,256,128,…と2のべき乗で半減

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問目の図形の問題で、後半ともなると図は載っていません。
自分でどのように図を描いて情報を整理するか、そこから力が問われるところとなります。
なお、筆者はそれほど幾何が得意ではないので、ある程度情報を整理した後は基本的に三角比の計算でなんとかします。もっと幾何でエレガントに解く方法もありえると思いますが、悪しからずご了承ください。

まず、至るところに直角が現れるので、それに絡んだ円が ( \triangle ABC の外接円以外に ) 出てきます。そこを軸に整理してみます。

なんとこの図のとおり、A,E,D,O,F の5点が同一円周上です。しかもADはその円の直径になります。
ここで、AD=h,~\angle BAD=\alpha,~\angle CAD=\beta, \angle DAO=\theta とおいておきます。なお、鋭角三角形との条件がありますから、\alpha+\beta\lt 90\degree です。
※この図では \alpha\lt \beta として描いていますが、実は大小関係が逆転していても問題が成立します。ただ、その場合、図の左右を反転すれば同じ話になるので、ここではこの大小関係で話を進めます。

さて、それで長さの条件を色々整備すると、

  • 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) …⑥

ひとまずここで話を変えて、今度は O が外心であることを思い出します。
その条件をどう利用するかですが、「外心は各辺の垂直二等分線の交点」ということで、O から各辺に垂線を引けば、その足は各辺の中点になるはずです。

すなわち、上の図のような状況で、

  • 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条件を眺めていると、両方とも値\frac{1}{2}で一致しているわけですが、なんとなく式の形が似ているし \theta=\beta-\alpha だと丁度一致しそうだよなあ…と思えてきます。で、実際確かにその条件が成立します。
ちゃんと示そうと思ったら cos\alpha\cos(\alpha+\theta)=\frac{1}{2}(\cos(2\alpha+\theta)+\cos\theta) みたいな積和で変形して比較、とかになるのですが細かいところは割愛します。
ともかく、

  • \theta=\beta-\alpha …⑦
  • \cos\alpha\cos\beta\cos(\beta-\alpha)=\frac{1}{2} …⑧

の2条件に整理し直すことができました。

\theta が判明したところで、③の条件が次のように変わります。

  • h\sin(\beta-\alpha)=4\sqrt{7} …⑨

が、それはそれとして改めて図に戻ります。

このように、\angle PAF=\alpha ということが分かるため、\angle EAD と同じEDの円周角 \angle EFD=\alpha と、\angle AFD が直角であることを合わせると、新たに \angle APF も直角であることが分かります。
ここから、

  • AP=AF\cos\alpha

もともと問題で AP=11 という条件がありましたから、これと⑤を合わせて、

  • h\cos\alpha\cos\beta=11 …⑩

という条件になります。

これで条件は出揃いました。改めて挙げると以下の4条件で、最後のEFが求める答えです。

  • 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 から、2\sin(\beta-\alpha)cos(\beta-\alpha)=\frac{4\sqrt{7}}{11} これにより \sin 2(\beta-\alpha)=\frac{4\sqrt{7}}{11}
続いて \cos 2(\beta-\alpha)=\sqrt{1-\sin^{2}2(\beta-\alpha)}=\frac{3}{11}
※このcosの値は負になる可能性もあるのですが、その場合後の計算で破綻が起きますので ( 詳細は割愛します ) 正の方で話を進めます。

今度は、倍角のcosが分かったので半角の計算をして、
\cos(\beta-\alpha)=\sqrt{\frac{1+\cos 2(\beta-\alpha)}{2}}=\frac{\sqrt{7}}{\sqrt{11}}
\sin(\beta-\alpha)=\sqrt{\frac{1-\cos 2(\beta-\alpha)}{2}}=\frac{2}{\sqrt{11}}

この sin の値と⑨,⑩を組み合わせて、
h=\frac{4\sqrt{7}}{\sin(\beta-\alpha)}=2\sqrt{77}
\cos\alpha\cos\beta=\frac{11}{h}=\frac{\sqrt{11}}{2\sqrt{7}}
そこから
\cos(\alpha+\beta)=2\cos\alpha\cos\beta-\cos(\beta-\alpha)=2\cdot\frac{\sqrt{11}}{2\sqrt{7}}-\frac{\sqrt{7}}{\sqrt{11}}=\frac{4}{\sqrt{77}}

ここまで来たら後は大詰めです。
\sin(\alpha+\beta)=\sqrt{1-\cos^2 (\alpha+\beta)}=\frac{\sqrt{61}}{\sqrt{77}}
EF=h\sin(\alpha+\beta)=2\sqrt{77}\cdot\frac{\sqrt{61}}{\sqrt{77}}=2\sqrt{61}
ということで答えが求まります。

最後の三角比の計算、もっと短縮できないものかとも思いますが、まあ答えが出たからヨシ! ということにしておきます。

第10問

  • 問題: S={0,1,2,\dots,8} とおく。S上で定義されSに値をとる関数fであって、任意のSの要素x,y,zに対して、x+y-zが9の倍数ならばf(x)f(y)-f(f(z))も9の倍数であるようなものはいくつあるか。
  • 答え: 858個

関数の問題ですが、いよいよ終盤ともなるとなかなか掴みどころがないところです。
取り敢えず「9の倍数」が出てくるので、計算を全て \mod 9 の世界で考えることにします。
例えば「x+y-z が9の倍数」というのは x+y\equiv z~\mod~9 ということですが、これを単に x+y=z で表記することにし、他にも f(x+y)f(x)f(y) といった計算も、それぞれ f(mod(x+y,9)),~mod(f(x)f(y),9) として扱うということです。

そうすると、問題の条件「x+y-zが9の倍数ならばf(x)f(y)-f(f(z))も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) …② も同値です。

条件これだけかよ、と思わなくもないですが、ここから整理を始めるより他ありません。
ここで、V=f(S)\subset S という集合に着目してみます。これは「f の値を集めた集合」であり、別の表現をすれば V=\{v|\exists x\in S, f(x)=v\} ということです。

当然、f(x), f(y)\in V ですが、f(f(x+y))=f(x)f(y) ということは積の値も V に含まれる、つまり V は積に関して閉じていることを表します。
改めて書き直すと、

  • a,b\in V ならば ab\in V …③

ここから派生して、次のことも帰納的に分かります。

  • a\in V ならば、1以上の整数 r に対し a^r\in V …④
    ※冒頭で「計算を全て \mod 9 の世界で考える」と言ったのですが、すみません。指数の部分だけは一緒くたにできないので、そこだけ普通の整数の演算で考えてください。

さて。ここまで来たところで、今回\mod 9 の世界で考えているわけですが、ここにはゼロ因子的な要素があることに着目します。
すなわち、通常の掛け算であれば ab=0\Rightarrow a=0~or~b=0 ですが、\mod 9 の世界ではそれが成り立たない要素があるということです。それが 3,6 になります。
このゼロ因子 ( またはゼロそのもの ) が絡んでくるかどうかで状況が大きく変わるため、場合分けして整理していきます。

  • V がゼロ/ゼロ因子 ( 0,3,6 ) のいずれかを含む場合
    今回ゼロ因子はべき乗すると ( というか、2乗するだけで ) ゼロになる、つまり 3^2=6^2=0^1=0 という性質を持っているため、条件④から 0\in V が確定します。
    そうすると、条件② f(f(z))=f(x)f(z-x)f(x)=0 となる x を考えると、実は任意の zf(f(z))=0 という強力な条件が得られます。
    これは言い方を変えると、x\in V ならば f(x)=0 ということでもあります。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 で問題の条件を満たします。このような f3^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 が必要で、またこれであれば十分問題の条件を満たします。このような f2^6個あります。
    • f(0)=f(6)=0,~f(3)=6 の場合
      直前と 3,6 をひっくり返しただけなので、x\neq 0,3,6 に対して f(x)=0~or~6 で問題の条件を満たします。このような f2^6個あります。

    これ以外のケース、例えば f(3)=3 等では f(f(z))=0 を一部満たせなくなるため、ゼロ/ゼロ因子を含むケースはこれで全てとなります。

  • V がゼロ/ゼロ因子 ( 0,3,6 ) を含まない場合
    この場合、V の要素の候補は 1,2,4,5,7,8 になるわけですが、これもべき乗してみると同じ条件に辿り着きます。
    それは、1^1=2^6=4^3=5^6=7^3=8^2=1 ( 今更ですが\mod~9での話です ) と全てべき乗で 1 になる要素であることから、条件④より 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 であれば、容易に問題の条件を満たすことが分かりますから、この f 1個分も答えに算入することになります。

ということで両ケースの整理が終わりました。
結局条件を満たす f は、V がゼロ/ゼロ因子を含む場合の 3^6+2^6+2^6個、含まない場合の1個で全てなので、これらを足し合わせて 858個と計算でき、これが答えとなります。

こうして書き挙げてみると単純そうではありますが、限られた条件から話を広げていくところ、なかなか骨が折れる問題かと思います。

おわりに

ということで、後半の4問を解説しました。分かってしまえばそう難しくはないとも言えるのですが、解説の分量が結構嵩んでいるように、ちゃんと整理するのはやはり大変になっています。
最後の難関2問については次で解説します。

Discussion