問題

2018 年 9 月 22, 23 日時間無制限 12 題

5 番以降は証明問題です. 答を出す問題であっても必ず証明をつけてください.
一問でも解けたら採点係のところまで持ってきてください. 採点は何度でも可能です.
殿堂入りを目指して頑張ってください.

1

次の虫食い算を解け.

(1)

$$\def\arraystretch{1.5} \begin{array}{cccccccc} &&&&\square&\square&\square&\square\\ &\times &&&\square&\square&2&\square\\ \hline &&&\square&8&0&\square&\square\\ &&\square&\square&1&\square&\square&\\ &\square&\square&8&0&\square&&\\ \square&\square&\square&\square&2&&&\\ \hline \square&\square&\square&\square&\square&\square&\square&\square \end{array}$$

(2)

$$\def\arraystretch{1.5} \begin{array}{cccccccc} &&&&\square&\square&\square&\square\\ &\times&&&\square&\square&\square&\square\\ \hline &&&\square&8&8&\square&\square\\ &&\square&\square&1&\square&\square&\\ &\square&\square&0&0&\square&&\\ \square&\square&2&\square&2&&&\\ \hline \square&\square&\square&\square&\square&\square&\square&\square \end{array}$$

2

$2018$ は各桁の和が $11$, 積が $0$ である. このように各桁の和と積の差が $11$ であるような 4 桁の整数はいくつあるか.

3

四角形 $ABCD$ は, $\angle{ABD}=\angle{CBD}=24\degree$, $\angle{ACB}=9\degree$, $\angle{DCA}=54\degree$ をみたす. このとき, $\angle{ADB}$ の大きさを求めよ.

4

左右に 3 列, 上下に 15 段に, 合計 45 個のブロックが積み上げられている. それぞれのブロックは黒または白で塗られている. 1 秒経つと, 「同じ色が 3 つ以上つながっている部分」がすべて消え, その後下に落ちる.「ブロックが消え, 落ちる」ことが $X$ 回行われるブロックの組み合わせを「$X$ コンボである」とする.

(1)

$0$ コンボであるようなブロックの塗り方はいくつあるか.

(2)

$15$ コンボであるようなブロックの塗り方はいくつあるか.

5

$n$ を正整数, $d(n)$ を $n$ の正の約数の個数とする. $d(n^3)=n$ を満たすような $n$ を全て求めよ.

6

鋭角三角形 $ABC$ において, 垂心を $H$ とし, $A$, $B$, $C$ から対辺におろした垂線の足を $D$, $E$, $F$ とする. また直線 $DE$ 上に $ED=DP$ なる $E$ でない点 $P$ をとる. $HE+HC=PC$ をみたすとき, $FP\perp BC$ であることを示せ.

7

$abc=1$ を満たす任意の正の実数 $a$, $b$, $c$ に対して $$ab^n+bc^n+ca^n \geq a+b+c$$ が成り立つような正整数 $n$ を全て求めよ.

8

$m$, $n$ を正整数, $c$ は $1$ 以上の実数とする. あなたは軍の指導者であり, 最初の武力は $1$ である. あなたの軍は, 武力が $c^0,c^1,c^2,c^3,\dots,c^{n-1}$ の武士が $m$ 人ずつの合計 $mn$ 人の武士と戦う. あなたの軍が武力 $x$ であるときに武力 $y$ の武士と戦うとき, $x\geq y$ であればこの武士に勝つことができる。これに勝つと, この武士があなたの軍に加わり, あなたの軍の武力が $x+y$ となる.

同じ武力の武士を区別せず, 違う武力の武士を区別するとき, 次の (1) から (3) それぞれの条件を満たすような $c$ の範囲を求めよ.

(1)

$m=10$, 任意の正整数 $n$ に対して全員の武士に勝つことができる.

(2)

$m=1$, 全員の武士に勝つ方法が複数あるような $n$ が存在する.

(3)

$m=10$, 全員の武士に勝つ方法が複数あるような $n$ が存在する.

9

$\phi=\dfrac{1+\sqrt{5}}{2}$ とする. 任意の正整数 $n$ に対し, $$[[n\phi]\phi]=[n\phi^2]-1$$ であることを示せ.

10

$N$ を $3$ 以上の整数とする. GP 国には $N$ 個の郵便ポストが一列に並んでいる. 最初, 各郵便ポストには $1$ つの手紙があり, 左から $i$ 番目の郵便ポストにある手紙を左から $p_i$ 番目のポストに届けたい. ただし $p_1,p_2,\dots,p_N$ は $1,2,\dots,N$ の並び替えである.

さとし君は次のプラン A またはプラン B のどちらかを選び, 最後まで変更してはならない:

プラン A：左から $i$ 番目の郵便ポストにある手紙と左から $j$ 番目にある郵便ポストにある手紙を交換し, $2\lvert i-j\rvert+1$ 円を払う.
プラン B：左から $i$ 番目の郵便ポストの中で一番上にある手紙を $i\geq2$ のとき左から $i-1$ 番目, もしくは $i\leq n-1$ のとき $i+1$ 番目のどちらかの郵便ポストを選び, 選んだ郵便ポストの一番上に手紙を積み, $1$ 円を払う.

