| 网站首页 | 数学 | 名师 | 奥数 | 下载 | 素材 | 交流 | 智力 | 专业 | 设计 | 中学 | 数学博览 | 
您现在的位置: 小学数学专业网 >> 数学博览 >> 智力趣题 >> 正文 用户登录 新用户注册
王国之路
作者:佚名    数学博览来源:shuxueweb    点击数:    更新时间:2007-10-22

  某王国有16个城市。国王希望规划一个道路系统,使得任两城市间的道路互通所经过的中间城市不超过一个。还规定以每个城市为端点的路不超过5条。

  (1)试证l所述要求可实现;

  (2)试证:如果将数5换成4,那么所述要求不能实现。


  解  (1)图1是实现所述要求的设计方案示意图。

  为了不让太多的线路搅乱视线,在图中未画出以下10条道路

  鉴于对称性,只需按以下三种情形分别验证即可。

  (2)假设每个城市最多引出4条道路,并且任两城市可经过不多于一个中间城市的道路互通。首先观察图2,如果某个城市引出的道路不多于3条,那么从该城市出发,能按规定道路到达的城市,至多有12个。因此,从每一个城市引出的道路都有4条。

  然后观察图3。如果某城市引出的道路有4条,并且该城市是某个道路三角形的顶点,那么从该城市出发能按规定到达的城市最多有14个。接着观察图4.我们看到,如果不存在三角形道路或四边形道路,那么至少有17个城市。图5告诉我们,如果某城市是两个道路四边形的顶点,那么总共至多有15个城市。因此,满足要求的道路网没有任何道路三角形,并且每个城市恰为一个道路四边形的顶点。

  设道路网中两两无公共点四边形为AjBjCjDj;1≤j≤4.城市A1除了所在道路四边形的两条道路以外,另外还有两条道路引出,其中无一条通往C1(否则将形成道路三角形)。这两条路也不能都通往第k个四边形(2≤k≤4),否则会出现道路三角形或者第5个道路四边形(使得某些点是两个道路四边形的顶点)。不妨设从A1引出的另两条路当中,第一条通往A2,第二条通往A3。我们用(2,3)给A1标号,表示有一条道路通向第2个道路四边形,另有一条道路通向第3个道路四边形。因为A1必须能经过至多一个中间城市到第4个道路四边形中的城市,所以A2和A3各有一条道路通往第4个道路四边形的两个城市。从B1和D1也各有一条道路通向第4个道路四边形的另外两个城市。不妨设B1的标号为(2,4),D1的标号为(3,4)。

 

  请注意,B2与D1的标号不同,并且都与A1的标号不同。由于对称性,三城市A1,B1,C1的标号也各不相同。于是,C1的标号只能是(3,4)。但这样C1和D1就会有同样的标号。矛盾!

数学博览录入:管理员    责任编辑:管理员 
  • 上一篇数学博览:

  • 下一篇数学博览:
  • 发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口
    没有相关数学博览
    (只显示最新10条。评论内容只代表网友观点,与本站立场无关!)