$a=b=1$ を代入すると $k\leqq 4$ が必要であることがわかる. 一方で $k=4$ のとき \[\Bigl(\sqrt{a}+\sqrt{b}\Bigr)^2-4\left(\frac{1}{\sqrt{a}}+\frac{1}{\sqrt{b}}-\frac{1}{ab}\right)=\left(\sqrt{a}+\sqrt{b}-\frac{2}{\sqrt{ab}}\right)^2\geqq 0 \] であるから, 求める最大値は $4$ である.

工事中

工事中

工事中

$x\geqq 6$ のとき, $\bmod{64}$ と $\bmod{17}$ を観察することで解が存在しないことがわかる.

$x\leqq 5$ において個別に確かめれば, $(x,y)=(3,1),(5,3)$ が求める解であることがわかる.

工事中

求める条件は $n=2k$ である. 以下それを示す.

$({\rm i})$　$n=2k$ のとき： 紗夜は日菜が $A_s$ に置いた直後に, $A_{s+k}$ にまだ駒が置かれていない場合は $A_{s+k}$ に, そうでない場合はどこか空いているところに置く, ということを繰り返せば, すべての点に駒を置くことになる.

$({\rm ii})$　$n\neq 2k$ のとき： ある点 $A_s$ から始めて, $A_s,A_{s+k},A_{s+2k}\ldots$ と $k$ ずつ進んでいくと, いずれ元の点 $A_s$ に戻る. このときに通った $n/\gcd(n,k)$ 個の点を $1$ つのグループとする. $n$ 個の点は $\gcd (n,k)$ 個のグループに分かれ, $n\neq 2k$ より各グループは $3$ つ以上の点を含むことになる. 日菜は, 紗夜が $A_s$ に駒を置いた直後に, $A_s$ が属するグループに駒が $1$ つしか置かれていない場合は $A_{s+2k}$ に, $2$ つ以上置かれていた場合は $A_{s+k}$ に置くこととする. このようにすれば, どちらも駒が置けない場所が存在し, 日菜は紗夜の行動にかかわらず必ず駒を置けるので, 必ず日菜が勝つことができる.

工事中

$\Omega$ の中心を $O$ とする. $\angle ABC=\angle ADC$ および $\angle ABC+\angle ADC=180^\circ$ より $\angle ABC=\angle ADC=90^\circ$ であり, $O$ は $AC$ 上にある. $BP,DP$ と $\Omega$ の交点であって, $B,D$ とは異なるものをそれぞれ $B’,D’$ とする. すると, \[\angle B’AC=\angle B’BC=\angle D’DA=\angle D’CA\] となり, 四角形 $AB’CD’$ が長方形であることが分かる. よって $O$ は $B’D’$ 上にある.

次に, $\angle OSX=\angle OTX=90^\circ$ より $4$ 点 $S,T,O,X$ は同一円周上にあり, \[OP\cdot XP=SP\cdot TP=DP\cdot D’P\] より $4$ 点 $D,O,D’,X$ は同一円周上にある.

以上より, $\angle PXD=\angle OD’D=\angle PBD$ となり, $4$ 点 $B,D,P,X$ が同一円周上にあることが示された.

工事中

求める関数は $f(n)\equiv n+1$ のみであることを示す. これは明らかに与式をみたす. $P(n,f(m))$より \[f^{f(n)+1}(m)=f^{f(m)}(n)+1=f^n(m)+2\] 　まず $f(n)\geqq n+1$ を示す. ある正の整数 $n$ について $f(n)=n$ と仮定すると, $P(n,n)$ より $f^n(n)=f^n(n)+1$ となり矛盾する. また, ある正の整数 $n$ について $f(n)\leqq n-1$ であると仮定し, $f(n)+1=n-k$　とおく. このとき \[f^{n-k}(m)=f^n(m)+2\] $m$ に $f^k(m),f^{2k}(m),\ldots, f^{ik}(m)$ を代入すると \[f^{n-k}(m)=f^n(m)+2=f^{n+k}(m)+4=\cdots=f^{n+ik}(m)+2(i+1)\] となるが, $i$ を十分大きくとると $f^{n-k}(m)\lt 2(i+1)$ となるため, $f^{n+ik}(m)\gt 0$ に矛盾する.

よって $f(n)\geqq n+1$が示された. これを繰り返し用いると \[f^{f(m)}(1)\geqq f^{f(m)-1}(1)+1\geqq \cdots \geqq f(1)+f(m)-1\geqq 1+f(m)\] 一方 $P(m,1)$ より $f^{f(m)}(1)=f(m)+1$ であるから, すべての不等号は等号となり, 特に $f(1)=2$ である.

