問題

2019 年 9 月 21・22 日時間無制限 14 題

一問でも解けたら採点係のところまで持ってきてください. 採点は何度でも可能です.
第 7 問からは証明問題です. 答を求める問題であっても必ず証明をつけてください.
小学生は 4 問, 中学生は 6 問, 高校生は 8 問, OB・大学生は 10 問で殿堂入りです.

1

次の虫食い算を解け.

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

2

次の虫食い算を解き, $\mathrm{SHOWA}$, $\mathrm{HEISEI}$, $\mathrm{REIWA}$ の値をそれぞれ求めよ. ただし, $\mathrm{A}, \mathrm{E}, \mathrm{G}, \mathrm{H}, \mathrm{I}, \mathrm{N}, \mathrm{O}, \mathrm{R}, \mathrm{S}, \mathrm{W}$ は $0, 1, \dots, 9$ の並び替えである.

$$\def\arraystretch{1.5} \begin{array}{ccccccccccc} &&&&&&\mathrm{R}&\mathrm{E}&\mathrm{I}&\mathrm{W}&\mathrm{A}\\ &&&\times &&\mathrm{H}&\mathrm{E}&\mathrm{I}&\mathrm{S}&\mathrm{E}&\mathrm{I}\\ \hline &&&&&\mathrm{G}&\mathrm{A}&\mathrm{N}&\mathrm{N}&\mathrm{E}&\mathrm{N}\\ &&&\mathrm{H}&\mathrm{S}&1&\mathrm{O}& \square &\mathrm{S}&&\\ &&\mathrm{G}&\mathrm{A}&\mathrm{N}&\mathrm{N}&\mathrm{E}&\mathrm{N}&&&\\ 3&\mathrm{W}&1&\mathrm{H}&\mathrm{W}&\mathrm{O}&&&&&\\ \hline \square & \square & \square & \square & \square & \square & \square & \square & \square & \square & \square \end{array}$$

3

$2019 \times 2019$ のマス目を, 以下の条件を満たすように白黒で塗り分ける方法はいくつあるか.

条件：どの $2 \times 2$ のマスをとっても, その $4$ マスのうち白, 黒がそれぞれ $3$ 個, $1$ 個または $1$ 個, $3$ 個である.

4

四角形 $ABCD$ は $CD=DA=AB$, $\angle{ABC}=72\degree$, $\angle{DAB}=96\degree, \angle{BCD}<90\degree$ をみたす. このとき, $\angle{CDA}$ の大きさを求めよ.

5

短針と長針と秒針の長さの比が $1:2:2$ である時計において, これらの 3 針の先端が同一直線上に並ぶことは 1 日に何回あるか.

6

次の虫食い算の解はいくつあるか. ただし, 頭に $0$ がいくつ入ってもよい.

$$ \square \square \square \square \times \square \square \square \square = \square \square \square \square \ 9\ \square \square \square $$

7

$n$ を整数とする. $4n$ 個の都市と, 2 つの異なる都市を双方向に結ぶ $6n$ 本の道路があり, どの都市も 3 つの道路とつながっている. また, 同じ二つの都市を複数の道路が結ぶことはない. さらに, ある都市から出発して, 道路で直接つながれた都市に移動することを繰り返して, 全ての年をちょうど 1 回ずつ訪れてから元の都市に戻ってくる方法がある. このとき, それぞれの都市に次の条件を満たすように 4 種類の産業を割り当てられることを示せ.

道路でつながれた 2 都市の産業は相異なる.
どの産業も割り当てられている都市は $n$ 個ずつである.

8

正の実数に対して定義され, 正の実数値をとる関数 $f$ であって, 任意の正の実数 $x$ に対して $f(x+1)=f(x)+1$, $f\left(x+\dfrac{1}{x}\right)>f(x)$ を共にみたす関数は (全て) 広義単調増加であるか.

9

実数に対して定義され実数値をとる関数 $f$ であって, 次が成り立つものをそれぞれ全て求めよ.

(1)

