0

2027JMO詳解

635
1
$$$$

2027 JMO予選 詳解


第1問|積の対称性

答え
$$ \boxed{\frac{12}{5}} $$

着想

4数から得られる6個の積を、積が等しくなる3組に分ける。

解答

4数を次のようにおく。
$$ a,b,c,d $$
このとき、
$$ (ab)(cd)=(ac)(bd)=(ad)(bc)=abcd $$
が成り立つ。したがって、6個の積
$$ ab,\ ac,\ ad,\ bc,\ bd,\ cd $$
は、各組の積が等しい3組に分かれる。うち5個は次の数である。
$$ 2,\ 3,\ 4,\ 5,\ 6 $$
よって、少なくとも2組はこの5数だけで構成される。相異なる4数から作る等積の2組は、
$$ 2\cdot6=3\cdot4=12 $$
に限られる。残る1組の積も12であるから、消した数を未知数とすると、
$$ 5x=12\quad\Longrightarrow\quad \boxed{x=\frac{12}{5}}. $$
実際、
$$ \begin{aligned} a&=\sqrt{\frac{5}{2}},& b&=2\sqrt{\frac{2}{5}},\\ c&=3\sqrt{\frac{2}{5}},& d&=5\sqrt{\frac{2}{5}} \end{aligned} $$
とすれば成立する。
要点: 個々の実数ではなく、組にした積を不変量として使う。


第2問|面積比と線形性

答え
$$ \boxed{96} $$

着想

次の平行関係を利用し、2つの三角形の面積比を底辺比と高さ比に分解する。
$$ PB\parallel CD $$

解答

平行四辺形の面積と線分の比を、次のようにおく。
$$ S=[ABCD],\qquad PQ:QD=m:n $$
条件から、
$$ AP:PB=7:2,\qquad PB:CD=2:9. $$
したがって、
$$ \frac{20}{27}= \frac{[QPB]}{[QCD]} =\frac{2}{9}\cdot\frac{m}{n} \quad\Longrightarrow\quad PQ:QD=10:3. $$
さらに、
$$ [QCD]=\frac{3}{13}[PCD]=27 $$
より、
$$ [PCD]=117,\qquad S=234. $$
よって、
$$ [PBC]=\frac{2}{9}[ABC] =\frac{2}{9}\cdot117=26, \qquad [DBC]=117. $$
点Qは線分PDを10:3に内分し、底辺BCに対する高さは頂点の位置に比例して変化する。したがって、
$$ \begin{aligned} [QBC] &=\frac{3}{13}[PBC]+\frac{10}{13}[DBC]\\ &=\frac{3\cdot26+10\cdot117}{13} =\boxed{96}. \end{aligned} $$

別解|面積の加減

$$ [QPC]=[PCD]-[QCD]=117-27=90 $$
だから、
$$ [QBC]=[PBC]+[QPC]-[QPB] =26+90-20=96. $$
両解法の核は同じ面積の線形性である。前者は内分比、後者は面積の加減で処理する。


第3問|平方数と指数の偶奇

答え
$$ \boxed{3\cdot2^{2026}} $$

着想

積の大きさではなく、素因数2、3の指数の偶奇だけを記録する。

解答

各段階の積は
$$ 2^u3^v $$
と表せ、平方数であるための必要十分条件は指数がともに偶数であること。状態を
$$ (u\bmod2,\ v\bmod2) $$
で表すと、
$$ \begin{array}{c|cccc} \text{状態}&(0,0)&(1,0)&(0,1)&(1,1)\\\hline \text{平方数か}&\text{はい}&\text{いいえ}&\text{いいえ}&\text{いいえ} \end{array} $$
となる。2、3、6を掛ける操作は、それぞれ次の状態を加えることに相当する。ただし各成分は2で割った余りをとる。
$$ (1,0),\quad(0,1),\quad(1,1) $$
第1項は3通り。その後、非零状態から零状態に移るのは、現在と同じ状態を加える1通りだけである。したがって第2項以降は毎回2通りとなり、
$$ \boxed{3\cdot2^{2026}}. $$
背景: 無数の積を4状態に圧縮する発想は、有限状態の漸化式や合同式の問題にも応用できる。


