EGMO日本代表一次選抜2023

964

解答

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

解答

p < q

の時,

p + q ∣ p^{2} - 3 p q + q^{2} ⟺ p + q ∣ 5 p q ⟺ p + q ∣ 5 ⟺ p = 2, q = 3

p = q

の時,

p + q ∣ p^{2} - 3 p q + q^{2} ⟺ 2 ∣ p ⟺ p = q = 2

よって,

(p, q) = (2, 2), (2, 3)

偶奇とか見てもいけますね.私は,gcdを見て,Euclidの補題を用いて変形しました.

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

解答

線分

P Q

の中点を

R

とする.有名事実として,

∠ A C H = ∠ A B H

.また,円周角の定理より,

∠ A P H = ∠ A B H = ∠ A C H = ∠ A Q H

なので、

△ A P Q

は二等辺三角形.したがって,

A R ⊥ P Q

が成り立ち,

R

は常に線分

A H

を直径とする円周上にある.

$n$ を $2$ 以上の整数とする. $n^{2}$ 枚のカード(カード $1$ ,カード $2$ , $\dots$ ,カード $n^{2}$ )があり, $1$ 以上 $n^{2}$ 以下の整数 $i$ について,カード $i$ には $⌈ \frac{n^{2}}{i} ⌉$ が書かれている. $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} ⩽ ⌈ \frac{n^{2}}{2} ⌉

n

が偶数の時,

n \times n

マスを

C_{2 i - 1, 2 i - 1}, C_{2 i - 1, 2 i}, C_{2 i, 2 i - 1}, C_{2 i, 2 i} (i = 1, \dots, \frac{n}{2})

を

1

マスとした新たなマス目

\frac{n}{2} \times \frac{n}{2}

を考える.

{(\frac{n}{2})}^{2}

個の

2 \times 2

マスには高々

2

個しか偶数が書けないから,

a_{n} ⩽ \frac{n^{2}}{2} = ⌈ \frac{n^{2}}{2} ⌉ .

n

が奇数の時,

2 n - 1

個の

C_{1, 1}, C_{1, 2}, \dots, C_{1, n}, C_{2, 1}, \dots, C_{n, 1}

には,高々

n

個しか偶数が書けないから,

a_{n} ⩽ n + \frac{(n - 1)^{2}}{2} = \frac{n^{2} + 1}{2} = ⌈ \frac{n^{2}}{2} ⌉ .

後は,

n \neq 3

の時に,(偶数が書かれたカードの枚数)

> a_{n}

を示せばいい.

2

が書かれたカードは

⌊ \frac{n^{2}}{2} ⌋

枚ある.

⌈ \frac{n^{2}}{i} ⌉ = 2 ⟺ ⌈ \frac{n^{2}}{2} ⌉ ⩽ i ⩽ n^{2} - 1

より明らか.

4

が書かれたカードは

⌈ \frac{n^{2}}{3} ⌉ - ⌈ \frac{n^{2}}{4} ⌉

枚ある.

⌈ \frac{n^{2}}{i} ⌉ = 4 ⟺ ⌈ \frac{n^{2}}{4} ⌉ ⩽ i ⩽ ⌈ \frac{n^{2}}{3} ⌉ - 1

より明らか.

Case 1.

n

が偶数のとき
偶数

n^{2} > 2

が書かれたカードが存在するので,補題

1, 2

より,

(偶数の書かれたカードの枚数) ⩾ ⌊ \frac{n^{2}}{2} ⌋ + 1 = ⌈ \frac{n^{2}}{2} ⌉ + 1 > ⌈ \frac{n^{2}}{2} ⌉ ⩾ a_{n} .

Case 2.

n

が奇数のとき

(n ⩾ 5)

⌈ \frac{n^{2}}{3} ⌉ - ⌈ \frac{n^{2}}{4} ⌉ = ⌈ \frac{n^{2} - 9}{12} ⌉ ⩾ ⌈ \frac{16}{12} ⌉ = 2

と,補題

1, 2, 3

より,