$S=\lvert p_1-1\rvert+\lvert p_2-2\rvert+\cdots+\lvert p_N-N\rvert$ とする. どのような $p_1,p_2,\dots,p_N$ の組み合わせに対しても, うまくプランを選ぶことでさとし君はすべての手紙を目的の場所に届けるのにかかる金額を $S+\dfrac{2}{3}N$ 円以下にできることを示せ.

11

$(a+bi)^n$ を整数にする正整数 $n$ が存在するような整数 $a$, $b$ を全て求めよ.

12

$AB\neq AC$ なる鋭角三角形 $ABC$ において, 垂心を $H$, 辺 $BC$ の中点を $M$, $A$ から $BC$ におろした垂線の足を $D$, $AH$ を直径とする円と三角形 $ABC$ の外接円との交点のうち $A$ でない方を $X$, $H$ を通り $BC$ に平行な直線と辺 $AB$, $AC$ との交点を $P$, $Q$ とする. 三角形 $XPQ$ の外接円の $X$ における接線と直線 $BC$ との交点を $Y$ とするとき, 三角形 $XYD$ の外接円は線分 $AM$ の中点を通ることを示せ.

解答

1

(1)

$$\def\arraystretch{1.5} \begin{array}{cccccccc} &&&&7&5&6&1\\ &\times&&&2&5&2&9\\ \hline &&&6&8&0&4&9\\ &&1&5&1&2&2&\\ &3&7&8&0&5&&\\ 1&5&1&2&2&&&\\ \hline 1&9&1&2&1&7&6&9 \end{array}$$

(2)

$$\def\arraystretch{1.5} \begin{array}{cccccccc} &&&&9&6&2&6\\ &\times&&&2&8&5&3\\ \hline &&&2&8&8&7&8\\ &&4&8&1&3&0&\\ &7&7&0&0&8&&\\ 1&9&2&5&2&&&\\ \hline 2&7&4&6&2&9&7&8 \end{array}$$

2

(i) 位に $0$ が含まれるとき

$a+b+c=11$, $1\leq a,b,c\leq9$ の整数解は $45$ 個, $a+b=11$, $1\leq a,b\leq9$ の整数解は $8$ 個であるから, $0$ がある位で場合分けすることで, $45\times3+8\times3=159$ 個.

(ii) 位に $0$ が含まれないとき

$a+b+c+d-abcd=\pm11$. $a$, $b$, $c$, $d$ に含まれる $1$ の個数で場合分けする.

(ア) $1$ が $3$ 個以上含まれるとき

解なし

(イ) $1$ が $2$ 個含まれるとき

$a=b=1$ とすると $c+d+2-cd=\pm11$. $\therefore (c-1)(d-1)=-8,14$. $\therefore (c,d)=(3,8),(8,3)$. よって, $(a,b,c,d)$ は $1$, $1$, $3$, $8$ の並び替えであり, $12$ 個.

(ウ) $1$ が $1$ 個含まれるとき

$a=1$ とすると $b+c+d+3-bcd=\pm11$. $\therefore \dfrac{1}{cd}+\dfrac{1}{db}+\dfrac{1}{bc}=1+\dfrac{8}{bcd}$ または $\dfrac{1}{cd}+\dfrac{1}{db}+\dfrac{1}{bc}+\dfrac{14}{bcd}=1$. 前者は左辺 $\leq\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{4}=\dfrac{3}{4}$ より不適. 後者は $b$, $c$, $d$ がすべて $3$ 以上とすると $(\text{左辺})\leq\dfrac{23}{27}$ となり解なしであるから, いずれかは $2$. $b=2$ とすると $2cd-c-d=14$ より $(2c-1)(2d-1)=29$ となるが, 解なし.

(エ) $1$ が含まれないとき

同様にして解なしが示せる.

以上より, 求める個数は $159+12=\boxed{171\text{ 個}}$.

3

三角形 $ACE$ が正三角形になるように直線 $AC$ に対して $B$ と同じ側に $E$ をとり, $BC$ の垂直二等分線と直線 $DC$ の交点を $F$ とすると, ($EC$ の中点を $M$ とすると, $\angle{AMC}+\angle{DCM}>180\degree$ より, $F$ は線分 $DC$ の $C$ 側の延長に存在する) $\angle{ECF}=\angle{FEC}=66\degree$, $\angle{EFA}=\angle{CFA}=24\degree$. ここで $\angle{ABD}=\angle{AFD}=24\degree$ より円周角の定理の逆から $ABFD$ 共円. よって円周角の定理より $\angle{BAF}=\angle{BDF}=93\degree$. ここで直線 $AB$ と直線 $EF$ の交点を $G$ とすると, $\angle{GEA}=54\degree$, $\angle{BAG}=63\degree$ より $\angle{BGA}=63\degree$ であるから, $EA=EG$. また $\angle{GBC}+\angle{GFC}=180\degree$ より内接四角形定理の逆から $BGFC$ 共円. よって円周角の定理より $\angle{GFB}=\angle{GCB}=51\degree-\angle{GCB}=18\degree$. 円周角の定理より $\angle{ADB}=\angle{AFB}=\boxed{6\degree}$.

