网格中穿越最大格子的直线

hejoseph

在 $n\times n$ 的方格本内画一条直线，最多能穿越几个格子？

hejoseph

如果仅过格子的顶点或与边重合，则不算穿越格子

isee

回复 1# hejoseph


    我凭直觉，像是把对角线向上拉一点点。。。这个直学似乎是对的。
    $n\times n$的网络，画出对角线（所在的直）线，经过了$n$个格，此对角线（段）除了首尾两个点，中间还经过了$n+1-2=n-1$个顶点，沿对角线垂直方向稍平移一个很小的距离，原$n-1$点会得到$n-1$个等腰直角三角形，即又多经过了$n-1$个网格，此时共经过了$n+n-1=2n-1$个网格。

hejoseph

这里有解答
bbs.emath.ac.cn/thread-9636-1-1.html