以下, 数学的帰納法によりすべての $n$ について $f(n)=n+1$ となることを示す. ある $k$ について, 任意の $n\leqq k$ で $f(n)=n+1$ と仮定する. このとき以下より, $f(1)=2$ とあわせて $f(n)\equiv n+1$ が示された. \[f(k+1)=f(f(k))=f^{f(1)}(k)=f^k(1)+1=f^{k-1}(2)+1=\cdots=f(k)+1=k+2\]

工事中

$DE$ と $BC$ の交点を $F$ とし, 点 $Q$ を $NQ$ が円 $\Gamma$ の直径となるような点とする. \[DB=EC,\quad QB=QC,\quad \angle QBD=\angle QCE\] より $\triangle QDB\equiv \triangle QCE$. よって $\angle QDA=\angle QEA$ より $4$ 点 $A,D,E,Q$ は同一円周上に存在する. したがって \[\angle QEF=\angle QAB= \angle QCF\] となり, $4$ 点 $Q,E,C,F$ も同一円周上に存在する. これを用いると, \[\angle QFE=\angle QCA=\angle QPA\] が分かり, これと $AP\parallel DE$ より $Q,P,F$ が同一直線上にあることが分かる. したがって, \[\angle NPF=180^\circ -\angle QPN=90^\circ\] また, $\angle NMF=\angle NHF=90^\circ $ であるから, $5$ 点 $F,P,H,M,N$ は同一円周上にある.

工事中

todo: 図の作成

求める最小の値は $2$ であることを示す.

数を書き込む操作は, 左下から右上までの道を書き込む操作と言い変えることができる. このとき, 図1の $A$ ～ $D$ のような部分の数の最小値を求める問題と言い換えられる.

まず, このような部分が必ず $2$ か所以上現れることを示す. $A$ と $B$ のうち少なくとも一方は $1$ か所以上現れることを示す. $A$ と $B$ がどちらも現れないとして矛盾を導けばよい. ここで左上の角を考えると, 必ず図2のようになる. そして $☆$ のマスを考えたとき, $A$ と $B$ が $1$ つもないという仮定から, このマスは図3のようにならなければならないと分かる. 次に図3の $★$ のマスについて考えると, 同様に図4のようになる. これを繰り返していくと, マス目の下端または右端に達したときに矛盾する. よって $A$ と $B$ の少なくとも一方は $1$ か所以上現れる.

同様に, 右下の角を考えることでCとDの少なくとも一方は $1$ か所以上現れることが示せるので, 図1の $A$ ～ $D$ のような部分が $2$ か所以上現れることが示された.

逆に図5のように渦巻き状の道を作れば, 図1のような部分はちょうど $2$ か所になることが分かる.

工事中

三角形 $ABC$ の内心を $I$, 辺 $BC$ の中点を $R$, 弧 $BC$ ($A$ を含まない方)の中点を $S$ とする. 六角形 $KNBACM$ に注目するとPascalの定理より $I,P,Q$ は同一直線上にある. また六角形 $ABCMKS$ に注目するとPascalの定理より $P,I,R$ は同一直線上にある. よって直線 $PQ$ と直線 $IR$ は一致するため, $IR\parallel PQ$ を示せばよい.

三角形 $ABC$ の内接円と辺 $BC$ の接点を $E$ とし, 線分 $EF$ が三角形 $ABC$ の内接円の直径となるように点 $F$ をとる. well-known fact として $A,F,D$ は同一直線上にあり, かつ $RE=RF$ となる. よって中点連結定理より $FD\parallel IR$ となり, 題意は示された.

工事中

まず, 次の式が成立する. \[S_n=\prod_{k=1}^{\infty}(1+{\rm ord}{p_k}(n!))\] 一方で \[{\rm ord}{p_k}(n!)=\sum_{i=1}^\infty \Biggl \lfloor \frac{n}{p_k^i} \Biggr　\rfloor\lt\sum_{i=1}^\infty \frac{n}{p_k^i}=\frac{n}{p_k-1} \implies 1+{\rm ord}_{p_k}(n!) \leqq \left \lceil \frac{n}{p_k-1}\right \rceil\] 以上より, $n$ が条件をみたすとき, 上式の不等号が任意の $k$ について等号となる必要がある.