4

(1)

$0$ コンボであるとは, 「同じ色でつながっているブロックの個数がどのつながりに対しても 1 個または 2 個である」ことと同値である. 一番下の段の 3 つのブロックについて考える. まず, この 3 つのブロックが「全部黒」「全部白」の時, 同じ色のつながりが 3 つ以上のブロックで構成されるものがあり, $0$ コンボではなくなる. 次に, 一番下の段が「黒黒白」と並べられている場合を考える. このとき, 下から 2 段目は「白白黒」でなければならない. 一番下の段の 3 つのブロックが「白白黒」「黒白白」「白黒黒」である場合も同様に, 一つ上の段がその段とは違う色である場合以外ありえない. また, 下から 3 番目, 下から 4 番目, …, 一番上の段も同様にすると 1 つに定まる. したがって, このケースは一番下の段の場合の数と同じ 4 通りである。最後に, 一番下の段が「白黒白」 (これを$A$とする) または「黒白黒」 (これを $B$ とする) と並べられている場合を考える. この場合, 下から 2 段目のブロックも $A$ または $B$ になる. 同様に考えると, どの段も $A$ または $B$ でなければならない. $A$ または $B$ が 3 個以上連続でつながってはいけないため, このケースの場合の数は「$A$ と $B$ で構成される $15$ 文字の文章で, $AAA$ と $BBB$ が含まれないもの」の個数と同じである. 具体的には, $1$ 文字の場合 $2$ 通り, $2$ 文字の場合 $4$ 通りで, $X$ 文字 ($X\geq3$) の場合は $\text{($X-1$ 文字の場合の通り数)}+\text{($X-2$ 文字の場合の通り数)}$ と表せる. ちなみにこれはフィボナッチ数列 $1, 2, 3, 5, 8, 13, \dots$ の $2$ 倍と等しい. このように計算していくと, $1974$ 通りが得られる. したがって, 求める場合の数は $4+1974=\boxed{1978\text{ 通り}}$.

(2)

$15$ コンボするためには, 15 回にわたって「ちょうど 3 つのブロックで構成された同じ色のつながり」が 1 つずつ消えていかなければならない. この条件を踏まえて, 最初に消えるブロックのつながりを考える. 最初に消えるブロックを白色としても, 一般性を失わない. まず, 最初に消えるブロックが「縦 3 つが白色」の場合, この横のブロックが全部黒色でない限りは一気に 4 つ以上の白いブロックが消えることになり, 15 コンボは達成できない. 次に, 消えるブロックが「横 3 つが白色」の場合, 先ほどの場合と同様に, 1 つ上または 1 つ下の段が全部黒色ではない場合白ブロックが一気に 4 つ以上消えることになるが, そうでない場合白ブロック 3 つと黒ブロック 3 つが同時に消えることになり, いずれにしろ $15$ コンボは達成できない. 残ったパターンは消えるブロックが L 型か Γ 型 (左右反転は考えなくても一般性を失わない) の場合である. Γ 型の場合, 一番上の段が消えるのであればここでコンボが終了する. 一番上の段以外が消える場合は次に (Γ の周りの) 4 つ以上の黒色つながりが消えることになる. L 型の場合, 一番下の段が消えるのであれば次の回で横 3 つが消え, その時点で $15$ コンボ達成が不可能になる. そうでない場合は右図のようになり, 4 つ以上のつながりが消えることになる. したがって, どの場合でも $15$ コンボ達成はできない. したがって, $15$ コンボであるような場合の数は $\boxed{0\text{ 通り}}$.

5

$n=1$ のときは明らかに成り立つので, 以下 $n\geq2$ のときについて考える. $n=a_1^{b_1}a_2^{b_2}\cdots a_m^{b_m}$ ($a_1<a_2<\dots<a_m$ は素数, $b_i$ は正整数) とすると $$d(n^3)=(3b_1+1)(3b_2+1)\cdots(3b_m+1)$$ より $$(3b_1+1)(3b_2+1)…(3b_m+1)=a_1^{b_1}a_2^{b_2}\cdots a_m^{b_m}\cdots(☆).$$ 左辺は $3$ で割り切れないので, $a_i$ に $3$ は含まれないことに注意する. $$(☆)\iff\dfrac{3b_1+1}{a_1^{b_1}}=\dfrac{a_2^{b_2}}{3b_2+1}\dfrac{a_3^{b_3}}{3b_3+1}\cdots\dfrac{a_m^{b_m}}{3b_m+1}\cdots(★).$$

(補題) $i\geq2$ において $a_i^{b_i}>3b_i+1$

(証明) $a_i\geq5$ より $a_i^{b_i}>4^{b_i}=(3+1)^{b_i}\geq3b_i+1$ ($\because$ 二項定理)

$a_1>2$ とすると, $a_1\geq5$ であるから, 補題より (★) において $(左辺)<1<(右辺)$ となり解なし. よって $a_i=2$ である. このとき補題より (★) の右辺は $1$ より大きい. よって $2^{b_1}>3b_1+1 \iff b_1=1, 2, 3$.

