问题及解答

平面 $\mathbb{R}^2$ 中坐标均为整数的点称为整点(或格点), 它们组成的集合称为格(lattice).

两个格点 $(a,b)$ 与 $(c,d)$ 是互相可见的, 如果连接它们的线段不包含其他格点.

假设 $\Delta_n=\{(x,y)\mid 0\leq x\leq n-1, 0\leq y\leq n-1, x,y\in\mathbb{Z}\}$.

请构思这样的一个小程序,

首先显示 $\Delta_n$ 中的所有格点,

(1) 点击 $\Delta_n$ 中的某个点 $p$, 即显示 $p$ 的所有可见点, 并用虚线连接.

(2) 点击 $\Delta_n$ 中的某个点 $p$, 将 $p$ 的所有可见点消除.

[Def] 设 $M,N\subset\Delta_n$, 称 $M$ 可从 $N$ 看见, 或 $N$ 中的点可以直达 $M$, 如果对于 $M$ 中的任一点, 都存在 $N$ 中的某一点看到它.

令

\[f(n)=\min\{|M|\mid \Delta_n\ \text{可被}\ M\ \text{看见}\}\]

这里 $|M|$ 指 $M$ 中点的个数, 尝试编程求 $f(n)$ 的值.

 H.L. ABBOTT 于 1974 年证明了 $f(n)$ 满足如下不等式

\[
\frac{\log n}{2\log\log n}<f(n)<4\log n.
\]

References:

H.L. ABBOTT, Some results in combinatorial geometry. Discrete Mathematics, 9 (1974) 199-204.