0

EGMO日本代表一次選抜2023

640
0
$$$$

解答

出典は ここらへん から.

$p\leqq q$をみたす素数の組$(p,q)$であって,$\dfrac{p^2-3pq+q^2}{p+q}$が整数となるようなものをすべて求めよ.

解答$p< q$の時,
$$p+q\mid p^2-3pq+q^2\Longleftrightarrow p+q\mid 5pq\Longleftrightarrow p+q\mid5\Longleftrightarrow p=2,q=3$$
$p=q$の時,
$$p+q\mid p^2-3pq+q^2\Longleftrightarrow 2\mid p\Longleftrightarrow p=q=2$$
よって,$(p,q)=(2,2),(2,3)$
コメント偶奇とか見てもいけますね.私は,gcdを見て,Euclidの補題を用いて変形しました.

鋭角三角形$ABC$があり,その垂心を$H$とする.三角形$AHB$の外接円,三角形$AHC$の外接円上にそれぞれ$H$と異なる点$P,Q$を,$3$$P,H,Q$がこの順に同一直線上にあるようにとる.このとき,ある円$\omega$が存在し,$P,Q$のとり方によらず線分$PQ$の中点が$\omega$上にあることを示せ.

解答線分$PQ$の中点を$R$とする.有名事実として,$\angle ACH=\angle ABH$.また,円周角の定理より,
$$\angle APH=\angle ABH=\angle ACH=\angle AQH$$
なので、$\triangle APQ$は二等辺三角形.したがって,$AR\perp PQ$が成り立ち,$R$は常に線分$AH$を直径とする円周上にある.

$n$$2$以上の整数とする.$n^2$枚のカード(カード$1$,カード$2$,$\dots$,カード$n^2$)があり,$1$以上$n^2$以下の整数$i$について,カード$i$には$\left\lceil\dfrac{n^2}{i}\right\rceil$が書かれている.$n\times n$のマス目の各マスに$1$枚ずつカードを置く方法であって,次の条件をみたすものが存在するような$n$をすべて求めよ.

辺を共有して隣りあうどの$2$マスについても,その$2$マスに置いたカードに書かれている$2$つの整数は互いに素である.

解答$i$$j$列目のマス目を$C_{i,j}$で表し,カードを置くという操作を,カードに書かれた数をマス目に直接書くという操作に置き換えて考える.$n=3$のみであることを示す.まず,$n=3$の時次のようにすればいい.
!FORMULA[51][36584004][0] $n=3$
$2$以上の整数$n$に対して,"$n\times n$のマス目に条件をみたしながら偶数を$K$個書くことができる"をみたす最大の整数$K$$a_n$とする.このとき,以下が成立する.$$a_n\leqslant\left\lceil\frac{n^2}{2}\right\rceil$$
$n$が偶数の時,$n\times n$マスを$C_{2i-1,2i-1},C_{2i-1,2i},C_{2i,2i-1},C_{2i,2i}\ (i=1,\cdots,\frac{n}{2})$$1$マスとした新たなマス目$\frac{n}{2}\times\frac{n}{2}$を考える.$\left(\frac{n}{2}\right)^2$個の$2\times2$マスには高々$2$個しか偶数が書けないから,$$a_n\leqslant\frac{n^2}{2}=\left\lceil\frac{n^2}{2}\right\rceil.$$
$n$が奇数の時,$2n-1$個の$C_{1,1},C_{1,2},\cdots,C_{1,n},C_{2,1},\cdots,C_{n,1}$には,高々$n$個しか偶数が書けないから,$$a_n\leqslant n+\frac{(n-1)^2}{2}=\frac{n^2+1}{2}=\left\lceil\frac{n^2}{2}\right\rceil.$$
後は,$n\ne3$の時に,(偶数が書かれたカードの枚数)$>a_n$を示せばいい.

$2$が書かれたカードは$\left\lfloor \frac{n^2}{2}\right\rfloor$枚ある.
$$\left\lceil\frac{n^2}{i}\right\rceil=2\Longleftrightarrow\left\lceil\frac{n^2}{2}\right\rceil\leqslant i \leqslant n^2-1$$
より明らか.
$4$が書かれたカードは$\left\lceil\frac{n^2}{3}\right\rceil-\left\lceil\frac{n^2}{4}\right\rceil$枚ある.
$$\left\lceil\frac{n^2}{i}\right\rceil=4\Longleftrightarrow \left\lceil\frac{n^2}{4}\right\rceil\leqslant i\leqslant\left\lceil\frac{n^2}{3}\right\rceil-1$$
より明らか.


$\textbf{Case 1.}$$n$が偶数のとき
偶数$n^2>2$が書かれたカードが存在するので,補題$1,2$より,
$$\text{(偶数の書かれたカードの枚数)}\geqslant\left\lfloor \frac{n^2}{2}\right\rfloor+1=\left\lceil \frac{n^2}{2}\right\rceil+1>\left\lceil\frac{n^2}{2}\right\rceil\geqslant a_n.$$