(i) $b_1=1$ のとき

(☆) に代入：$4(3b_2+1)\cdots(3b_m+1)=2a_2^{b_2}\cdots a^m_{b_m}$. 左辺は $4$ の倍数だが右辺は $4$ の倍数でないので解なし

(ii) $b_1=2$ のとき

$\dfrac{7}{4}=\dfrac{a_2^{b_2}}{3b_2+1}\dfrac{a_3^{b_3}}{3b_3+1}\cdots\dfrac{a_m^{b_m}}{3b_m+1}$. 補題より $\dfrac{a_i^{b_i}}{3b_i+1}\leq\dfrac{7}{4}$. これを満たす $(a_i, b_i)$ の組は $(5, 1)$, $(7, 1)$ のみであることに注意すると, $m=2$, $a_2=7$, $b_2=1$ のみが満たすことがわかり, このとき $n=28$

(iii) $b_i=3$ のとき

同様にすると, $m=2$, $a_2=5$, $b_2=1$ のみが満たすことがわかり, このとき $n=40$

以上より, $\boxed{n=1, 28, 40}$.

6

$FP$ と $BC$ の交点を $Q$, $HC$ の中点を $M$, $CE$ の中点を $N$ とする. $\triangle{HDC}$ は直角三角形なので $HM=MC=MD$ となり $2MD=HC$, 中点連結定理より $2HE=MN$, $HE\parallel MN$, $2DN=PC$, $DN\parallel PC$. $HE+HC=PC$ より $MD+MN=DN$ であるから, 三点 $D$, $M$, $N$ は一直線にあり, $HE\parallel DN\parallel PC$. よって $\triangle{EPC}$ は直角三角形になり $ED=DP=DC$, よって $\angle{DCP}=\angle{DPC}$. ところで円周角の定理より $\angle{BAD}=\angle{BED}=\angle{HCD}$. $HE\parallel DN\parallel PC$ なので $\angle{BAC}=\angle{EHC}=\angle{HCP}$. よって $\angle{DAC}=\angle{DCP}$. $\angle{DCP}=\angle{DPC}$ なので $2\angle{DAB}=\angle{BAC}$, また $\angle{DAB}=\angle{DAC}$ より $\triangle{DAC}$ と $\triangle{DAC}$ は合同で $AB=AC$. $\triangle{AHF}$ と $\triangle{AHE}$ も合同で $HE=HF$ となり $HE+HC=PC$ より $\triangle{CFP}$ は $CF=CP$ の二等辺三角形. $\angle{FCQ}=\angle{PCQ}$ と合わせて, $\triangle{FCQ}$ と $\triangle{PCQ}$ は合同. よって $FP$ は $BC$ と垂直に交わる.

7

$n=1$のとき

$(a, b, c)=\left(2, 1, \dfrac{1}{2}\right)$ などが反例として挙げられる.

$n=2$のとき

$ab^2+bc^2+ca^2=\left(\dfrac{2}{3}ab^2+\dfrac{1}{3}bc^2\right)+\left(\dfrac{2}{3}bc^2+\dfrac{1}{3}ca^2\right)+\left(\dfrac{2}{3}ca^2+\dfrac{1}{3}ab^2\right)\geq\sqrt[3]{a^2b^5c^2}+\sqrt[3]{a^2b^2c^5}+\sqrt[3]{a^5b^2c^2}=a+b+c$
よってこれは条件を満たす ($\geq$ の部分は相加相乗平均を用いた).

$n\geq3$のとき

$(ab^n+bc^n+ca^n)(c+a+b)(1+1+1)^{n-3}\geq(b+c+a)^{n-1}$ ($\because$ Cauchy-Schwarzの不等式)
$\therefore ab^n+bc^n+ca^2\geq\dfrac{(a+b+c)^{n-2}}{3^{n-3}}=(a+b+c)\left(\dfrac{a+b+c}{3}\right)^{n-3}\geq(a+b+c)(\sqrt[3]{abc})^{n-1}=a+b+c$
よってこれは条件を満たす (最後の $\geq$ の部分は相加相乗平均を用いた).

以上より求める答は $\boxed{\text{$n\geq2$ を満たす全ての整数}}$.

8

(1)

武力の小さい武士から対戦するときが最適な手法であることは明らかであるから, この方法で対戦することを考える. また, そのときに 1 つでも武力 $c^a$ の武士に勝つことができれば, 残り $m-1$ 人の武力 $c^a$ の武士に勝つことができることも明らかである. 最初の武力 $c^a$ の武士と対戦するとき, 現在の軍の武力がこれ以上である, つまり $1+m(c^0+c^1+c^2+\cdots+c^{a-1})\geq c^a$ でなければならない. $c=1$ のときは明らかに条件を満たす. $c\neq1$ のとき, $c^0+c^1+c^2+\cdots+c^{a-1}=\dfrac{c^a-1}{c-1}$ (等比数列の和の公式) を利用して不等式を解くと, $c\leq m+1$ が得られる. これはどの $a$ でも同じなので, $c\leq m+1$ のときのみ全員の武士に勝つ方法が存在する. したがって $\boxed{1\leq c\leq11}$.