第4問|操作の不変量と2進表示

答え
$$ \boxed{126} $$

着想

与えられた操作の結果を、最初の9数
$$ 2^0,\ 2^1,\ldots,\ 2^8 $$
の符号付き和で表す。

解答

どの段階でも、各数は最初の数のうち互いに重ならないものの符号付き和で表される。その係数の総和は、初めは各数について1であり、操作後も
$$ 1+1-1=1 $$
と保たれる。
最後の数を
$$ T=\sum_{i=0}^{8}\varepsilon_i2^i, \qquad\varepsilon_i\in\{-1,1\} $$
とすると、
$$ \sum_{i=0}^{8}\varepsilon_i=1. $$
したがって正符号が5個、負符号が4個である。
逆に、このような任意の符号配置は実現できる。正符号2個と負符号1個を選び、与えられた操作によって正符号の組1つにまとめる。この操作を4回繰り返せばよい。
さらに、
$$ \begin{aligned} T&=\sum_{i=0}^{8}2^i -2\sum_{\varepsilon_i=-1}2^i\\ &=511-2\sum_{\varepsilon_i=-1}2^i. \end{aligned} $$
2進表示の一意性より、負符号を付ける4数の選び方が異なれば結果も異なる。ゆえに、
$$ \boxed{\binom{9}{4}=126}. $$


第5問|約数関数の差分

答え
$$ \boxed{243,\ 1458,\ 1875} $$

着想

2倍、3倍、4倍した整数の約数の個数を比較するため、素因数2、3の指数を分離する。

解答

次のようにおく。
$$ n=2^a3^bm,\qquad \gcd(m,6)=1, \qquad D=d(m). $$
すると、
$$ \begin{aligned} d(n)&=(a+1)(b+1)D, &d(2n)&=(a+2)(b+1)D,\\ d(3n)&=(a+1)(b+2)D, &d(4n)&=(a+3)(b+1)D. \end{aligned} $$
よって条件は、
$$ (b-a)D=5 $$
に等しい。Dは正整数だから、可能性は次の2通りである。
$$ (b-a,D)=(5,1),\ (1,5). $$
① 約数が1個の場合
$$ \begin{aligned} D&=1,\quad m=1,\quad b=a+5,\\ n&=243\cdot6^a\le2027. \end{aligned} $$
これより、
$$ a=0,1\quad\Longrightarrow\quad n=243,1458. $$
② 約数が5個の場合
$$ \begin{aligned} D&=5,\quad m=p^4,\quad p\ge5\ \text{(素数)},\\ b&=a+1,\quad n=3\cdot6^ap^4\le2027. \end{aligned} $$
これより、
$$ a=0,\quad p=5\quad\Longrightarrow\quad n=1875. $$
したがって、
$$ \boxed{243,\ 1458,\ 1875}. $$
背景: 約数関数の乗法性
$$ \gcd(u,v)=1\quad\Longrightarrow\quad d(uv)=d(u)d(v) $$
を利用している。


第6問|ガウス記号と階差

答え
$$ \boxed{949} $$

着想

次のようにおくと、各項は階差を含む積となる。
$$ a_n=[\sqrt{10n}],\qquad a_n(a_n-a_{n-1}) $$
階差が0か1なら、増加したときの値だけを加えればよい。

解答

$$ a_0=0,\qquad a_1=3,\quad a_2=4,\quad a_3=5. $$
また、4番目以降では、
$$ \begin{aligned} \sqrt{10n}-\sqrt{10(n-1)} &=\frac{10}{\sqrt{10n}+\sqrt{10(n-1)}}\\ &<1\qquad(n\ge4). \end{aligned} $$
したがって、
$$ a_n-a_{n-1}\in\{0,1\}\quad(n\ge2), \qquad a_{190}=[\sqrt{1900}]=43. $$
$$ \begin{array}{c|ccccc} n&0&1&2&3&4\\\hline a_n&0&3&4&5&6\\ a_n(a_n-a_{n-1})&-&9&4&5&6 \end{array} $$
第1項は9、その後は4から43までの整数がそれぞれ1回ずつ加わる。よって、
$$ \begin{aligned} \sum_{n=1}^{190}a_n(a_n-a_{n-1}) &=9+\sum_{k=4}^{43}k\\ &=9+\frac{43\cdot44}{2}-6\\ &=\boxed{949}. \end{aligned} $$
要点: ガウス記号を含む和は、値が変化する位置に注目すると簡単になる場合がある。


