n阶方点阵的一笔画问题

s4219

　　一.  问题的由来
　　有一道古老的益智题，相信诸位在学生时代都曾接触过。
　　以一笔画的方式用四条直线连接九点，各点只许通过一次。题目与答案如下：


　　此题看似简单，但多数人并不能很快完成，失败的症结是思维不能跳出方框。一旦跳出方框，答案便跃然纸上了。趣味盎然。

　　以上是3阶点阵(3*3=9点) 4划，仅有一个答案。

    对于：
          4阶点阵   6划
          5阶点阵   8划
          6阶点阵  10划
            ......
                  n阶点阵 (n-1)*2划  
    是否也都能这样以一笔画的方式用 (n-1)*2 划直线连接 n*n点呢？
    至今好象很少有人认真思考过。

     对于该题，本人空闲时曾作过一些研究，并对4阶5阶6阶及更高阶的都试着画过，都找到了多种画法。
    在此我们约定：凡经旋转或翻转后能重叠的画法都只算作一种。各点只许经过一次。

    以下是4阶点阵的14种画法。

这是2008年9月前的答案，目前已找到15种画法。

　　5阶点阵的画法有一百多种。6阶点阵的画法更是多达三百种以上。


一.  问题的由来
二.  图形的变异与遗传
三.  证明的关键是寻找合适的模型
四.  可能的应用

数学星空

5阶点阵的画法有一百多种。6阶点阵的画法更是多达三百种以上。
这说明我们只能期望估计出"N阶点阵一笔画"数目的近似表达式?
若记点阵的相邻格点距离为1,试给出"N阶点阵一笔画"的最小长度和最大长度(当然只能期望是估计式)?

为了便于我们讨论问题,可以记N阶点阵的坐标为A(i,j),例如对于N=3,我们有一种方案:
A(2,1)-A(3,1)-A(3,2)-A(2,3)-A(1,3)-A(1,2)-A(1,1)-A(2,2)-A(3,3)

s4219

若记点阵的相邻格点距离为1,试给出"N阶点阵一笔画"的最小长度和最大长度
N阶点阵一笔画长度是相同的，为N平方减1。（N-1）*2段折线串连起所有节点，形成一条链，不同的画法在链上的表现仅仅是节点排列（次序）上发生了变化。只要在排列上相邻就是相邻点了。与节点的几何距离无关，因为在此并不考虑几何尺度。

    该题属于图论方面的研究题，比普通概念的一笔画稍有区别，要求更高一些（因为各点只许通过一次）。该题是寻找符合题意要求的可能路径。当节点增加时，寻路的计算量便迅速窜升至天文数，电脑也无能为力了。高阶点阵的节点显然对直线的穿越会造成无数的障碍（屏蔽），因此当N趋无穷大时还能画出来吗？
    答案出乎意料，当N增大时画法数S也会增加而且S>N，当N趋∞时，S也∞

    3阶的画法在五、六十年前就很流行了，最早什么时间出现的已很难考证了，估计至少存在近百年了。因此非常可能在那时代已有数学爱好者进行过研究，甚至可能早已有过明确的结论。世界如此之大，很难相信该题会被数学爱好者所忽略的，尽管至今我尚未见有文献提及该题。不过我还是很想知道目前该题是否已有答案和结论？

    从该题的画法演化来看，当N变大时图形具有很强的趋同性，这与遗传特性似乎很相象。

数学星空

N阶点阵一笔画长度是相同的，为N平方减1
显然你的说法有误:
例如:由楼主提供的"四阶点阵的一笔画方法"图形,我们可以计算出其连线长度(从左自右,从上自下),
          设相邻格点距离为1
         (1)  $ 19/2+5/2*sqrt(5)+5*sqrt(2)$
         (2)   $21/2+5/2*sqrt(5)+5*sqrt(2)$      
         (3)   $10+5*sqrt(2)+3*sqrt(5)$         
         (4)   $ 11+5*sqrt(2)+2*sqrt(5)$
         (5)    $15+4*sqrt(5)+7*sqrt(2)$         
         (6)   $11+5*sqrt(2)+5*sqrt(5)$
         (7)   $11+6*sqrt(5)+4*sqrt(2)$
         (8)   $12+5*sqrt(5)+4*sqrt(2)$
         (9)   $13+5*sqrt(5)+6*sqrt(2)$
           ..........................

当N增大时画法数S也会增加而且S>N，当N趋∞时，S也∞
这个结论是显然的,我们只能关注画法数估计式$F(N)$

s4219

