第1問

平面上の直線は、

x

軸、

y

軸、直線

x+y=0

のいずれとも平行でないとき、サニーな直線と呼ばれる。

n\ge3

を与えられた整数とする。次の2条件を同時に満たす平面上の

n

本の相異なる直線が存在するような、非負整数

k

をすべて求めよ:

a+b\le n+1

を満たすすべての正の整数

a

と

b

に対し、点

(a,b)

がそれらの直線の少なくとも1本の上にあること;そして、その

n

本のうちちょうど

k

本がサニーであること。

ステップ 3/6: 長い直線がある場合:k = 0 または k = 1

前のステップ次のステップ

n=3:\quad \{(1,1),(1,2),(1,3),(2,1),(2,2),(3,1)\},\ \ 1+2+3=6\ \text{points}

詳しい解説

$n=3$ の格子は上記の $6$ 点をもつ。 $3$ 本のうち1本が長い直線(1辺上の $3$ 点を通る)なら、残る $3$ 点は他の $2$ 本で覆わねばならない。そのうち一方は残り $3$ 点のうち少なくとも $2$ 点を通ることになり、この配列の2格子点を通る直線は常に禁止された3方向のいずれかに平行なので非サニーである;最後の直線は残った1点だけを覆い、サニーでもそうでなくてもよい。よってこの場合はちょうど $k=0$ または $k=1$ 本のサニーな直線を与える。