第7問|外心と相似

答え
$$ \boxed{\frac{13}{49}} $$

着想

2つの外心は線分ADの垂直二等分線上にある。また、3つの外心を結ぶ直線は、それぞれ元の三角形の辺に垂直である。この関係から角追いをする。

主解法|初等幾何

点の配置を模式的に示す。
$$ \xymatrix@C=3em@R=2.5em{ & A\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&\\ B\ar@{-}[r]&D\ar@{-}[r]&C } $$
次のようにおき、線分ADの中点をMとする。
$$ \angle BAC=\alpha,\qquad \angle ABC=\beta,\qquad \angle ACB=\gamma. $$
外心の性質から、
$$ O_1O_2\perp AD,\qquad OO_1\perp AB,\qquad OO_2\perp AC. $$
三角形ABCが鋭角三角形であるため、2つの外心はMの両側にある。また、
$$ \angle DO_1O_2=\beta,\qquad \angle DO_2O_1=\gamma. $$
したがって、
$$ \triangle DO_1O_2\sim\triangle ABC, \qquad \angle O_1DO_2=\alpha.\tag{1} $$
一方、Oは三角形DO₁O₂の外心でもあるから、
$$ OO_1=OO_2. $$
二等辺三角形OO₁O₂の底角は、各垂直関係から、
$$ \angle OO_1O_2=\angle BAD, \qquad \angle OO_2O_1=\angle DAC. $$
よって、
$$ \angle O_1OO_2=180^\circ-\alpha.\tag{2} $$
また、(1) と中心角・円周角の定理より、小さい中心角は
$$ \angle O_1OO_2=2\alpha.\tag{3} $$
(2)、(3) より、
$$ \alpha=60^\circ. $$
さらに二等辺三角形の底角が等しいから、
$$ \angle BAD=\angle DAC=30^\circ. $$
したがってADは角の二等分線である。
辺の長さを、
$$ BD=3t,\quad DC=4t,\qquad AB=3u,\quad AC=4u $$
とおくことができる。余弦定理より、
$$ BC^2=9u^2+16u^2-12u^2 =13u^2=49t^2.\tag{4} $$
また、
$$ \angle BO_1D=2\angle BAD=60^\circ, \qquad O_1B=O_1D $$
より、三角形BO₁Dは正三角形となる。同様に三角形DO₂Cも正三角形となるので、
$$ DO_1=3t,\qquad DO_2=4t. $$
線分O₁O₂はADの垂直二等分線であるから、
$$ [AO_1O_2]=[DO_1O_2]. $$
したがって、(4) より、
$$ \begin{aligned} \frac{[AO_1O_2]}{[ABC]} &=\frac{DO_1\cdot DO_2\sin60^\circ} {AB\cdot AC\sin60^\circ}\\ &=\frac{t^2}{u^2}=\frac{13}{49}. \end{aligned} $$
三角形ABCの面積は1なので、
$$ \boxed{[AO_1O_2]=\frac{13}{49}}. $$

別解|座標幾何