任意の実数 $x$ に対して $f(x)+f(f(x))+f(f(f(x))+\cdots$ が定義され, 値が $x$ である.

(2)

任意の実数 $x$ に対して $f(x)+f(f(f(x)))+f(f(f(f(f(x)))))+\cdots$ が定義され, 値が $x$ である.

10

$n$ を正の整数とし, 実数 $x$ に対し $[x]$ で $x$ を超えない整数, 正整数 $m$ に対し $\varphi(m)$ で $1$ 以上 $m$ 以下の整数のうち $m$ と互いに素なものの個数を表すとする. $\displaystyle\sum_{i=1}^{n}\left[\dfrac{n}{i}\right]\varphi(i)$ の値を求めよ.

11

$AB=5$, $BC=7$, $CA=8$ をみたす三角形 $ABC$ があり, 外接円を $\Gamma$, 内心を $I$, $I$ から $BC$ におろした垂線の足を $D$ とする. $AI$ と $\Gamma$ の交点のうち $A$ でない方を $M$, $MD$ と $\Gamma$ の交点のうち $M$ でない方を $E$, $E$ を通り $BC$ に平行な直線と $\Gamma$ の交点のうち $E$ でない方を $F$, $A$ を通り $BC$ に垂直な直線と $FM$ の交点を $G$ とする. 三角形 $AFG$ の外接円の半径の長さを求めよ.

12

$a$, $c$, $n$ を正整数とする. $n\times n$ のマス目がある. A 君は各マスに $1$ 以上 $a$ 以下の整数を一つずつ書き込み, B 君は $1$ 以上 $a$ 以下の整数から $c$ 個以下を選び, その数が書かれているマス目を黒く塗りつぶす. その黒マスから成る上下左右にわたる連結成分のマス数の最大値をスコアとし, A 君はスコアを最小化するように, B 君は最大化するように行動する. $c$ が次の値のとき, ある整数 $N$ が存在して任意の $n$ に対してスコアが $N$ 以下になるような $a$ の最小値をそれぞれ求めよ.

(1)

$c=2$

(2)

$c=2019$

13

$AB\neq AC$ なる三角形 $ABC$ があり, 内接円と $BC$, $CA$, $AB$ との接点を $D$, $E$, $F$, 内心を $I$ とする. $D$ を通り $AI$ に平行な直線と内接円との交点のうち $D$ でない方を $P$ とし, 直線 $AP$ と三角形 $IPD$ の外接円との交点のうち $P$ でない方を $Q$ とする. また, 三角形 $BFQ$ の外接円と三角形 $CEQ$ の外接円との交点のうち $Q$ でない方を $R$ とする. このとき, $Q$, $I$, $R$ が同一直線上にあることを示せ.

14

任意の正整数 $n$ に対してある正整数 $m$ が存在して, $\displaystyle\sum_{k=1}^m k^k$ が $n$ の倍数になることを示せ.

解答

1

$12137\times82817$.

2

順に $54867$, $403503$, $90367$.

3

一段目と一列目の計 $4037$ マスの塗り方を定めれば残りのマスの塗り方も一意に定まる. $2^{4037}$ 通り.

4

辺 $BC$ 上に点 $E$ を $\angle{BAE}=36\degree$ となるようにとると三角形 $AED$ が正三角形であるため, $144\degree$.

5

長針と秒針が重なってから次に重なるまでの $\dfrac{60}{59}$ 分の間にちょうど 1 回一直線上に並ぶので, 答はこれらが重なる回数の $2$ 倍である $1440\div\dfrac{60}{59}\times2=2832$ 回.

6

4 桁以下の正の整数の組 $(a, b)$ であって, $ab$ を $10000$ で割った余りが $9000$ 以上であるものの個数を求める問題である. $a$ を固定したときに $b$ が何通りあるかを考える. $g=\mathrm{gcd}(a, 10000)$ として, $ab$ を $10000$ で割った余りは $0, g, 2g, \dots, 10000-g$ がそれぞれ $g$ 回ずつ現れるので, この中に $9000$ があるときは $1000$ 通り, そうでないときは $9000$ 以上の最小の $g$ の倍数を $x$ とすると $10000-x$ 個である. ここで, $9000$ が現れない条件は $2^4\mid g$ または $5^4\mid g$ であるから, $g$ は $16$, $80$, $400$, $2000$, $625$, $1250$, $2500$, $5000$ の 8 種類のみであり, そのような $a$ はそれぞれ $500$, $100$, $20$, $4$, $8$, $4$, $2$, $1$ 個であり, $b$ の個数はそれぞれ $1000$ より $8$, $40$, $200$, $1000$, $375$, $1000$, $1000$, $1000$ 個少ない. よって求める個数は $9999\times1000-(500\times8+100\times40+\cdots)=9973000$ 個.

7

全ての都市を 1 度ずつ訪れて戻ってくる経路 (以下サイクル) で訪れる順に $1, 2, \dots, 4n$ と都市に番号を振り, 番号が奇数の都市に A, B を, 偶数の都市に C, D を割り当てるとする. サイクル以外の $2n$ 本の道路の両端は全て異なる. それらのうち奇数-奇数のペアは片方に A, もう片方に B, 偶数-偶数のペアは片方に C, 片方に D を割り当て, 残りの奇数-偶数のペア (偶数個) の半分を A-C, もう半分を B-D と割り振ればどの産業も $n$ 都市ずつであり, サイクル上の道路で隣り合う都市も, そうでない道路で隣り合う都市も相異なる産業であり, 題意を満たす.

8

$f(x)=\begin{cases}x+\lbrace x\rbrace-\lbrace x\rbrace^2 & \text{($x$ が正の有理数)}\\ x & \text{($x$ が正の無理数)} \end{cases}$ (ただし, $\lbrace x\rbrace$ は $x$ の小数部分を表す) とすれば条件を満たし, 広義単調増加ではない.

他にも様々な構成がある.

9

(1)

$x$ に $f(x)$ を代入して, 元の式と比較すると $f(x)=\dfrac{x}{2}$. これは題意を満たす.

(2)

$f$ の $n$ 回合成を $f_n(x)$ とする. $x$ に $f(f(x))$ を代入して, 元の式と比較すると $f(x)+f(f(x))=x$. よって, この数列は $a_0=1, a_1=0, a_{n+2}=-a_{n+1}+a_n$ で定義される整数列 $\lbrace a_n\rbrace$ を用いて, $f_n(x)=a_n+a_{n+1}f(x)$ と書ける. ここで $b_n=(-1)^na_n$ とすると $b_n$ はフィボナッチ数列である. また, 左辺が収束することから $\displaystyle\lim_{n \to \infty}f_n(x)=0$ であるため, $f(x)=-\left(\displaystyle\lim_{n\to\infty}\dfrac{a_n}{a_{n+1}}\right)x=\dfrac{-1+\sqrt{5}}{2}x$. これは題意を満たす.

10

$\lbrace(a, b)\in\mathbb{N}^2\mid 0\leq a<b<n\rbrace$ という集合を考える. $\dfrac{a}{b}$ を既約分数で表したときに分母が $d$ になるものが $\varphi(d)\left[\dfrac{n}{d}\right]$ 個になるので, 求める値はこの集合の大きさ, つまり $\dfrac{n(n+1)}{2}$.

11

$I_a$ を $A$ に対する三角形 $ABC$ の傍心とする. $AI$ を直径とする円と $\Gamma$ の交点を $E ^ {\prime}$, $E ^ {\prime}M$ と $BC$ の交点を $D ^ {\prime}$ とすると, $M$ が四角形 $IBI_aC$ の外心であることと $\angle{MBC}=\angle{BE ^ {\prime}M}$ より $MI^2=MB^2=MD ^ {\prime}\cdot ME ^ {\prime}$ から, 角度計算により $D=D ^ {\prime}$ がわかり, $E=E ^ {\prime}$ も言える. $F ^ {\prime}$ を $AI_a$ を直径とする円と $\Gamma$ の交点として内心と同様のことをすると, $MF ^ {\prime}$ と $BC$ の交点が傍接円との接点であることがわかるので, $\triangle{MEF}$ は二等辺三角形であり, $F=F ^ {\prime}$ がわかる. また, $\angle{AGF}=\angle{AI_aF}$ がわかるので $AFI_aG$ 共円であるから求める長さは $\dfrac{AI_a}{2}$. $\angle{BAC}=60\degree$, $MI=MI_a$ であることに注意すれば, $AM=\dfrac{13\sqrt{3}}{3}$, $MI_a=\dfrac{7\sqrt{3}}{3}$ より答は $\dfrac{10\sqrt{3}}{3}$.

12

$a\leq c$ のときはすべてのマスを黒くできるので, $a\geq c+1$ である. $a=c+1$ のとき $0\leq i\leq c$ に対し, $x-y\equiv4i\pmod{4c}$ または $x+y\equiv4i+1\pmod{4c}$ なるマス $(x, y)$ に $i$ を書き込み, それ以外に $c+1$ を書き込むと, どの数もその数だけで盤面を有限な大きさの連結成分に分割しているので, これは題意を満たす. よって

(1)

$3$

(2)

$2020$

である.

$c=2$ のときのみに適用できる構成例もある. 例えば以下のマス目を敷き詰めればよい.

$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|}\hline 3&2&1&3&1&2\\ \hline 3&1&2&3&2&1\\ \hline 1&3&3&2&3&3\\ \hline 3&1&2&3&2&1\\ \hline 3&2&1&3&1&2\\ \hline 2&3&3&1&3&3\\ \hline \end{array}$$