ところで, $n$ を次のように $p$ 進法で表示する. \[n=\sum_{i=0}^\infty r_i p^i\] これを用いて, 次のように変形する. \[{\rm ord}{p}(n!)=\sum{i=1}^\infty \left\lfloor \frac{n}{p^i}\right\rfloor=\sum_{i=1}^\infty \sum_{j=0}^\infty r_{i+j}p^j\] 最右辺はさらに次のように変形される. \[\sum_{i=1}^\infty \sum_{j=0}^\infty r_{i+j}p^j=\sum_{i=1}^\infty \sum_{j=0}^\infty r_j p^{j-i}-\sum_{i=1}^\infty \sum_{j=0}^\infty r_j p^{-i}=\frac{n}{p-1}-\frac{1}{p-1}\sum_{j=0}^\infty r_j\] 以上より, \[\frac{1}{p-1}\sum_{j=0}^\infty r_j=\frac{n}{p-1}-\left\lceil\frac{n}{p-1}\right\rceil+1 \leq 1 \implies \sum_{j=0}^\infty r_j \leq p-1\] つまり, $n$ を $p$ 進数で表したときの各桁の和が $p-1$ 以下になる.

$p=2$ のときを考えると $n$ は $2$ べきであるから, 非負整数 $a$ を用いて $n=2^a$ と表す.

$({\rm i})$　$n$ を $3$ 進法で表示したときの各桁の和が $1$ のとき： $n$ が $2$ べきでも $3$ べきでもあることから, $n=1$ である.

$({\rm ii})$　$n$ を $3$ 進法で表示したときの各桁の和が $2$ のとき： 非負整数 $b\geqq c$ を用いて $2^a=n=3^b+3^c$と表せる. $\bmod{3}$ と $\bmod{8}$ を見ることで, 解が $(n,a,b,c)=(2,1,0,0),(4,2,1,0)$ のみであることが分かる.

逆に $n=1,2,4$ は条件をみたすから, これらが求める解である.

工事中

関数 $F:\mathbb{R}\rightarrow\mathbb{R}$ が任意の実数 $x,y$ について次をみたすとき, これを面白い関数}とよぶこととする. \[y=\frac{F(x)+1}{F(x)-1}\implies x=\frac{F(y)+1}{F(y)-1}\]

補題より以下が成立し, これより $f^n(a)=1\pm \sqrt{2}$ が必要である. \[f^{2n}(a)=\frac{a+1}{a-1}\implies a=\frac{f^{2n}(a)+1}{f^{2n}(a)-1}\implies f^n(a)=\frac{f^n(a)+1}{f^n(a)-1}\] 　逆に $f(x)=x$ は条件をみたし, $n=1,a=1\pm \sqrt{2}$ とすればいずれもありうるから, これらが求める値である.

工事中

三角形 $P_iP_jP_k$ であって, $3$ 辺が同じ色である三角形を良い三角形, そうでない三角形を悪い三角形とよぶ. また, 相異なる $3$ 点の順序付きの組 $(P_i,P_j,P_k)$ であって, 辺 $P_iP_j,P_jP_k$ がそれぞれ赤, 青で塗られているものをすごい組とよぶ.

このとき, すごい組の個数は悪い三角形の個数の $2$ 倍である. なぜならば, \[(P,Q,R),(P,R,Q),(Q,P,R),(Q,R,P),(R,P,Q),(R,Q,P)\] のうちすごい組の個数は, 三角形 $PQR$ が良いとき, 悪いときでそれぞれ $0,2$ 個だからである. また, 頂点 $P$ から赤い辺が $n$ 本出ているとき, $(*,P,**)$ の形のすごい組は $n(24-n)\leqq 144$ 個であるため, 全体ですごい組は $3600$ 個以下である. よって悪い三角形は $1800$ 個以下であるから, 良い三角形は少なくとも ${}_{25}{\rm C}_3-1800=500$ 個ある.

逆に良い三角形が $500$ 個となる辺の塗り方が存在することを示す. 添字を $\bmod{25}$ で同一視する. $P_iP_{i+k}$ ($i$ は整数, $k$ は $1$ 以上 $6$ 以下の整数) と表される辺をすべて赤で, 他の辺をすべて青で塗れば, どの頂点からも赤い辺が $12$ 本出るため, 上の評価において等号が成り立ち, 特に良い三角形が $500$ 個となる. 以上より, 求める最小値は $500$ である.

工事中