面積比は拡大縮小で変わらない。次のようにおく。
$$ \begin{gathered} D=(0,0),\quad B=(-3,0),\quad C=(4,0),\\ A=(x,y),\quad y>0,\qquad S=x^2+y^2. \end{gathered} $$
外心の座標は、
$$ \begin{aligned} O_1&=\left(-\frac{3}{2},\frac{S+3x}{2y}\right),\\ O_2&=\left(2,\frac{S-4x}{2y}\right),\\ O&=\left(\frac{1}{2},\frac{S-x-12}{2y}\right). \end{aligned} $$
外心の一致から、
$$ OD^2=OO_1^2=OO_2^2. $$
これを整理すると、
$$ \begin{cases} S^2-2Sx-39S-72x=0,\\ S^2-2Sx-32S+96x=0. \end{cases} $$
差をとり、さらに代入すると、
$$ S=-24x,\qquad48x(13x+18)=0. $$
ここでSは正なので、
$$ \begin{aligned} x&=-\frac{18}{13},\\ S&=\frac{432}{13},\\ y^2&=\frac{5292}{169}. \end{aligned} $$
また、
$$ O_1O_2=\frac{7\sqrt{S}}{2y} $$
であり、AとDは直線O₁O₂に関して対称である。したがって、
$$ \frac{[AO_1O_2]}{[ABC]} =\frac{S}{4y^2}=\frac{13}{49}. $$
初等幾何は角の構造が見える点、座標解法は位置関係を代数計算に帰着できる点に利点がある。


第8問|2階差分と上界の構成

答え
$$ \boxed{\frac{166}{15}} $$

着想

階差を次のように置けば、条件は各2階差分の絶対値が1以下であることになる。
$$ y_i=x_{i+1}-x_i,\qquad d_i=y_i-y_{i-1},\qquad |d_i|\le1. $$
目的の差を2階差分の線形結合に表して評価する。

解答

添字を15周期で考えると、
$$ \sum_{i=1}^{15}y_i=0, \qquad x_5-x_1=\sum_{i=1}^{4}y_i. $$
係数を、
$$ \lambda_i-\lambda_{i+1} =\begin{cases} 11&(1\le i\le4),\\ -4&(5\le i\le15), \end{cases} \qquad\lambda_{16}=\lambda_1 $$
となるように選ぶと、巡回する和の移項より、
$$ \begin{aligned} \sum_{i=1}^{15}\lambda_i d_i &=\sum_{i=1}^{15}(\lambda_i-\lambda_{i+1})y_i\\ &=11\sum_{i=1}^{4}y_i-4\sum_{i=5}^{15}y_i\\ &=15(x_5-x_1). \end{aligned} $$
2階差分の総和は0なので、係数に共通の定数を加えても等式は変わらない。絶対値の和が最小になるように選ぶと、
$$ \begin{aligned} (\lambda_1,\ldots,\lambda_{15}) ={}&(22,11,0,-11,-22,-18,-14,-10,\\ &\quad-6,-2,2,6,10,14,18). \end{aligned} $$
この15数は0を中心に正負対称であるから、共通定数を0とするのが最適であり、
$$ \sum_{i=1}^{15}|\lambda_i|=166. $$
よって、
$$ 15x_5 =\sum_{i=1}^{15}\lambda_i d_i \le\sum_{i=1}^{15}|\lambda_i||d_i| \le166. $$
等号成立例として、
$$ \begin{aligned} (x_1,\ldots,x_{15}) =\frac{1}{15}(&0,34,83,132,166,185,189,178,\\ &152,111,55,14,-12,-23,-19) \end{aligned} $$
をとると、2階差分は、
$$ (d_1,\ldots,d_{15}) =(1,1,0,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1) $$
となり、全条件を満たす。さらに、
$$ x_5=\frac{166}{15} $$
なので、最大値は、
$$ \boxed{\frac{166}{15}}. $$
背景: 制約された量の線形結合として目的量を表す評価は、線形最適化の双対的な考え方につながる。


第9問|4進法と指数の表現

答え
$$ \boxed{2^{64}3^{16}5^4\cdot7} $$

着想

「単純な整数」は、どの素因数の指数も3以下の整数である。整数を3つの単純な整数の累乗の積で表せる条件は、各素因数の指数が共通の3つの正整数を用いて
$$ e=\alpha s+\beta t+\gamma u, \qquad \alpha,\beta,\gamma\in\{0,1,2,3\} $$
と表せることに等しい。係数が0〜3なので4進法が自然に現れる。

解答

