MathLabs

第1問

平面上の直線は、xx 軸、yy 軸、直線 x+y=0x+y=0 のいずれとも平行でないとき、サニーな直線と呼ばれる。n≥3n\ge3 を与えられた整数とする。次の2条件を同時に満たす平面上の nn 本の相異なる直線が存在するような、非負整数 kk をすべて求めよ:a+b≤n+1a+b\le n+1 を満たすすべての正の整数 aa と bb に対し、点 (a,b)(a,b) がそれらの直線の少なくとも1本の上にあること;そして、その nn 本のうちちょうど kk 本がサニーであること。
ステップ 2/6: サニーな本数を変えずに n = 3 に帰着
n ⟶ n−1 by deleting a long line, same count of sunny linesn\ \longrightarrow\ n-1\ \text{by deleting a long line, same count of sunny lines}
詳しい解説

長い直線は決してサニーではないので、それを削除すると非サニーな直線が1本減り、残った n−1n-1 本は n−1n-1 に対応するより小さな三角形格子(残る点はまさに a+b≤na+b\le n)をちょうど覆い、サニーな本数 kk は変わらない。この削除を繰り返せば、n≥3n\ge3 の任意の有効な配置は同じ kk を保ったまま n=3n=3 の配置に帰着する;逆に n=3n=3 の配置から新しい長い直線 a+b=n+1a+b=n+1(場合により a=1a=1 や b=1b=1)を追加すれば kk を変えずに任意の n≥3n\ge3 まで戻れる。したがって n=3n=3 に対して kk を分類すればよい。