$\textbf{Case 2.}$$n$が奇数のとき$(n\geqslant5)$
$$\left\lceil\frac{n^2}{3}\right\rceil-\left\lceil\frac{n^2}{4}\right\rceil=\left\lceil\frac{n^2-9}{12}\right\rceil\geqslant\left\lceil\frac{16}{12}\right\rceil=2$$
と,補題$1,2,3$より,
$$\text{(偶数の書かれたカードの枚数)}\geqslant\left\lfloor \frac{n^2}{2}\right\rfloor+\left\lceil\frac{n^2}{3}\right\rceil-\left\lceil\frac{n^2}{4}\right\rceil\geqslant\left\lfloor \frac{n^2}{2}\right\rfloor+2=\left\lceil \frac{n^2}{2}\right\rceil+1>\left\lceil \frac{n^2}{2}\right\rceil\geqslant a_n.$$

コメント補題に気づけばやるだけだと思います.

正の実数からなる数列$a_1,a_2,...$は,任意の正の整数$n$に対して
\begin{equation} a_{n+1}=a_n\cdot\lfloor a_{n+2}\rfloor\tag{$*$} \end{equation}
をみたしている.このとき,任意の正の整数$n$について$a_n=a_1$が成り立つことを示せ.

解答数列$\{b_i\}_{i\in\mathbb Z_{>0}}$$b_1=1,b_{n+1}=\frac{a_{n+1}}{a_n}\ (n>0)$で定め,数列$\{c_i\}_{i\in\mathbb Z_{>0}}$$c_n=\displaystyle\prod_{i=1}^nb_i$で定める.このとき,$(*)$は次のように書ける(以下$n$は任意の$  2$以上の整数を動くものとする):
\begin{equation} b_{n}=\lfloor c_{n+1}a_1\rfloor\tag{$**$} \end{equation}
$b_{n}\in\mathbb Z_{\geqslant0}$かつ$b_n>0$を合わせると,$b_n\geqslant1\ (1)$.$(**)$より,
$$b_{n}=\lfloor c_{n}a_1\rfloor\leqslant c_{n}a_1.$$
これと$(1)$より,
$$b_{n+1}\geqslant \lfloor b_{n}b_{n+2}\rfloor=b_{n}b_{n+2}\geqslant b_{n}$$
が成り立ち,
\begin{equation} b_{n+1}\geqslant b_{n}b_{n+2}\geqslant b_{n}b_{n+1} \Longrightarrow b_{n}\leqslant1\tag{2} \end{equation}
$(1),(2)$と合わせて,$b_n=1$並びに$c_n=1$.よって,$a_n=c_na_1=a_1$.

$10\times10$のマス目があり,そのうちいくつかのマスが黒く,残りのマスが白く塗られている.次の$2$つ条件のうち少なくとも$1$つをみたすような白いマスを$1$つ選び,黒く塗りなおす操作を考える.

  • 1つ上のマスと1つ下のマスがともに存在し,いずれも黒いマスである.
  • 1つ左のマスと1つ右のマスがともに存在し,いずれも黒いマスである.
操作を何回か行ってすべてのマスを黒いマスにできるとき,はじめに黒く塗られているマスの個数としてありうる最小の値を求めよ.

解答$i$$j$列目のマス目を$C_{i,j}$で表し,求める値を$m$とおく.また,有限回の操作によって,すべてのマスを黒くできるような塗り方を,いい塗り方と呼ぶこととする.$m=36$であることを示す.まず,以下より$m\leqslant36$が分かる.
!FORMULA[127][1603104248][0] $m\leqslant36$
あとは,$m\geqslant36$を示せばいい.まず,いい塗り方であれば,$C_{1,1},C_{1,10},C_{10,1},C_{10,10}$の4つは黒で塗られていないといけず,端の$4$つの$1\times10 \ (10\times1)$マスにはそれぞれ6つは黒で塗られている必要がある.なぜなら,白で塗られたマスが隣り合ってはいけないから.よって,(いい塗り方なら)端の$36$マスで,$6\cdot4-4=20$個のマスが黒で塗られている必要がある.次に,内側の$8\times8$マスについて考える.この$8\times8$マスは$16$個の$2\times2$が集まったものと見ることができる.また,いい塗り方ならば,すべてのマスが白で塗られている$2\times2$マスは存在しない.もし,存在したとすると,$4$つのうち初めて黒で塗られるマスが存在するが,塗られる直前に残った$3$つのうち隣り合う$2$つのいずれかが黒で塗られている必要があり,これは最速性に反する.よって,(いい塗り方なら)内側の$8\times8$マスで,$16$個のマスが黒で塗られている必要がある.したがって,$m\geqslant20+16=36$.

コメント実験すると,$C_{3,3}$とかが黒だと$3$つ一気に減らせて一番よさそうだなと気づけます.

まとめ

今回は$40$点満点の$28$点がボーダーで,少し簡単だったかなという印象です.これと言って,難しいものもなかったように思いました.私は$3$番の問題が好きです.

投稿日:2023124

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

kk2
kk2
53
6779
2006年に生まれました

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中