一般に学生が $n~(\geqq 5)$ 人であるとする. このとき, 求める最小値は, 以下で定まる $f(n)$ で与えられる. \[ f(n)=\begin{cases} n(n-4)/8 & n\equiv 0 \pmod 4 \\ (n-1)(n-3)/8 & n\equiv 1,3 \pmod 4 \\ (n-2)^2/8 & n\equiv 2 \pmod 4 \\ \end{cases} \] これを $n$ についての帰納法で示す. $n=5$ のとき明らかであるから, ある $k\geqq 6$ について $n=k-1$ で成立を仮定する.

$n=k$ 人の生徒に $1,\ldots,k$ の番号を振る. このとき, 相異なる $i,j$ について, 生徒 $i$ と $j$ が会話したとき $E(i,j)=1$, そうでないとき $E(i,j)=0$ とおく. また, $S=\{1,2,\dots,k\}, S_m=S-\{m\}$と定める. いま \[\sum_{i,j\in S,~ i\lt j}E(i,j) = \frac{1}{k-2}\sum_{m\in S} \sum_{i,j\in S_m,~ i\lt j}E(i,j) \geqq \frac{1}{k-2}\sum_m f(k-1)=\frac{k}{k-2}f(k-1)\] ここで $\left\lceil \frac{k}{k-2}f(k-1) \right\rceil=f(k)$ が証明できるから, 上式の左辺は $f(k)$ で下から抑えられる.

逆に, 実際に $f(k)$ にできることを示せばよい. $k$ を $4$ で割った余りが $r$ であるとき, $\lfloor \frac{k}4\rfloor+1$ 人のグループを $r$ 個, $\lfloor \frac{k}4\rfloor$ 人のグループを $4-r$ 個, 合計 $4$ つのグループを作る. $2$ 人が同じグループであるとき, かつそのときに限り両者が会話すると, これは条件をみたし, かつ会話をする組が $f(k)$ 個であることが容易に確かめられる.

以上より求める最小値が $f(n)$ で与えられることが示され, 特に $f(25)=66$ である.

工事中

男子と女子の人数が等しいことは明らかである. 男子, 女子の集合をそれぞれ $\{b_1,\dots,b_m\},\{g_1,\dots,g_m\}$ とし, 女子 $i$ と女子 $j$ の共通の知り合いである男子が $K(i,j)$ 人いるとする.

まず組 $(b_i,b_j,g_p,g_q)$ であって, $b_i$ と $g_p$, $b_i$ と $g_q$, $b_j$ と $g_p$, $b_j$ と $g_q$ がすべて知り合いであるようなものの数を数える. 任意に男子を $2$ 人選んだとき, その共通の知り合いである女子は $k$ 人であるので, そのような組の数は \[{}_m{\rm P}_2 \cdot {}_k{\rm P}_2=m(m-1)k(k-1)\] である. 一方, 任意に女子を $2$ 人選んだとき, 同様に考えるとそのような組の数は \[\sum_{1\leq p, q\leq m} {}_{K(p,q)}{\rm P}_2=\sum_{1\leq p, q\leq m} K(p,q)(K(p,q)-1)\] となる. これらは等しいため \[m(m-1)k(k-1)=\sum_{1\leq p, q\leq m} K(p,q)(K(p,q)-1)\] 　次に, 組 $(b_i,b_j,g_p,g_q)$ であって, $b_i$ と $g_p$, $b_j$ と $g_p$, $b_j$ と $g_q$ は知り合いだが, $b_i$ と $g_q$ は知り合いでないものの数を数える. 上と同様にして $2$ 通りの数え方をすることで, \[m(m-1)k(n-k)=\sum _{1\leq p, q\leq m} K(p,q)(n-K(p,q))\] 　両式を連立すると \[\sum _{1\leq p, q\leq m} K(p,q)=m(m-1)k,\quad \sum _{1\leq p, q\leq m} K(p,q)^2=m(m-1)k^2\] よって \[\sum _{1\leq p\lt q\leq m} (K(p,q)-k)^2=0\] より, 任意の $p,q$ について $K(p,q)=k$ であることが示された.