13

$AB<AC$ としても一般性を失わない. 三角形 $ABC$, $IPD$ の外接円をそれぞれ $\Gamma$, $\Omega$ とする. $A$ を含まない方の弧 $BC$ の中点を $M$, 含む方を $N$ とする. また, $\Gamma$, $\Omega$ の交点のうち $A$ を含まない方の弧 $BC$ 上にあるものを $Q ^ {\prime}$, $MQ ^ {\prime}$, $BC$ の交点を $X$ とする. このとき, 円 $BIC$ の中心が $M$ であることから, この円での反転により $\Gamma$ と $BC$ が対応するため $MQ ^ {\prime}\cdot MX=MI^2$ より $X$ は $\Omega$ 上にある. $\angle{XQ ^ {\prime}I}=\angle{XDI}=90\degree$ より $Q ^ {\prime}IN$ 共線. ここで, $AI$ を直径とする円と $\Gamma$ の交点のうち $A$ でない方を $Y$ とすると, 角度計算により $\triangle{YFE}$ と $\triangle{YBC}$ が $Y$ を中心とする回転相似であり, $A$ と $N$, $P$ と $I$ が対応する. よって $AP$ と $NI$ のなす角は $EF$ と $BC$ のなす角と等しく, これは同時に $\angle{PDI}$, $\angle{AMN}$ とも等しいので $AP$, $NI$ の交点は $\Gamma$, $\Omega$ の交点である. よってこれは $Q ^ {\prime}$ であり, $Q=Q ^ {\prime}$ がわかる. また, 円 $BFQ$ と $EF$ の交点のうち $F$ でない方を $R ^ {\prime}$ とすると, $Q$ が $\Gamma$ 上にあることから角度計算により $R$ が $EF$ 上にあることがわかり, 再び角度計算により $QRN$ 共線がいえるので, 題意が示される.