(2)

整数 $a$ に対して武力 $c^a$ ($0\leq a<n$) の武士が 1 人ずついる. 武力 $c^{n-3}$ までの武士に勝利した後で, 武力 $c^{n-1}$ の武士に勝利できれば勝ち方は 2 通り以上存在する. つまり, $1+c^0+c^1+c^2+\cdots+c^{n-3}\geq c^{n-1} \iff 1+\dfrac{c^{n-2}-1}{c-1}\geq c^{n-1} \iff c^n-c^{n-1}-c^{n-2}\leq c-2 \iff c^2-c-1\leq(c-2)c^{-n+2}$. まず, $c>2$ の場合 (1) より明らかに条件を満たさず, $c=2$ の場合明らかに不等式を満たさず, $c=1$ のときは不等式を満たす. $1<c<2$ の場合を考える. $f(n)=(c-2)c^{-n+2}$ は単調増加関数であるから, $n$ が大きくなるほど $c^2-c-1$ の解の範囲も広がるため, $n$ を限りなく大きくした方がよいことがわかる. このとき右辺は $0$ に限りなく近い負の実数となることから, 先ほどの不等式は $c^2-c-1<0$ と書き換えられ, これを解くと$1<c<\dfrac{1+\sqrt{5}}{2}$ が得られる. したがって, $\boxed{1\leq c<\dfrac{1+\sqrt{5}}{2}}$.

(3)

(2) と同様にして解くことができる. 具体的には, 武力 $c^{n-3}$ までの武士すべてと武力 $c^{n-2}$ の武士を1つ残してすべて勝利した後に武力 $c^{n-1}$ の武士に勝利できれば勝ち方は 2 通り以上存在する. つまり, $1+10(c^0+c^1+c^2+\cdots+c^{n-2})-c^{n-2}\geq c^{n-1} \iff 1-c^{n-2}+10\dfrac{c^{n-1}-1}{c-1}\geq c^{n-1} \iff c^n-10c^{n-1}-c^{n-2}\leq c-11 \iff c^2-10c-1\leq(c-11)c^{-n+2}$. $c>11$ の場合 (1) より条件を満たさず, $c=11$ の場合明らかに不等式を満たさず, $c=1$ のとき明らかに不等式を満たすので, $1<c<11$ の場合を考える. $n$ を限りなく大きくした方がよく, このとき右辺は $0$ に限りなく近い負の実数となることから, 先ほどの不等式は $c^2-10c-1<0$ と書き換えられ, これを解くと $c<5+\sqrt{26}$ が得られる. したがって, $\boxed{1\leq c<5+\sqrt{26}}$.

9

(補題) レイリーの定理 $\dfrac{1}{r}+\dfrac{1}{s}=1$ を満たす正の無理数 $r$, $s$ に対して, 全ての整数は二つの数列 $\lbrace[mr]\rbrace$ ($m=1, 2, \dots$), $\lbrace[ns]\rbrace$ ($n=1, 2, \dots$) のいずれかに必ず一回だけ登場する.

(証明)

$N$ が両方の数列にあると仮定して矛盾を示す. ある正の整数 $m$, $n$ が存在して $N<mr<N+1$ かつ $N<ns<N+1$. 前者を $m$ でわって, 後者を $n$ で割って辺々加えると $N<m+n<N+1$ より矛盾.
$N$ がどちらの数列にも登場しないと仮定して矛盾を示す. ある正の整数 $m$, $n$ が存在して $mr<N$, $N+1<(m+1)r$, $ns<N$, $N+1<(n+1)s$. 1 と同様にして $m+n<N$, $m+n+2>N+1$ がわかり, $m+n<N<m+n+1$ となるがこれは矛盾.

よって示された.

$[[n\phi]\phi]\leq[n\phi\phi]=[n\phi^2]\leq[([n\phi]+1)\phi]$. また, $\phi^2=\dfrac{6+2\sqrt{5}}{4}=\dfrac{3+\sqrt{5}}{2}>\frac{3+1}{2}=2$ より $[(n-1)\phi^2]=[n\phi^2-\phi^2]\leq[n\phi^2-2]<[n\phi^2]-1$. ゆえに, $s=[n\phi^2]-1$ と置くと, $s$ は $[m\phi^2]$ ($m$ は自然数) とはかけない. また, $\dfrac{1}{\phi}+\dfrac{1}{\phi^2}=\dfrac{\phi+1}{\phi^2}=1$ とレイリーの定理より, $s=[r\phi]$ ($r$ は自然数) とかけ, また $[[n\phi]\phi]\neq[n\phi^2]$ となる。ここから, $[[n\phi]\phi]\leq[n\phi^2]-1$ となり, 一番上の結果も用いると, $[n\phi]\leq r<[n\phi]+1$ となる。ゆえに, $[n\phi]=r$ となり, $[[n\phi]\phi]=[n\phi^2]-1$.

10

