答え
$$
\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}
$$
とすれば成立する。
要点: 個々の実数ではなく、組にした積を不変量として使う。
答え
$$
\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.
$$
両解法の核は同じ面積の線形性である。前者は内分比、後者は面積の加減で処理する。
答え
$$
\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状態に圧縮する発想は、有限状態の漸化式や合同式の問題にも応用できる。
答え
$$
\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}.
$$
答え
$$
\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)
$$
を利用している。
答え
$$
\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}
$$
要点: ガウス記号を含む和は、値が変化する位置に注目すると簡単になる場合がある。
答え
$$
\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}.
$$
初等幾何は角の構造が見える点、座標解法は位置関係を代数計算に帰着できる点に利点がある。
答え
$$
\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}}.
$$
背景: 制約された量の線形結合として目的量を表す評価は、線形最適化の双対的な考え方につながる。
答え
$$
\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〜最大値までの数で整数を表す場面では、位取り記数法が自然な道具となる。
答え
$$
\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桁 |
|---|---|---|
| 1 | 7 | 9 |
| 2 | 14 | 27 |
| 3 | 7 | 30 |
| 4 | — | 9 |
| 計 | 28 | 75 |
となる。したがって、
$$
\boxed{28\cdot75=2100}.
$$
背景: 周期7と9の位置の組合せが63桁でちょうど1回ずつ現れる性質は、中国剰余定理の具体例である。
答え
$$
\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の定理から導ける。
答え
$$
\boxed{28004025}
$$
各橋の料金を直接扱わず、島ごとに始点からの最小通行料を割り当てる。元の格子距離を差し引くと値域が0〜27に収まり、これを27個の2色分割に分解できる。
始点と終点を次のようにおく。
$$
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は減少しない。
次の整数と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色配置に対する上限を示せば十分である。
次の集合を考える。
$$
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}
$$
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}
$$
各島に0または1を割り当てる。
$$
b(i,j)\in\{0,1\}.
$$
任意の有限グラフの頂点集合を、どちらも連結な2つの非空集合へ分けると、各集合の内部に必要な辺は合計で頂点数より2少ない本数以上である。したがって両者の境界(カット)の辺数は、
$$
|\delta(X)|\le |E|-|V|+2.
$$
等号は、両側の内部の辺がそれぞれ木になる場合に限る。本問の上限と達成例はこの補題を利用している。
| 問 | 中心となる発想 |
|---|---|
| 1 | 積の不変量 |
| 2 | 面積の線形性 |
| 3 | 指数の偶奇を4状態に還元 |
| 4 | 符号付き和と2進法 |
| 5 | 約数関数の乗法性 |
| 6 | ガウス記号の階差 |
| 7 | 外心・相似(座標解法も併記) |
| 8 | 2階差分の線形結合 |
| 9 | 4進法による指数の表現 |
| 10 | 循環2進法と繰り上がり |
| 11 | 角の二等分線と座標 |
| 12 | 最短路と連結な2色領域 |