別解1.　組 $\{g_p,b_q,b_r\}$ であって, $g_p$ と $b_q$, $g_p$ と $b_r$がともに知り合いであるものの個数を $2$ 通りに数えることで \[ m\cdot \frac{n(n-1)}2=\frac{m(m-1)}2\cdot k \implies n^2-km=n-k\] を得る. $m$ 次正方行列 $U=(u_{ij})$ を次のように定める： \[u_{ij}= \begin{cases} \cfrac{m-n+\sqrt{n-k}}{m\sqrt{n-k}} & (\text{男子}~i~\text{と女子}~j~\text{が知り合い}) \\ \cfrac{-n+\sqrt{n-k}}{m\sqrt{n-k}} & (\text{otherwise}) \end{cases}\] このとき, $U$ の行ベクトルが正規直交基底をなすことが確認できる. すなわち $U$ はユニタリ行列であり, 列ベクトルも正規直交基底をなすので, 結論を得る.

別解2.　男子と女子の人数は等しいから, これを $x$ とおく. $n=k$ のとき, $x=n$ でありすべての男女は知り合いであるから, 以下 $n\gt k$ とする. $x\times x$ の単位行列を $E$, すべての成分が $1$ の $x\times x$ 行列を $I$ とおく. $i$ 人目の男子と $j$ 人目の女子が知り合いのとき $a_{ij}=1$, それ以外のとき $a_{ij}=0$ とすることで正方行列 $A$ を構成すると, 各条件より \[AA^{\top}=kI+(n-k)E\] が従う (これを $T$ とおく). $x$ 本の列ベクトルの一次独立性より $T$ は正則で, 特に $A$ も正則である. また一つ目の条件より $AI=IA=nI$ であり, $AE=EA=A$ とあわせて $AT=TA$ が従う. よって\[A^{\top}A=A^{-1}TA=T\]であり, これが示すべきことであった.

工事中

三角形 $ABC$ の外接円を $\Omega$ とし, その半径を $r$ とする. また, 三角形 $ABC$ の $\angle B, \angle C$ 内の傍心をそれぞれ $I_B,I_C$ とし, $\Omega$ と直線 $DE$ の交点を $X,Y$ とする. ただし $X,D,E,Y$ がこの順に並ぶとする.

まず, $5$ 点 $I_B,X,I,Y,I_C$ が同一円周上にあることを示す. $\angle ICI_B=\angle IAI_B=90^\circ$ より $4$ 点 $I,C,I_B,A$ は同一円周上にあるので, 方べきの定理より $DX\cdot DY=DA\cdot DC=DI\cdot DI_B$ が従う. よって $I_B,X,I,Y$ は同一円周上にあり, 同様に $I_C,Y,I,X$ も同一円周上にある. 以上より所望の共円が示された. これを $\Omega’$ とし, その中心を $O’$ とする.

$\Omega$ は三角形 $I_AI_BI_C$ の九点円であるから, 線分 $I_AI,I_AI_B,I_AI_C$ の中点を通る. よって $\Omega’$ は $\Omega$ を点 $I_A$ を中心に $2$ 倍に拡大したものであり, $\Omega’$ の半径は $2r$ である. また $OO’=OI_A$ である. 三角形 $O’XY$ は一辺が $2r$ の正三角形であり, $O$ は線分 $XY$ の中点であるから $OO’=\sqrt 3 r$ である. よって $OI_A=\sqrt 3 r$ であり, $OI_A/OA=\sqrt 3$ である.

工事中

Gaussの補題より $P(x)=Q(x)^2R(x)$ と表せる. ただし, $Q(x)\in \mathbb{Z}[x]$, $R(x)$ は $1$ または相異なる既約な整数係数多項式の積である. $P(n)$ が平方数となるとき $R(n)$ も平方数となるので, 任意の $n$ について $R(n)$ は平方数である.

以下, $R(x)$ が定数でないとして矛盾を導けばよい.

補題2よりある $A_\ast(x),B_\ast(x)\in \mathbb{Q}[x]$ が存在して $A_\ast(x)R(x)+B_\ast(x)R’(x)=1$ となり, ある正の整数 $D$ によって $A(x)=DA_\ast(x)\in \mathbb{Z}[x],B(x)=DB_\ast(x)\in \mathbb{Z}[x]$ とできる. よって\[A(x)R(x)+B(x)R’(x)=D\]となる. また補題1における素数 $p$ のうち, $D$ を割りきらないものが存在するから, これを適当に $q$ とする. $q\mid R(n_q)$となるような正の整数 $n_q$ をとるとき, 補題3より $q\mid R’(n_q)$である. しかし, これは\[A(n_q)R(n_q)+B(n_q)R’(n_q)=D\] に矛盾する (左辺は $q$ の倍数だが, 右辺は $q$ の倍数でない). したがって, $R(x)$が定数であることが示された.

工事中