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 本がサニーであること。
ステップ 1/6: 禁止される方向はわずか3つ
ざっくり言うと

非サニーな直線はちょうど3つの方向のいずれかに平行なので、三角形格子の3辺は自動的に非サニーとなる。

n≥4 ⟹ 2n≥3(n−1) fails, so a long line is forcedn\ge4\ \Longrightarrow\ 2n\ge3(n-1)\ \text{fails, so a long line is forced}
詳しい解説

三角形格子 {(a,b):a,b≥1,a+b≤n+1}\{(a,b): a,b\ge1, a+b\le n+1\} の3辺(a=1a=1、b=1b=1、a+b=n+1a+b=n+1 上にあり、まさに禁止された3方向)のいずれかの上の nn 点すべてを通る直線を長い直線と呼ぶ。外周には 3(n−1)3(n-1) 個の点があり、nn 本のうち長い直線が1本もなければ各直線は外周と高々22点で交わるので 2n≥3(n−1)2n\ge3(n-1) となり n≤3n\le3 が強制される。したがって n≥4n\ge4 では条件を満たす nn 本の直線族は必ず長い直線を含む。