第4問

正の奇数

n

を固定する。座標平面上に相異なる

m+2

点

P_0,P_1,\ldots,P_{m+1}

を取り、(1)

P_0=(0,1)

、

P_{m+1}=(n+1,n)

、

1\le i\le m

では

P_i

の両座標が

1

以上

n

以下の整数、(2)

0\le i\le m

で線分

P_iP_{i+1}

は

i

が偶数なら

x

軸に平行、奇数なら

y

軸に平行、(3)

0\le i<j\le m

で二線分の共通点は高々一つ、とする。

m

の最大値を求めよ。

i

P_iP_{i+1}

P_jP_{j+1}

ステップ 4/5: 帰納的構成

(n-4)(n-5)+n^2-(n-4)^2-4=n(n-1)

詳しい解説

この手順では仮定と式 $n\ge5$ 、 $n-4$ 、 $(n-4)\times(n-4)$ 、 $(n,2),(n-1,n-2),(2,3),(1,n-1)$ を用いて、示された結論を導く。