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

工事中

工事中

工事中

$x\geqq 6$ のとき, $mod64$ と $mod17$ を観察することで解が存在しないことがわかる.

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

工事中

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

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

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

工事中

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

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

以上より, $\mathrm{\angle }PXD=\mathrm{\angle }O{D}^{\prime }D=\mathrm{\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),\dots ,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)<2(i+1)$ となるため, $f^{n+ik}(m)>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$ が円 $\mathrm{\Gamma }$ の直径となるような点とする. $$DB=EC,QB=QC,\mathrm{\angle }QBD=\mathrm{\angle }QCE$$ より $\mathrm{△}QDB\equiv \mathrm{△}QCE$. よって $\mathrm{\angle }QDA=\mathrm{\angle }QEA$ より $4$ 点 $A,D,E,Q$ は同一円周上に存在する. したがって $$\mathrm{\angle }QEF=\mathrm{\angle }QAB=\mathrm{\angle }QCF$$ となり, $4$ 点 $Q,E,C,F$ も同一円周上に存在する. これを用いると, $$\mathrm{\angle }QFE=\mathrm{\angle }QCA=\mathrm{\angle }QPA$$ が分かり, これと $AP\parallel DE$ より $Q,P,F$ が同一直線上にあることが分かる. したがって, $$\mathrm{\angle }NPF={180}^{\circ }-\mathrm{\angle }QPN={90}^{\circ }$$ また, $\mathrm{\angle }NMF=\mathrm{\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}^{\mathrm{\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}^{\mathrm{\infty }}\sum _{j=0}^{\mathrm{\infty }}{r}_{i+j}{p}^j=\sum _{i=1}^{\mathrm{\infty }}\sum _{j=0}^{\mathrm{\infty }}{r}_j{p}^{j-i}-\sum _{i=1}^{\mathrm{\infty }}\sum _{j=0}^{\mathrm{\infty }}{r}_j{p}^{-i}=\frac{n}{p-1}-\frac{1}{p-1}\sum _{j=0}^{\mathrm{\infty }}{r}_j$$ 以上より, $$\frac{1}{p-1}\sum _{j=0}^{\mathrm{\infty }}{r}_j=\frac{n}{p-1}-\lceil \frac{n}{p-1}\rceil +1\le 1⟹\sum _{j=0}^{\mathrm{\infty }}{r}_j\le p-1$$ つまり, $n$ を $p$ 進数で表したときの各桁の和が $p-1$ 以下になる.

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

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

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

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

工事中

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

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

工事中

三角形 $P_i{P}_j{P}_k$ であって, $3$ 辺が同じ色である三角形を良い三角形, そうでない三角形を悪い三角形とよぶ. また, 相異なる $3$ 点の順序付きの組 $(P_i,P_j,P_k)$ であって, 辺 $P_i{P}_j,P_j{P}_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$ 本出ているとき, $(\ast ,P,\ast \ast )$ の形のすごい組は $n(24-n)\leqq 144$ 個であるため, 全体ですごい組は $3600$ 個以下である. よって悪い三角形は $1800$ 個以下であるから, 良い三角形は少なくとも ${}_{25}{\mathrm{C}}_3-1800=500$ 個ある.

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

工事中

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

$n=k$ 人の生徒に $1,\dots ,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<j}E(i,j)=\frac{1}{k-2}\sum _{m\in S}\sum _{i,j\in S_m,i<j}E(i,j)\geqq \frac{1}{k-2}\sum _{m}f(k-1)=\frac{k}{k-2}f(k-1)$$ ここで $\lceil \frac{k}{k-2}f(k-1)\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{\mathrm{P}}_2\cdot {}_k{\mathrm{P}}_2=m(m-1)k(k-1)$$ である. 一方, 任意に女子を $2$ 人選んだとき, 同様に考えるとそのような組の数は $$\sum _{1\le p,q\le m}{}_{K(p,q)}{\mathrm{P}}_2=\sum _{1\le p,q\le m}K(p,q)(K(p,q)-1)$$ となる. これらは等しいため $$m(m-1)k(k-1)=\sum _{1\le p,q\le 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\le p,q\le m}K(p,q)(n-K(p,q))$$ 　両式を連立すると $$\sum _{1\le p,q\le m}K(p,q)=m(m-1)k,\sum _{1\le p,q\le m}K(p,q{)}^2=m(m-1)k^2$$ よって $$\sum _{1\le p<q\le 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⟹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>k$ とする. $x\times x$ の単位行列を $E$, すべての成分が $1$ の $x\times x$ 行列を $I$ とおく. $i$ 人目の男子と $j$ 人目の女子が知り合いのとき $a_{ij}=1$, それ以外のとき $a_{ij}=0$ とすることで正方行列 $A$ を構成すると, 各条件より $$A{A}^{\mathrm{\top }}=kI+(n-k)E$$ が従う (これを $T$ とおく). $x$ 本の列ベクトルの一次独立性より $T$ は正則で, 特に $A$ も正則である. また一つ目の条件より $AI=IA=nI$ であり, $AE=EA=A$ とあわせて $AT=TA$ が従う. よって$$A^{\mathrm{\top }}A=A^{-1}TA=T$$であり, これが示すべきことであった.

工事中

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

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

$\mathrm{\Omega }$ は三角形 $I_A{I}_B{I}_C$ の九点円であるから, 線分 $I_{A}I,I_A{I}_B,I_A{I}_C$ の中点を通る. よって ${\mathrm{\Omega }}^{\prime }$ は $\mathrm{\Omega }$ を点 $I_A$ を中心に $2$ 倍に拡大したものであり, ${\mathrm{\Omega }}^{\prime }$ の半径は $2r$ である. また $O{O}^{\prime }=O{I}_A$ である. 三角形 $O^{\prime }XY$ は一辺が $2r$ の正三角形であり, $O$ は線分 $XY$ の中点であるから $O{O}^{\prime }=\sqrt{3}r$ である. よって $O{I}_A=\sqrt{3}r$ であり, $O{I}_A/OA=\sqrt{3}$ である.

工事中

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

工事中