(偶数の書かれたカードの枚数) ⩾ ⌊ \frac{n^{2}}{2} ⌋ + ⌈ \frac{n^{2}}{3} ⌉ - ⌈ \frac{n^{2}}{4} ⌉ ⩾ ⌊ \frac{n^{2}}{2} ⌋ + 2 = ⌈ \frac{n^{2}}{2} ⌉ + 1 > ⌈ \frac{n^{2}}{2} ⌉ ⩾ a_{n} .

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

正の実数からなる数列 $a_{1}, a_{2}, . . .$ は,任意の正の整数 $n$ に対して
$\begin{matrix} (*) & a_{n + 1} = a_{n} \cdot ⌊ a_{n + 2} ⌋ \end{matrix}$
をみたしている.このとき,任意の正の整数 $n$ について $a_{n} = a_{1}$ が成り立つことを示せ.

解答

数列

{b_{i}}_{i \in Z_{> 0}}

を

b_{1} = 1, b_{n + 1} = \frac{a_{n + 1}}{a_{n}} (n > 0)

で定め,数列

{c_{i}}_{i \in Z_{> 0}}

を

c_{n} = \prod_{i = 1}^{n} b_{i}

で定める.このとき,

(*)

は次のように書ける(以下

n

は任意の

2

以上の整数を動くものとする):

\begin{matrix} (* *) & b_{n} = ⌊ c_{n + 1} a_{1} ⌋ \end{matrix}

b_{n} \in Z_{⩾ 0}

かつ

b_{n} > 0

を合わせると,

b_{n} ⩾ 1 (1)

(* *)

より,

b_{n} = ⌊ c_{n} a_{1} ⌋ ⩽ c_{n} a_{1} .

これと

(1)

より,

b_{n + 1} ⩾ ⌊ b_{n} b_{n + 2} ⌋ = b_{n} b_{n + 2} ⩾ b_{n}

が成り立ち,

\begin{matrix} (2) & b_{n + 1} ⩾ b_{n} b_{n + 2} ⩾ b_{n} b_{n + 1} ⟹ b_{n} ⩽ 1 \end{matrix}

(1), (2)

と合わせて,

b_{n} = 1

並びに

c_{n} = 1

.よって,

a_{n} = c_{n} a_{1} = a_{1}

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

1つ上のマスと1つ下のマスがともに存在し,いずれも黒いマスである.
1つ左のマスと1つ右のマスがともに存在し,いずれも黒いマスである.

操作を何回か行ってすべてのマスを黒いマスにできるとき,はじめに黒く塗られているマスの個数としてありうる最小の値を求めよ.

解答

i

行

j

列目のマス目を

C_{i, j}

で表し,求める値を

m

とおく.また,有限回の操作によって,すべてのマスを黒くできるような塗り方を,いい塗り方と呼ぶこととする.

m = 36

であることを示す.まず,以下より

m ⩽ 36

が分かる.

m ⩽ 36

あとは,

m ⩾ 36

を示せばいい.まず,いい塗り方であれば,

C_{1, 1}, C_{1, 10}, C_{10, 1}, C_{10, 10}

の4つは黒で塗られていないといけず,端の

4

つの

1 \times 10 (10 \times 1)

マスにはそれぞれ6つは黒で塗られている必要がある.なぜなら,白で塗られたマスが隣り合ってはいけないから.よって,(いい塗り方なら)端の

36

マスで,

6 \cdot 4 - 4 = 20

個のマスが黒で塗られている必要がある.次に,内側の

8 \times 8

マスについて考える.この

8 \times 8

マスは

16

個の

2 \times 2

が集まったものと見ることができる.また,いい塗り方ならば,すべてのマスが白で塗られている

2 \times 2

マスは存在しない.もし,存在したとすると,

4

つのうち初めて黒で塗られるマスが存在するが,塗られる直前に残った

3

つのうち隣り合う

2

つのいずれかが黒で塗られている必要があり,これは最速性に反する.よって,(いい塗り方なら)内側の

8 \times 8

マスで,

16

個のマスが黒で塗られている必要がある.したがって,

m ⩾ 20 + 16 = 36

実験すると,

C_{3, 3}

とかが黒だと

3

つ一気に減らせて一番よさそうだなと気づけます.

まとめ

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

投稿日：2023年1月24日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

kk2

9009

2006年に生まれました

他の人のコメント

コメントはありません。

読み込み中

kk2

EGMO日本代表一次選抜2023

解答
まとめ