素因数の正の指数を大きい順に次のようにおく。
$$ e_1\ge e_2\ge e_3\ge\cdots $$
次の場合には、与えられた形に必ず表せる。
$$ \begin{array}{c|l} \text{指数の条件}&\text{指数の選び方}\\\hline e_1\le63&(s,t,u)=(1,4,16)\\ e_2\le15&\text{最大指数だけ別枠、残りを1,4で表す}\\ e_3\le3&\text{最大2指数だけ別枠、残りを指数1にまとめる} \end{array} $$
また、素因数が3種類以下なら、各素数を別々の単純な整数に割り当てて表せる。したがって、表せないためには少なくとも4種類の素因数があり、
$$ e_1\ge64,\quad e_2\ge16, \quad e_3\ge4,\quad e_4\ge1 $$
が必要である。大きい指数を小さい素数に割り当てたとき積が最小となるから、
$$ n\ge N:=2^{64}3^{16}5^4\cdot7. $$
実際、次の関係が成り立つ。
$$ p< q,\ r>s\quad\Longrightarrow\quad p^rq^s< p^sq^r. $$
最後にNが表せないことを示す。仮に、
$$ N=a^sb^tc^u,\qquad s\le t\le u $$
と表せたとする。
指数1を表すには最小の指数が1でなければならず、指数4を表すには2番目の指数が4以下でなければならない。さらに指数16を表すには、3番目の指数が16以下でなければならない。すなわち、
$$ s=1,\qquad t\le4,\qquad u\le16 $$
が必要である。しかし係数0〜3で表せる指数の最大値は、
$$ 3(s+t+u)\le3(1+4+16)=63 $$
であり、指数64を表せない。矛盾する。ゆえに、
$$ \boxed{N=2^{64}3^{16}5^4\cdot7}. $$
背景: 係数0〜最大値までの数で整数を表す場面では、位取り記数法が自然な道具となる。


第10問|循環2進小数と繰り上がり

答え
$$ \boxed{2100} $$

着想

分母の形
$$ 2^7-1,\qquad 2^9-1 $$
から、2数はそれぞれ周期7、周期9の循環2進小数である。周期は互いに素なので、63桁を1周期として扱う。

解答

整数をそれぞれ7桁、9桁の2進表示で表し、1の個数をA、Bとする。問題の範囲では、どちらの循環列にも0と1が少なくとも1個ずつある。
63桁では7桁の列が9回、9桁の列が7回現れるので、
$$ s(a)=\frac{A}{7},\qquad s(b)=\frac{B}{9}. $$
和の小数部分の63桁に含まれる1の個数をHとすると、
$$ s(a+b)=\frac{H}{63}. $$
したがって求める条件は、
$$ H=AB.\tag{1} $$
63桁で加算するときの繰り上がりと桁を、次のようにおく。
$$ c_i\in\{0,1\},\qquad X_i,\ Y_i,\ Z_i\in\{0,1\}. $$
添字を63周期で考えると、2進法の加法から、
$$ X_i+Y_i+c_{i+1}=Z_i+2c_i. $$
全桁について足し合わせると、
$$ H=9A+7B-K,\qquad K=\sum_{i=1}^{63}c_i. $$
一方、周期7と周期9は互いに素なので、位置の組合せ
$$ (i\bmod7,\ i\bmod9) $$
は63桁で一度ずつ現れる。したがって00の位置は
$$ (7-A)(9-B) $$
個であり、そこでは繰り上がりが0となる。よって、
$$ \begin{aligned} K&\le63-(7-A)(9-B)\\ &\Longrightarrow\quad H\ge AB. \end{aligned} $$
等号が成立するのは、00の位置以外ではすべて繰り上がる場合に限る。桁の規則は次の通り。
$$ \begin{array}{c|c} \text{桁の組}&\text{繰り上がり}\\\hline 00&0\\ 01,10&\text{隣の下位桁から伝播}\\ 11&1 \end{array} $$
2つの循環列に隣り合う0がなければ、各00のすぐ下位側の桁は11になる。したがって、その間の01、10の位置にも繰り上がりが伝わり、00以外ではすべて1となる。
逆に、一方の列に連続する00があれば、他方の列には0と1がともに含まれるので、01または10の遷移がある。互いに素な周期7と9を利用して、00のすぐ上位側に01または10が来る位置を揃えられる。その位置には繰り上がりが生じず、等号は成立しない。
ゆえに (1) の必要十分条件は、両方の循環列で0が隣り合わないことである。
長さがrの円周上で、0をk個、隣り合わせずに置く方法は、
$$ \frac{r}{r-k}\binom{r-k}{k} $$
通りである。これを適用すると、