郵便ポストを左から順に郵便ポスト $1,2,3,\dots,N$ とする. まず, プラン A について考える。プラン A の場合, どの時点でも各郵便ポストにちょうど 1 つ手紙がある. 郵便ポスト $i$ にある手紙の目的地を郵便ポスト $p_i$ とする. そこで次の補題を証明する：

(補題) $1,2,3,\dots,N$ の並べ替え $p_1,p_2,p_3,\dots,p_N$ に対し, $i\neq p_i$ となるような $i$ が 1 つ以上存在する場合, $i<p_i>p_{p_i}$ となるような $i$ が少なくとも1つは存在する.

(証明) $i\neq p_i$ であるような $i$ を 1 つ選ぶとき, $a_0=i$, $a_j=p_{a_{j-1}}$ とする. $a_k=i$ となるような $1$ 以上の最小の整数を $k$ とする. そのとき, このような $k$ は必ず存在する. なぜなら, 仮に存在しないとして, 最終的には $b_0,b_1,\dots,b_{m-1}$ のサイクルをたどり続けるとすると, このサイクルに初めて入る時を $b_0$, その 1 つ前の値を $c$ として $p_{b_{m-1}}=b_0$ かつ $p_c=b_0$ となり $c$ は $b_0,b_1,\dots,b_{m-1}$ に含まれないことから $b_{m-1}\neq c$ なのでこれは $p_0,p_1,\dots,p_{N-1}$ 同じ値が 2 つ含まれることになり矛盾するからである. そのとき,$a_0\neq a_1\neq a_2\neq\cdots\neq a_(k-1)\neq a_k$ かつ $a_0=a_k$ なので,$a_0<a_1<a_2<\cdots<a_k$ の場合, $a_0>a_1>a_2>\cdots>a_k$ の場合両方 $a_0=a_k$ を満たさないので, $<. >$ が両方存在することから $a_i<a_{i+1}>a_{i+2}$ となるような $i$ は必ず存在する. よって題意は示された.

そのとき, $i<p_i>p_{p_i}$ を満たすような $i$ に対して $j=p_i$, $k=p_{p_i}$ とすると $i<k$ のとき $p_j$ と $p_k$ を交換し, $i>k$ のとき $p_i$ と $p_j$ を交換する. また, $i=k$ の場合は $p_i$ と $p_j$ を交換する. $i$ から $p_i$ に向けて矢印を向けることを考えると, この方法では交換したものは必ず手紙は矢印の方向を進んでいる. なので, $i$ と $j$ の交換にかかるコストを $2\lvert i-j\rvert$ としたときにコスト $S$ 円が達成でき, これ未満はあり得ない. また, $i\neq p_{p_i}$ の場合は $j=p_j$ に変わる $j$ の個数が $1$ で, $i=p_{p_i}$ の場合 $2$ になる. そこで, $N$ 個の点があり $i$ 個目の点と $p_i$ 個目の点を結ぶという操作をすることで得られる連結な形の個数を $A$ とし, これに含まれる頂点数をそれぞれ $c_1,c_2,\dots,c_A$ とする. そのとき, 例えば $c_1$ を $(1,1,1,1,\dots,1)$ に分解されるようにするとき上の操作を行うと $(c_i)\to(c_i-1,1)\to(c_i-2,1,1)\to\cdots\to(2,1,1,1,\dots,1)\to(1,1,1,1,\dots,1)$ となり, 結果的に $c_i-1$ 回の操作で終わる. $c_1+c_2+\cdots+c_A=N$ なので交換回数 $(c_1-1)+(c_2-1)+(c_3-1)+\cdots+(c_A-1)=N-A$ 回が達成でき, これ未満はあり得ないことが分かった. よって, プラン A の最小コストは $S+N-A$ 円である.

次に, プラン B について考える. 先ほど述べた「連結な部分」ごとに考える. 連結な部分で $c_i\geq2$ であるようなものに対して, これに含まれる点の番号を左から順に $x_1,x_2,\dots,x_{c_i}$ とし (これ以降「座標」に対応させる), 郵便ポストの番号をこれに関して $1,2,\dots,c_i$ と割り振り, 目的の郵便ポストの番号を $p_i$ ($1\leq p_i\leq c_i$) とする. そのとき, 次の 2 つに場合分けをする. 「$x_1=x_2-1=x_3-2=x_4-3=⋯=x_{c_i}-c_i+1$ の場合」と「そうでない場合 ($x_i\neq x_{i+1}-1$ が 1 つでも存在する場合)」です.

Pattern 1: $x_i\neq x_{i+1}$ が 1 つでも存在する場合

