数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 408|回复: 8

[讨论] 穿越格子最多的直线

[复制链接]
发表于 2017-9-7 10:20:24 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
在 \(n\times n\) 的方格本内画一条直线,最多能穿越几个格子?
注:所谓穿过格子,指经过格子的内点。仅经过格子角上或者边界上的点不算数。

以前有讨论过这个问题吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-9-7 11:04:50 | 显示全部楼层
取一条对角线(穿越 \(n\) 个方格),
再将之略微平移很小的距离(新增 \((n-1)\) 个方格),
则可穿越 \((2n-1)\) 个方格,不知是否达到了最多?

点评

谢谢确实这样想就简单了  发表于 2017-9-7 17:36
这个“穿越边界”的证明,非常巧妙!  发表于 2017-9-7 13:20
每次横坐标或者纵坐标加1,最小值(1,1),最大(n,n),所以最多穿越边界2(n-1)次,所以最多2n-1个方格  发表于 2017-9-7 11:35
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-9-7 17:37:28 | 显示全部楼层
本帖最后由 hejoseph 于 2017-9-7 19:53 编辑

如果是 $m\times n$ 的方格结果又如何?$m+n-1$
如果是 $l\times m\times n$ 的长方体呢?$l+m+n-2$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-9-7 19:21:51 来自手机 | 显示全部楼层
假设直线是向右上方延伸,那么触碰到的格子只能向右或者向上增加。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 7 天前 | 显示全部楼层
本帖最后由 咻咻 于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 7 天前 | 显示全部楼层
有一个和这个方格类似的问题:
如果a乘b的长方形方格的一条对角线恰好穿过c个单位小方格,求a+b的最大值。(a不等于b)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-9-20 08:27 , Processed in 0.261715 second(s), 20 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表