0の個数7桁9桁
179
21427
3730
4—9
計2875

となる。したがって、
$$ \boxed{28\cdot75=2100}. $$
背景: 周期7と9の位置の組合せが63桁でちょうど1回ずつ現れる性質は、中国剰余定理の具体例である。


第11問|角の二等分線と座標

答え
$$ \boxed{\frac{49\sqrt{30}}{60}} $$

着想

線分BDが角ABEの二等分線になる。まず面積条件からDEを決め、残る角条件を座標と内積・外積で処理する。

解答

次のようにおく。
$$ AD=L,\qquad DE=e. $$
角の二等分線の定理より、
$$ \frac{AB}{BE}=\frac{L}{e}.\tag{1} $$
点QはBEを3:1に外分するから、
$$ BQ=\frac{3}{2}BE. $$
面積条件から、
$$ \begin{aligned} \frac{3}{L} &=\frac{[BQC]}{[ABC]}\\ &=\frac{BQ}{AB} =\frac{3BE}{2AB} =\frac{3e}{2L}. \end{aligned} $$
したがって、
$$ \boxed{DE=2}. $$
次の座標を設定する。
$$ \begin{gathered} BD=b,\quad D=(0,0),\quad B=(-b,0),\\ C=(5b,0),\quad E=(u,v),\quad v<0. \end{gathered} $$
条件から、
$$ u^2+v^2=4. $$
また、A、D、Eはこの順に一直線上に並ぶので、
$$ A=-\frac{L}{2}(u,v),\qquad P=-\frac{L-3}{2}(u,v). $$
(1) より、
$$ AB=\frac{L}{2}BE. $$
両辺を2乗すると、
$$ b^2-bLu+L^2 =\frac{L^2}{4}(b^2+2bu+4) $$
となる。正の長さに注意して整理すると、
$$ 2Lu=b(2-L).\tag{2} $$
次に、点Fを次で定める。
$$ F=(3b,0). $$
外分比より、
$$ CQ\parallel FE $$
であるから、問題の角条件は、
$$ \angle ACP=\angle DFE $$
となる。ここで、
$$ \begin{aligned} \vec{CA}&=\left(-5b-\frac{Lu}{2},-\frac{Lv}{2}\right),\\ \vec{CP}&=\left(-5b-\frac{(L-3)u}{2},-\frac{(L-3)v}{2}\right). \end{aligned} $$
これらの内積は、
$$ \vec{CA}\cdot\vec{CP} =25b^2+\frac{5b}{2}(2L-3)u+L(L-3) $$
であり、外積の大きさは、
$$ \frac{15b}{2}|v| $$
となる。したがって、
$$ \cot\angle ACP =\frac{25b^2+\frac{5b}{2}(2L-3)u+L(L-3)} {\frac{15b}{2}|v|}. $$
一方、
$$ \cot\angle DFE=\frac{3b-u}{|v|}. $$
両角が等しいことから、
$$ 5b^2+10bLu+2L(L-3)=0. $$
(2) を代入して、
$$ (L-3)(2L-5b^2)=0. $$
点Pは線分ADの端点ではないので、
$$ L>3,\qquad 5b^2=2L.\tag{3} $$
また、
$$ \begin{aligned} 49&=(5b-u)^2+v^2\\ &=25b^2-10bu+4. \end{aligned} $$
(2)、(3) より、
$$ b^2=\frac{2L}{5},\qquad bu=\frac{2-L}{5}. $$
したがって、
$$ 49=12L,\qquad L=\frac{49}{12}. $$
最後に角の二等分線の長さの公式
$$ BD^2=AB\cdot BE-AD\cdot DE $$
を用いる。(1)、(3) より、
$$ \frac{2L}{5}=\frac{L}{2}BE^2-2L \quad\Longrightarrow\quad BE^2=\frac{24}{5}. $$
したがって、
$$ \begin{aligned} AB&=\frac{L}{2}BE =\frac{49}{24}\sqrt{\frac{24}{5}}\\ &=\boxed{\frac{49\sqrt{30}}{60}}. \end{aligned} $$
背景: 角の二等分線の長さの公式は、角の二等分線の定理とStewartの定理から導ける。