$x_i\neq x_{i+1}-1$ を満たす $i$が 1 つでも存在するとき, $x_i<t<x_{i+1}$ であるような整数 $t$ が存在する. そのとき, $x_i<t<x_{p_i}$ が成立するような $i$ が存在する. 数直線上の座標 $x_i$ と $x_{p_i}$ を端点とした線分をすべての $i$ に対して書くと, すべての $j$, $T$ ($x_j<T<x_{j+1}$) に対して, 座標 $T$ を含む線分の個数は $1$ 個以上である. なぜなら, 仮に $0$ 個だとすると, 線分のまとまりが座標 $1,2,3,\dots,j$ の部分と $j+1,j+2,\dots,c_i$ の部分の 2 つに分かれてしまうことになり, 「連結な部分」であるということに矛盾する. よって, 座標 $t$ に対してもこれを含む線分が $1$ 個以上存在するから, $t$ がどの $x_j$ の値とも異なることより $x_i<t<x_{p_i}$ または $x_i>t>x_{p_i}$ であるような $i$ が 1 つ以上存在する. また, 座標 $t$ を含む右から左に向かう線分があったとしてそれより左に郵便ポストがあるので左から右に向かう線分もないとサイクルが存在しなくなってしまうので, いずれの場合でも $x_i<t<x_{p_i}$ となるような $i$ が存在する. そこで, $x_i\neq x_{i+1}-1$ を満たす $i$ を 1 つ選び, まず郵便ポスト $i$ の手紙を座標$x_i$ から $t$ に移動させる. 次に, $p_j=i$ となるような $j$ が 1 つ存在するから郵便ポスト $j$ の手紙を郵便ポスト $i$ に移動させ, その次に $p_k=j$ となるような $k$ が 1 つ存在するから郵便ポスト $k$ の手紙を郵便ポスト $j$ に移動させ…を繰り返すと, 「1 つのサイクルになっている」ことより郵便ポスト $i$ にあった手紙以外を届け終わったとき郵便ポスト $i$ に手紙が届けられる. その後, 郵便ポスト $i$ にあった手紙を座標 $t$ から座標 $x_{p_i}$ に移動させる. そのとき, コストは $|x_1-x_{p_1}|+|x_2-x_{p_2}|+…+|x_{c_i}-x_{p_{c_i}}|$ 円かかる.

Pattern 2: $x_i\neq x_{i-1}$ が 1 つも存在しない場合

まず, $c_i=2$ の場合を考える. $N\geq3$ なので, $x_1\neq 1$ あるいは $x_2\neq N$ のいずれかが満たされる. $x_1\neq 1$ のとき, 郵便ポスト $1$ にある手紙を $x_1-1$ に移動し, 郵便ポスト $2$ にある手紙を $x_1$ に移動し, 郵便ポスト $1$ にある手紙を $x_2$ まで移動させる. そのとき, コストは $S+2$ かかる. 次に, $c_i\geq3$ の場合を考える. まず郵便ポスト $1$ にある手紙を郵便ポスト $p_1$ に移動させる. 次に, $p_j=1$ であるような $j$ を 1 つ選び郵便ポスト $j$ にある手紙を郵便ポスト $1$ に移動させる. その次に, $p_k=j$ であるような $k$ を 1 つ選び郵便ポスト $k$ にある手紙を郵便ポスト $j$ に移動させる. その次に, $p_l=k$ であるような $l$ を 1 つ選び郵便ポスト $l$ にある手紙を郵便ポスト $k$ に移動させる…これを繰り返していくと, 最後に郵便ポスト $p_1$ にある手紙が移動されようとするが, そのときは最初郵便ポスト $1$ にあった手紙を左か右に座標 $1$ 移動させる (ただし, 移動できる方でかつ郵便ポスト $p_{p_1}$ ではない場所に移動しなければならない. ただし, $p_1=c_i$ かつ $p_{p_1}=c_i-1$ の場合はできない！). その後, 郵便ポスト $p_1$ にある手紙を郵便ポスト $p_{p_1}$ まで移動させ, 最初郵便ポスト $1$ にあった手紙を郵便ポスト $p_i$ に戻す. しかし, この方法だと $p_1=c_i$ かつ $p_{p_1}=c_i-1$ の場合にできない. そこで, 座標の左右を反転させて郵便ポスト $c_i$ からスタートする, ということをすれば $c_i\geq3$ より $p_{p_i}\neq 1$ であるから 1 つ目の方法でできない場合これでは必ずできる. この場合, コストは $S+2$ 円かかる. よって, このパターンの場合 $S+2$ 円以下に抑えることができる.

以上の考察から, プラン A の場合 $S+N-A$ 円かかり, プラン B の場合 $S+2A$ 円以下かかるということがわかる. $S+N-A\leq S+2A$ は $A\geq\dfrac{N}{3}$ の場合に満たされ $A=\dfrac{N}{3}$ の場合でも $S+N-A=S+\dfrac{2}{3}N$, $S+N-A>S+2A$ は $A<\dfrac{N}{3}$ の場合に満たされこの場合 $S+2A<S+\dfrac{2}{3}N$ である. したがって, $\min⁡(S+N-A,S+2A)$ は $S+\dfrac{2}{3}N$ を超えないから, 最適に行動したとき $S+\dfrac{2}{3}N$ 以下でできることが示された.

11

