穿越格子最多的直线
在 \(n\times n\) 的方格本内画一条直线，最多能穿越几个格子？注：所谓穿过格子，指经过格子的内点。仅经过格子角上或者边界上的点不算数。
以前有讨论过这个问题吗？ 取一条对角线（穿越 \(n\) 个方格），
再将之略微平移很小的距离（新增 \((n-1)\) 个方格），
则可穿越 \((2n-1)\) 个方格，不知是否达到了最多？ 本帖最后由 hejoseph 于 2017-9-7 19:53 编辑
如果是 $m\times n$ 的方格结果又如何？$m+n-1$
如果是 $l\times m\times n$ 的长方体呢？$l+m+n-2$ 假设直线是向右上方延伸，那么触碰到的格子只能向右或者向上增加。 本帖最后由 咻咻 于 2017-9-13 14:58 编辑
考虑该直线L与网格线的所有交点
边界上至多两个交点
内部的交点，至多 2N-2 个。因为除掉网格边界之外，内部的网格线，分别为N-1条横线和N-1条纵线,一条直线至多与它们总共有 N-1 + N-1 个交点
假设直线L穿过了m个方格
每穿过一个方格，就要有两个交点。所有交点数为2m。此2m中，边界的交点被计算了一次，非边界的交点都被计算了两次，所以有：
2m <= 2 + 2(2N-2)
从而 m<=2N-1 有一个和这个方格类似的问题：
如果a乘b的长方形方格的一条对角线恰好穿过c个单位小方格，求a+b的最大值。（a不等于b）
页:
[1]