第12問|最短路・2色分割・木

答え
$$ \boxed{28004025} $$

着想

各橋の料金を直接扱わず、島ごとに始点からの最小通行料を割り当てる。元の格子距離を差し引くと値域が0〜27に収まり、これを27個の2色分割に分解できる。

1. 最短路を高さに置き換える

始点と終点を次のようにおく。
$$ S=(0,0),\qquad T=(1000,1000). $$
始点から島vまでの最小通行料をd(v)とする。すべての橋が通行料2027の最短路に属するから、各橋の通行料は、
$$ w(uv)=|d(u)-d(v)|.\tag{1} $$
各島の最短移動本数と、そこから終点までの最短移動本数は、それぞれ次の通りである。
$$ i+j,\qquad 2000-i-j. $$
どの島も通行料2027の最短路に属するので、
$$ i+j\le d(i,j)\le i+j+27. $$
そこで、
$$ h(i,j):=d(i,j)-i-j $$
とおくと、
$$ 0\le h(i,j)\le27.\tag{2} $$
また最短路に沿ってdは1本ごとに少なくとも1増え、格子座標の和は高々1増えるから、hは減少しない。

2. 27個の2色分割

次の整数と0・1変数を考える。
$$ k=0,1,\ldots,26, \qquad b_k(i,j)= \begin{cases} 0&h(i,j)\le k,\\ 1&h(i,j)>k. \end{cases} $$
このとき、
$$ h(i,j)=\sum_{k=0}^{26}b_k(i,j). $$
さらに、
$$ H_k(i,j)=i+j+27b_k(i,j) $$
と定めれば、
$$ d(i,j)=\frac{1}{27}\sum_{k=0}^{26}H_k(i,j). $$
三角不等式から、全橋の通行料総和をW、各Hₖの隣接差の総和をWₖとして、
$$ \boxed{W\le\frac{1}{27}\sum_{k=0}^{26}W_k}.\tag{3} $$
つまり、連結な2色配置に対する上限を示せば十分である。

3. 境界の本数

次の集合を考える。
$$ X=\{(i,j):b_k(i,j)=0\}, \qquad Y=\{(i,j):b_k(i,j)=1\}. $$
最短路上でhが減少しないため、Xは始点側で、Yは終点側でそれぞれ連結である。
格子全体の島と橋の本数は、
$$ V=1001^2,\qquad E=2\cdot1000\cdot1001. $$
異色の島を結ぶ橋の本数をC、Xの島数をmとすると、各色の内部には少なくとも次の本数の橋が必要である。
$$ m-1,\qquad (V-m)-1. $$
したがって、
$$ \begin{aligned} C&\le E-(m-1)-(V-m-1)\\ &=E-V+2=1\,000\,001. \end{aligned}\tag{4} $$
次に、右向き・上向きに見て、0から1へ移る橋をP本、1から0へ移る橋をQ本とし、
$$ C=P+Q,\qquad F=P-Q $$
とおく。行と列の0・1の差を足すと途中が消え、
$$ \begin{aligned} F={}&\sum_{j=0}^{1000} \bigl(b_k(1000,j)-b_k(0,j)\bigr)\\ &+\sum_{i=0}^{1000} \bigl(b_k(i,1000)-b_k(i,0)\bigr). \end{aligned} $$
始点は0、終点は1だから、四隅の寄与は2、残りは高々2(1000−1)。したがって、
$$ F\le2000.\tag{5} $$
さらに、
$$ C-F=2Q \quad\Longrightarrow\quad C\equiv F\pmod2. $$
Cの上限は奇数、Fの上限は偶数だから、(4)、(5) の等号は同時に成立しない。整数性から、
$$ \begin{aligned} 26C+F &\le26\cdot1\,000\,001+2000-1\\ &=26\,002\,025. \end{aligned}\tag{6} $$