$Q$ は三角形 $ABC$ の混線内接円と外接円の接点である.

14

$n=p^x$ ($p$ は奇素数)のとき, $S_x=\lbrace n\mid 1\leq n\leq p^x(p-1), p\nmid n\rbrace$とすると, Euler の定理に注意すれば, 帰納法により $$p^x|\displaystyle\sum_{k\in S_{x+1}}k^k$$ が示せる. また, $$\displaystyle\sum_{k\in S_x}k^k\equiv\sum_{p\nmid i}^{p^x}\sum_{i\equiv j\pmod{p^{x-1}}}^{p^{x-1}(p-1)}i^j\pmod{p^x}$$ より, $i\equiv1\pmod{p}$ かどうかで場合分けすることで, $$p^x\nmid\displaystyle\sum_{k\in S_x}k^k$$ が示される. これらより, 十分大きな $M$ に対して $\displaystyle\sum_{k=1}^{M+p(p-1)i}k^k$ を $p^x$ で割った余りは $i=0, 1, \dots, p^x-1$ で相異なることから, 任意の $c$ に対してある $c ^ {\prime}\equiv c\pmod{p(p-1)}$ が存在して, $m\equiv c ^ {\prime}\pmod{p^{x+1}(p-1)}$ なる十分大きな $m$ が題意を満たすことが示せる. 次に, $n=2^x$ のとき, $S_x=\lbrace n\mid 1\leq n\leq 2^x, n\text{ は奇数}\rbrace$ とすると同様にして $x\geq2$ で $$2^x\mid \displaystyle\sum_{k\in S_x}k^k$$ が示せる. また, $$2^{x+1}\nmid\displaystyle\sum_{k\in S_x}k^k$$ は $x=l$ で成立と仮定すると, $$2^{l+2}\nmid \displaystyle\sum_{k\in S_{l+1}}k^k \iff 2^{l+2}\mid \sum_{k=2^l+1}^{2^{l+1}}k^k-\sum_{2\nmid k}^{2^l}k^k$$ に注意して, $k\equiv1, 3\pmod4$ で場合分けすれば帰納法で示せる. これらより, 数列 $\lbrace c_x\rbrace$ が, $m\equiv c_x\pmod{2^x}$ なる十分大きな $m$ が題意を満たすように定まることが, $c_{l+1}$ として十分大きな $M$ を用いて $M2^l+c_l$, $(M+1)2^l+c_l$ のいずれかがみたすことから示せる. $n$ が一般の時は $$n=\displaystyle\prod_{k=1}^{y}p_k^{\operatorname{ord} _ {p_k}(n)}\quad\text{($p_1<p_2<\cdots<p_y$ は素数)}$$ として, $\bmod X_y$ での解の存在が $p_{l+1}\nmid X_l$ から中国剰余定理により, $y$ についての帰納法で示せる. ただし, $X_i$ とは, $p_k=2$ のとき $Y_k=2^{\operatorname{ord} _ 2(n)}$, $p_k\neq2$ のとき $Y_k=p_k^{\operatorname{ord} _ {p_k}(n)+1}(p_k-1)$ として, $Y_1, \dots, Y_i$ の最小公倍数のことである.