一个未解的数学问题:9棵树,每3棵栽一行,怎样栽10行?
2019年2月8日星期五
一天,儿子神秘兮兮地对我说:“我有一道题,你肯定做不出来!”我既觉得好奇,又感到好笑,说:“什么题?”儿子看了我一眼,摆摆手:“等我看完这集动画片再给你说。”小鬼居然吊起了我的胃口。
看完后,儿子对我说:“有9棵树,每3棵栽一行,怎样栽10行?”
“你这是脑筋急转弯吧!我也给你出一道:树上骑(7)个猴,树下一个猴,一共几个猴?”
“什么意思?”
我又重复了一遍本山大叔的经典智力测试题。
“8个猴?”
“错!2个猴。”
“怎么可能?”
“树上骑着一个猴,骑马的骑。哈哈……”
“骗人!”
“这是脑筋急转弯,你出的题不也是吗?”
“我出的题是有答案的,你想不出来就算了,要不要我告诉你这个笨蛋爸爸?”
“等等……”
栽树
小品《卖车》
我开始在本子上画想到的一种方案。我认为这个题目中所谓的“每3棵栽一行”更应该理解为“3点共线”,行与行之间不是整齐划一的平行关系,是可以而且必须相交的。最容易想到的是“田字格”,但是只有8行,没有成功。
“人家的是这样的!”儿子有点着急,赶紧给我示范。
“你这不能画曲线啊!”我赶紧反驳。儿子也没有成功,但是他记住了点的大概位置。虽然他并不理解点位背后的关系,但的确给了我成功的提示。
这个正确的结果是在构成“田字格”的9个点的基础上变化而来的。为了进一步验证,我又用软件画了一遍。
矩形是ABCD,依次取各边中点为:G、H、I、J,加上中心点E,构成了最初的9个点。接下来将左右两边的中点:G、H,分别向中心点E方向平移到点L、K的位置,得到新的9个点:A、B、C、D、E、L、K、I、J,即为满足条件的“9棵树”。其中,点L、K分别是线段GE、HE的中点。
(重要程度★★★)
“你这是从哪看到的题?”
“一个动画片上。”
我本来想一探究竟,但估计不会有太多的发现。
我对上述答案及不靠谱的解答方法十分不满,因为由此产生的问题远远要比题目和答案更多!
1.为什么“田字格”不满足题意?只是因为有8条“三点共线”的直线吗?
田字格
2.为什么上面的答案是正确的?除了“10行”或10条“三点共线”的直线外,还有没有其他的原因?
正确答案
3.一个9个点的图,每3点共线,最多可以有多少条这样的直线?最少又是多少?
4.一个n个点的图,每k点共线,最多可以有多少条这样的直线?最少又是多少?
其中:n∈N,k∈N,2<k≤n。N表示自然数,为何没有k=2,因为这时就是“完全图”,下面介绍。
首先,为了表达的方便,我们引入一些概念。这些概念主要有:简单图(G)、阶(n)、规模(m)、度(deg(v))、完全图(Kn)。
下图是一个“图”:
简单图1
这是一个“简单图”,它由5个点、4条边组成。点的集合(简称“点集”)是:V={A、B、C、D、E},边的集合(简称“边集”)是:E={AB、BC、AC、CD}。为了不致混淆,《图论》中常用小写字母表示点的名称,于是记为:V={a、b、c、d、e},E={ab、bc、ac、cd}。所以说是“简单”,因为具备这样两个特点:
①无重边。重边指连接两点有两条及以上的边。
三重边
②无环。若一条边的两个端点是同一个点,则称此边为环。
环
著名的哥尼斯堡七桥问题中抽象出的几何图显然不是“简单图”,它是一个“多重图”,AB之间、AC之间,分别存在“二重边”。
人教六数下册104页
一般的图用符号:G=(V,E)表示,说明图G是由点集V和边集E组成的。
我们称呼图的点的数量为图的阶,也就是图G的点集V中的元素的个数,记为:n=|V(G)|。其中:V(G)表示图G的点的集合V,其元素为点;双竖线“||”表示集合中元素的个数或集合的基数。当一个集合是无限集合时,其元素的个数或基数是没有意义的,数学家又发明了“集合的势”的概念。对于有限集合,集合的势就是集合的基数,也就是集合中元素的个数。
我们称呼图的边的数量为图的规模,也就是图G的边集E中的元素的个数,记为:m=|E(G)|。E(G)表示图G的边的集合E,其元素为边。
对于多个图,不加区别时,也可以记为:阶n=|V|,规模m=|E|。用语言表述为:阶n等于点集V的基数,规模m等于边集E的基数。
若用G1表示上面的简单图1,则有:
n=|V(G1)|=|{A、B、C、D、E}|=5
m=|E(G1)|=|{AB、BC、AC、CD}|=4
即:G1是一个5阶简单图,规模为4。
若一个图的点集V中的两点vi、vj间存在边(至少一条),我们就称点vi与vj邻接,否则,就称点vi与vj非邻接。边vivj与点vi和vj相关联。简单图中,点v的度指与点v邻接的点的数量;多重图中,点v的度指与点v关联的边的数量。点v的度记作deg(v)。
以上简单图1(5阶规模4)中有:
deg(A)=2
deg(B)=2
deg(C)=3
deg(D)=1
deg(E)=0
度的总和:∑deg=2+2+3+1+0=8=4×2=m×2=|E|×2
E点的度为0,我们称为孤立点,因为它不与其他的点邻接。
以上哥尼斯堡七桥问题中的抽象几何图(4阶规模7)中有:
deg(A)=5
deg(B)=3
deg(C)=3
deg(D)=3
度的总和:∑deg=5+3+3+3=14=7×2=m×2=|E|×2
我们给出简单而重要的“欧拉定理”:
在任何图中,点的度的总和等于边数的两倍。
证明:因为图的每条边都关联于两个点,每增加一条边,都将使点的度的总和增加2。
在简单图中,有一类特殊而重要的图,叫做完全图,记为Kn。在该图中,共有n个点,每两个点之间都存在边。下图是1阶~5阶完全图,点数、边数相对较少。
1阶~5阶完全图
完全图Kn中:
m=n×(n-1)÷2
∑deg=n×(n-1)
以5阶完全图为例,一共有n×(n-1)÷2=5×(5-1)÷2=10条边,5个点的度的总和是n×(n-1)=5×(5-1)=20。
如果您对边数的计算有所迷惑,可参阅以下教材:
人教六数下册100页
完全图Kn有两个重要的特点:
①完全图Kn的边数、度数总和是一般的n阶简单图的上限。
②任取Kn中n1(1≤n1≤n)个点,连同只与这n1个点关联的所有边,一定是一个n1阶完全图。
通俗点讲,就是完全图的任一部分(子图)仍然是一个完全图。
3阶完全子图
4阶完全子图
5阶完全子图
可见,完全图恰好回答了问题4(一个n个点的图,每k点共线,最多可以有多少条这样的直线?最少又是多少?)中当k=2的情况。此时:最多=最少=n×(n-1)÷2,显然没有多大的意义。
(重要程度★★★★★)
也许您已经烦透了,别担心,我和您一样。如果我们要将“数学之路”走得稍微远一点,除了要具备一定的“抽象的、逻辑推理的”数学思维之外,还要熟悉必要的概念和数学符号语言。学习首先要从克服表达、交流、沟通的障碍开始。
接下来观察一下完全图K9:
完全图K9
稍带着欣赏一下:完全图K26
m=n×(n-1)÷2=9×(9-1)÷2=36
∑deg=n×(n-1)=9×(9-1)=72
对于任意9阶简单图有:
边数:0≤m≤36
度的总和:0≤∑deg≤72
对于三点共线,只有一种情况:
当产生第4点时,有两种选择:
①产生重合直线:
②寻找新的直线:
此时,我们似乎发现了题目隐藏的限定条件:所谓“每k点共线”产生的直线彼此不能重合。
以“五点共线”为例:
若三点相邻,则有:ABC共线、BCD共线、CDE共线,共3条直线重合。计算方法为:C(1,n-k+1)=C(1,5-3+1)=C(1,3)=3(条)。组合计算的道理是将“相邻三点”当作一个整体,计算3选1的组合。
若任取三点,则有:ABC共线、ABD共线、ABE共线、ACD共线、ACE共线、ADE共线、BCD共线、BCE共线、BDE共线、CDE共线,共10条直线重合。计算方法为:C(k,n)=C(3,5)=5×4×3÷(3×2×1)=10(条),即计算5选3的组合。
显然,如果不排除直线“重合”的可能,则有些“赖皮”。设若平面上只画了一条直线,我们也是可以大言不惭地说:看,这是十万条直线,只不过全都重合在了一起。
对于“九点共线”,其中包含的“赖皮”一样的“三点共线”,以相邻三点而论时有:
C(1,9-3+1)=C(1,7)=7(条)
以任意三点而论时有:
C(3,9)=9×8×7÷(3×2×1)=84(条)
险些夸张地完成题目!
为了使问题更有意义,而不是在“特例”上诡辩,下面我们严格遵循“每k点共线产生的直线彼此不重合”。
对比“三点共线图”和“完全图K3”:
有:
对于“栽10行”,也就是彼此不重合的10条“三点共线”的直线,此时要求符合题意的图:
m=2×10=20
∑deg=4×10=40
这里的乘以10并不是想当然的,所以这样做,是因为“每3点共线产生的直线彼此不重合”,这就保证了“点重而边不重”,对于结果的边数和度的总和的计算没有影响。
(重要程度★★★★)
事实上,“田字格”只有16边、32度,所以不符合题意。
田字格
正确答案满足20边、40度,您可以验证一番。
正确答案
一个9个点的图,每3点共线,最多可以有多少条这样的直线?最少又是多少?
答案的下限自然是0,比如按“正九边形”的点位栽植:
答案的上限是:
∑deg(V(Kn))÷∑deg(V(Kk))
=∑deg(V(K9))÷∑deg(V(K3))
=9×(9-1)÷[3×(3-1)]
=72÷6
=12
即用9阶完全图的度数和除以3阶完全图的度数和。
用边数计算得到的结果是一样的。
m(Kn)÷m(Kk)
=m(K9)÷m(K3)
=9×(9-1)÷2÷[3×(3-1)÷2]
=36÷3
=12
这样计算背后的道理是:当三点共线时,对比三阶完全子图(9阶完全图的任意3点及其只与该3点关联的边构成3阶完全图,如前所述,此处运用),损失了2度、1条边,“栽10行”的结果将消耗9阶完全图的度数:(4+2)×10=60,边数:(2+1)×10=30,而9阶完全图一共有72度、36边。
(重要程度★★★★★)
从计算来看,似乎存在“9棵树,每3棵栽一行,可以栽11行、12行”的可能,但我实在画不出来。上限并不见得就是可以实现的。
同理,“9棵树,每4棵栽一行,可以栽多少行”的上限是:9×(9-1)÷[4×(4-1)]=72÷12=6(行)。只是我能画出的却只有3行,呵呵,惭愧啊。
且不论问题4的一般情况的解决,就连问题3也只解决了一半。我只是用最简单的方法划定了一个范围。如何让上限更加逼近实际可以画出的“k点共线”的直线数,或许要用到更为深奥的数学知识。鄙人实在黔驴技穷、力有不逮。就把这个未解的问题留于真正的大神吧!诚如儿子给我说的:我终究没能做出来。
再会。
联系客服