4. 通行料の上界

2色配置に対する仮の高さは、
$$ H_k(i,j)=i+j+27b_k(i,j). $$
右向き・上向きの橋の通行料は次のようになる。
$$ \begin{array}{c|ccc} \text{色の変化}&0\to0,\ 1\to1&0\to1&1\to0\\\hline \text{通行料}&1&28&26 \end{array} $$
したがって、
$$ \begin{aligned} W_k&=E+27P+25Q\\ &=E+26(P+Q)+(P-Q)\\ &=E+26C+F\le28\,004\,025. \end{aligned} $$
(3) より、
$$ W\le28\,004\,025.\tag{7} $$

5. 上界を実現する2色配置

各島に0または1を割り当てる。
$$ b(i,j)\in\{0,1\}. $$

  • 第0行:すべて0。
  • 第1行:左から0、1、0、1、……と交互。
  • 第2行以降の偶数行:左端のみ0、他は1。
  • 第3行以降の奇数行:右端のみ1、他は0。
    横幅6に縮小した模式図を示す。
    $$ \begin{array}{c|ccccccc} j\backslash i&0&1&2&3&4&5&6\\\hline 6&0&1&1&1&1&1&1\\ 5&0&0&0&0&0&0&1\\ 4&0&1&1&1&1&1&1\\ 3&0&0&0&0&0&0&1\\ 2&0&1&1&1&1&1&1\\ 1&0&1&0&1&0&1&0\\ 0&0&0&0&0&0&0 \end{array} $$
    0の領域は左端と下端を幹として奇数行の枝と第1行の葉が付いた木、1の領域は右端を幹として偶数行の枝と第1行の葉が付いた木になる。いずれも連結かつ閉路をもたないので、内部の橋は合計でV−2本。よって、
    $$ C=E-V+2=1\,000\,001. $$
    また、右端の1が999個、上端の1が1000個で、左端・下端はすべて0だから、
    $$ F=999+1000=1999. $$
    そこで高さと通行料を次のように定める。
    $$ H(i,j)=i+j+27b(i,j),\qquad w(uv)=|H(u)-H(v)|. $$
    すると、
    $$ \begin{aligned} W&=E+26C+F\\ &=2\,002\,000+26\cdot1\,000\,001+1999\\ &=28\,004\,025. \end{aligned} $$
    最後に問題の条件を確認する。0の島は始点以外なら左または下の0の島へ進め、1の島は終点以外なら右または上の1の島へ進める。よってどの橋も高さHが狭義増加する始点から終点への経路に含まれ、その通行料は、
    $$ H(T)-H(S)=2027. $$
    他方、任意の経路の通行料は三角不等式により2027以上である。したがって問題の条件を満たし、(7) の上界が達成される。
    $$ \boxed{28\,004\,025}. $$

背景|カットと全域木

任意の有限グラフの頂点集合を、どちらも連結な2つの非空集合へ分けると、各集合の内部に必要な辺は合計で頂点数より2少ない本数以上である。したがって両者の境界(カット)の辺数は、
$$ |\delta(X)|\le |E|-|V|+2. $$
等号は、両側の内部の辺がそれぞれ木になる場合に限る。本問の上限と達成例はこの補題を利用している。


解法一覧表

問中心となる発想
1積の不変量
2面積の線形性
3指数の偶奇を4状態に還元
4符号付き和と2進法
5約数関数の乗法性
6ガウス記号の階差
7外心・相似(座標解法も併記)
82階差分の線形結合
94進法による指数の表現
10循環2進法と繰り上がり
11角の二等分線と座標
12最短路と連結な2色領域
投稿日:2日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

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

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

バッジはありません。

投稿者

H・I
H・I
22
4592

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中