能与数学星空讨论该题很高兴。
1。你所提的长度和我所指的“长度”非同一意义，我没去考虑它的作用。因为本题所表现的规律性问题不在此。而且你以后你可以看到，实际上关键部分仅在点阵区域范围内，只要在该区域范围内是直线就足以说明问题了，外部的联接线即使是曲线也不会影响所获得的画法（即答案）的正确性。因此可认为长度的意义并不重要。关键还是在点阵区域范围内节点连接的变化。
2。结论并非显然，是需要证明的。从F（2）=0，即已表示本题存在无解的可能，F（3）=1，。。。为什么F（N）一定就是越来越大，而不会是呈现正态分布呢？从想象来看，N变大时，图形越来越难画，因为每一线段的平均连接的节点数是在不断增加的。因此不仅要证明有解，而且还要证明解的组数是远大于N。F（N）应该一系列的固定值数，甚至可能用通式来表示，但由于目前很难获得此数，对于高阶点阵即使用计算机也无能为力，这与许多图论题相似，本题的F（N）只能暂定为“不可测”。我肯定没能力完成F（N）的求解。


    二.  图形的变异与遗传
   
    下图所示为如何从3阶演变为4阶的过程：

    A. 3阶图形的左下三点带线平移一格
    B. C. 折线通过端点的延伸即可获得相应的4阶图形
    D. E. 先将A图的平移段割断，然后转向连接即可获得新的一组4阶图形
    F. 请注意这是B.C.D.E.图中共同的“基因”，它是从3阶图形变异后遗传过来的。它们是同族的图形。（通过基因识别，很容易将图形进行归类和统计，或者再找出新的画法）
    凡是基因相同的，都是同族的，在前一节的附图中，不难找到第5图也是具有相同基因的，它也是一个祖宗生的。

    不难发现B.C.E. 这三个图形通过端点延伸，又能很容易地直接获得四个5阶的图形。如果作些变移，就能有更多的画法了。但通常这样的衍生并不能都顺利地进行，大都走不远，很快就会终止。

s4219

Tips:

    1。要找寻n阶点阵的一笔画方法，势必要动手试着画，然而失败的比例极高，徒手画点阵，画连接线，对不熟悉的人来讲，万分辛苦，没画几个就没耐心了，纸也很浪费。
    较好的办法是：在白纸上先多打上些细线方格，再用深色的笔画上所需要的N阶点阵的节点，把这张纸贴在透明塑料片的背面。需要时用彩色水笔在塑料片直接上画即可，如果不需要时只要用湿布一擦就又可重新开始画了。找到新的画法时才记录到本子，既方便又节约纸，省得不断的画点阵和方格。
   
    2。在高阶点阵绘画时，在方点阵范围内的线段应该用直线画出，并且尽量使之能分清所连节点和走向，对于点方阵外的连线有时则可以使用弧线替代连接，只要被连接的节点不要搞错即可，这样就能大大压缩图形的尺寸，并使图形更清晰。否则实际图形有可能超出去很多，反而看不清楚了。

    3。把同族的图形同向(按同基因方向)排列，这样将有利于迅速剔除重复的图形。

数学星空

为方便研究:
      依次将一笔画折线上每条线段的点数记录下来,若格点被两条线段连接则-1,对于楼主提供的"四阶点阵的一笔画"图形,我们可以依次得到从左自右,从上自下)
     (1)$3+(3-1)+2+3+(4-1)+(4-1)$
     (2)$3+(3-1)+2+3+(3-1)+4$
     (3)$ 3+(4-1)+(4-1)+2+3+(3-1)$   
     (4)$3+(4-1)+(4-1)+3+(3-1)+2$     
     (5)$3+(4-1)+(3-1)+2+4+2$
     (6)$2+4+2+2+2+4$
      (7)$2+2+2+4+2+4$
      (8)$2+2+4+2+4+2$   
      (9)$2+4+2+2+4+2$
      (10)$2+2+2+3+4+3$
      (11)$2+3+(3-1)+3+4+2$
      (12)$4+2+2+2+2+4$      
      (13)$2+4+2+2+4+2$
       (14)$2+2+4+2+2+4$


这提示我们能够一笔画连线的条件就是:     (对于N阶点阵)
    $-k+2*x_2+3*x_3+4*x_4+......+N*x_n=N^2$
    $x_2+x_3+x_4+........+x_n=2*(N-1)$
     $0<=k<=N/2$  
的正整数解${k,x_2,x_3,......,x_n}$

s4219

1。链上各段折线所连接的节点数的累加和等于n^2，这是题意本来就所要求的。

    题目本来就是要求用2(n-1)段折线连接n阶点阵的全部节点，而且只许通过一次。所以各段加起来必须是n平方。这应该是属于本题的限制性的规则。

(注：通常的一笔画的节点是允许多次通过的，结果累计通过的节点数有可能会超过总点数。)

2。对所提及的正整数解不能理解，4阶的解该为几何？

数学星空

对于4阶点阵,(1)~(14)的解(1#楼主提供的"四阶点阵的一笔画"图形)
例 (1)$k=3,x_2=1,x_3=3,x_4=2$
      (2)$k=2,x_2=1,x_3=3,x_4=1$
      (3)$k=3,x_2=1,x_3=3,x_4=2$   
        ......................

s4219

看明白你的意思了。
通过这能找到各种画法吗？肯定是不行的。
1。这些对寻找正确答案没有意义。它没能体现节点的序列。
2。缺乏唯一性。不同的画法可能有相同的分段结果，例如4阶中的：（9）与（13），（12）与（15）等

注：4阶的画法目前实际已有15种，第15种是09年找到的，因此在08年的图中未画进去。
（15）的序列：11，21，31，41，43，24，14，23，33，44，34，13，12，22，32，42
分段也是422224。与（12）相同。

实际上在高阶点阵的一笔画中存在大量的相同的分段结果，而且N越大，相同的会越多。然而它们的实际走向却都是完全不同的。所以仅凭分段来指导寻求画法是远远不够的。再说在图中起点和终点实际是相同的概念，因此还需要和倒过来的排列作比较，那时相同的将可能会更多。