$(a+bi)^n=m$ となったとする ($n$ は正整数). $a$ と $b$ がともに $0$ であるときは成り立つので除く. $a$ と $b$ が互いに素なときのみを考えて, その非ゼロ整数倍を考えれば良い. つぎに $a$, $b$ がともに奇数だとすると, $\dfrac{a+b}{2}$ と $\dfrac{-a+b}{2}$ は共に整数であり, 偶奇は異なる. よって, $\biggl(\dfrac{a+bi}{1+i}\biggr)^{4n}=\biggl(\dfrac{a+b}{2}+\dfrac{(-a+b)i}{2}\biggr)^{4n}=\biggl(\dfrac{(a+bi)^4}{4}\biggr)^n$ となるので, 偶奇が違うときのみ考え, それを $1+i$ 倍すればよい. $a$, $b$ のどちらかが $0$ の時, つまり $a+bi=\pm i$ もしくは $\pm1$ のとき) は成り立つので除く. このとき $n$ は $2$ 以上である. 絶対値をとり $(a^2+b^2)^n=m^2$. $m$ は $a^2+b^2$ の倍数として良い. ここから、「虚部と実部が共に $\bmod{a^2+b^2}$ で $0$ になること」がない, とわかれば解がないことがわかる. 以下 $c+di≡e+fi$ で $c\equiv e\pmod{a^2+b^2}$ かつ $d\equiv f\pmod{a^2+b^2}$ を表すものとする ($c$, $d$, $e$, $f$ は整数). $(c+di)(a+bi)^2\equiv0 \implies c(a^2-b^2)\equiv d\times2ab$ かつ $d(a^2-b^2)+c\times2ab\equiv0$. $\therefore a^2c\equiv2abd+b^2c$ かつ $a^2d+2abc\equiv b^2d$. $\therefore 0\equiv2abd+2b^2c$ かつ $2abc\equiv2b^2d$. $\therefore 0\equiv2b(bc+ad)$ かつ $2b(ac-bd)\equiv0$. ここで, $a$, $b$ の偶奇が異なるので, $2$ と $a^2+b^2$ は互いに素. また, $\text{$a$ と $a^2+b^2$ が互いに素} \iff \text{$a$ と $b^2$ が互いに素} \iff \text{$a$ と $b$ が互いに素}$, となるので $a$ と $a^2+b^2$ は互いに素. ゆえに, $2a$ と $a^2+b^2$ は互いに素. 同様にして $2b$ と $a^2+b^2$ は互いに素. ゆえに, $bc+ad\equiv ac-bd\equiv0$. $\therefore (c+di)(a+bi)\equiv0$. よって, $(a+bi)^n=0 \implies (a+bi)^n-2(a+bi)^2\equiv0 \implies (a+bi)^n-2(a+bi)\equiv0 \implies (a+bi)^n-3(a+bi)^2\equiv0 \implies \cdots$ と繰り返すことにより, $a+bi\equiv0$ が成り立つ. 特に, $a\equiv0\pmod{a^2+b^2}$ が成り立ち, $0<\lvert a\rvert\leq a^2<a^2+b^2$ となるので, これは矛盾. よって, $\pm i$, $\pm1$ もしくはこれに $1+i$ や非ゼロ整数倍をしたもの, もしくは $0$ という形をしたもの, つまり. $\boxed{a, ai, a+ai, a-ai \text{ ($a$ は整数)}}$ が答である.

12

$AB<AC$ と仮定しても一般性を失わない. 直線 $AX$, $EF$, $BC$ は根心 $G$ で交わる. 三角形 $ABC$ の九点円は $D$, $M$, $E$, $F$ を通ることより方冪の定理より $GD\cdot GM=GE\cdot GF=GB\cdot GC$. よって $G$, $B$, $D$, $C$ は調和点列. 直線 $PQ$ と直線 $GA$ との交点を $Z$, 直線 $EF$, $PQ$ の交点を $R$ とする. ここで $\angle{AFE}=\angle{ACB}=\angle{AQP}$ より, 内接四角形定理の逆から $E$, $F$, $P$, $Q$ 共円であるから, 方冪の定理より $RP\cdot RQ=RE\cdot RF$. また, 円 $APQ$ は $PQ$ に $H$ で接しているので, 方冪の定理より $RE\cdot RF=RX^2$. これらを合わせて $RP\cdot RQ=RX^2$. $PQ\parallel BC$ より $Z$, $P$, $H$, $Q$ は調和点列であるから, $ZH$ の中点を $R ^ {\prime}$ とすると $R ^ {\prime}P\cdot R ^ {\prime}Q=R ^ {\prime}H^2$. よって $R$, $R ^ {\prime}$ は一致する. これと $\angle{ZXH}=90\degree$ であることより $RZ=RX=RH$. ゆえに $RX^2=RP\cdot RQ$ であるから方冪の定理の逆より $\triangle{XPQ}$ の $X$ における接線は $XR$ である. ここで, 方冪の定理より $GD\cdot GM=GE\cdot GF=GX\cdot GA$ より方冪の定理の逆から $XADM$ 共円なので, $\angle{AXM}=\angle{ADM}=90\degree$. よって $\angle{GXH}=\angle{GXM}=90\degree$ なので $X$, $H$, $M$ 共円. さて, $ZR=HR$ より $GY=MY$, $AD\perp GM$, $AG\perp MX$ より円 $XYD$ は三角形 $AGM$ の九点円である. よってこれは $AM$ の中点を通る.