差三角

KeyTo9_Fans

机器还可以，算法也不错。 $n=9$和$n=10$的结果如下：

1. 9: 59
2. 43
3. 53 10
4. 13 40 30
5. 59 46 6 24
6. 55 4 42 36 12
7. 1 54 50 8 28 16
8. 58 57 3 47 39 11 5
9. 49 9 48 45 2 37 26 21
10. 17 32 23 25 20 18 19 7 14
11. 10: 76
12. 52
13. 16 36
14. 66 50 14
15. 75 9 41 27
16. 15 60 51 10 17
17. 73 58 2 49 39 22
18. 76 3 55 53 4 35 13
19. 12 64 61 6 47 43 8 5
20. 69 57 7 54 48 1 42 34 29
21. 45 24 33 26 28 20 19 23 11 18

复制代码

zgg___

“机器还可以，算法也不错”，呵呵。一般来说，算法的威力要比机器的威力要大得多，想来Fans能算的原因不是有钱而是聪明的呢。呵呵。 我的算法是这个样子的：例如n=10，先试着在三角形里放入55，有10种方法，就是放在底座上了，然后试着放入44，要么放在底座上，要么和45连着，再下来放43，还是只能放在底座上或是和已有大数相连……如此构成的树的分支较少，深度也较小（我原想要证明当n大时，深度是有限的，也就证明了差三角的不存在性，不过还没有证明），看来复杂度是n^n量级的。而算法的副产品是将从m（55）开始的数，依次递减的填入边长为n（10）的差三角，看能递减到哪里？而从Fans的算法的输出来看，貌似不是这个思路，所以我挺好奇的，Fans讲讲你的方法吧。呵呵。

KeyTo9_Fans

之前提到，我把三角形横着摆是为了图方便，其实是与算法的设计有关。 我的算法很简单，就是一行一行地填数。 对于每一行，只要确定了第$1$个数，那么后面的数都确定了。 所以该算法需要枚举每行的第$1$个数，枚举量是$m^n$。 唯一的优化是： 如果前面确定下来的数已经有重复了，那么就没必要枚举下去了，直接回退即可。 ##### 当$n=11$时，找到了$m=103$的解：

2. 11: 103
3. 102
4. 34 68
5. 12 22 46
6. 103 91 69 23
7. 15 88 3 66 43
8. 16 1 87 84 18 25
9. 95 79 78 9 75 57 32
10. 14 81 2 76 67 8 49 17
11. 21 7 74 72 4 63 55 6 11
12. 92 71 64 10 62 58 5 50 44 33
13. 40 52 19 45 35 27 31 26 24 20 13

复制代码

但现在还不知道这个解是不是最优的。 ##### 躺等$3$日，又得到了一个$m=102$的解：

1. 11: 102
2. 12
3. 77 65
4. 98 21 44
5. 19 79 58 14
6. 100 81 2 56 42
7. 95 5 76 74 18 24
8. 8 87 82 6 68 50 26
9. 102 94 7 75 69 1 49 23
10. 99 3 91 84 9 60 59 10 13
11. 16 83 80 11 73 64 4 55 45 32
12. 70 54 29 51 40 33 31 27 28 17 15

复制代码

再躺$2$日，又拿到了一个$m=101$的解：

1. 11: 101
2. 21
3. 79 58
4. 92 13 45
5. 19 73 60 15
6. 99 80 7 53 38
7. 93 6 74 67 14 24
8. 11 82 76 2 65 51 27
9. 101 90 8 68 66 1 50 23
10. 97 4 86 78 10 56 55 5 18
11. 16 81 77 9 69 59 3 52 47 29
12. 64 48 33 44 35 34 25 22 30 17 12

复制代码

但还是不知道这个解是不是最优的。

KeyTo9_Fans

躺了$2$周，终于把$m=100$搜了个遍，结果无解。 于是当$n=11$时，$m=101$是最优解。 把$n=1$到$n=11$的$m$值列出来，结果如下： $1$，$3$，$6$，$10$，$15$，$22$，$33$，$44$，$59$，$76$，$101$。 该数列已经被《整数数列百科大全》网站收录，链接如下： https://oeis.org/A226239 恭喜楼主！ 由于我们坛子里的各路精英们经常会提出高质量的原创问题， 我们坛子已经向《整数数列百科大全》网站贡献了很多个原创数列。 如果这些数列被人关注，很可能会得到专业人士的扩展和相关的文献支持， 我们将会有机会从中学到更多的研究方法，了解到更多的相关研究结果。

hujunhua

Fans能否简单地说明一下，对于给定的n, m=m1无解，则m=m1-1也无解？ 比如上面，n=11时，搜遍m=100无解，就涵盖了m=99的情况吗？

hujunhua

由于我们坛子里的各路精英们经常会提出高质量的原创问题，我们坛子已经向《整数数列百科大全》网站贡献了很多个原创数列。 ... KeyTo9_Fans 发表于 2013-6-5 13:29

要说新数列，本坛的曾经热烈讨论过的自然数前段的均衡样本可以贡献几个很好 的新数列： 1）前段{1, 2, 3, ..., n}的所有均衡样本总数，前几项为{0, 0, 2, 2, 6, 6, 18, 16, 50, 46, 150, 136, 470, 426, 1518, 1390,5042, 4650, 17110, 15882, 59006}。由于奇偶有起伏，可以分离为2个单增数列。 2）前段{1, 2, 3, ..., n}的所有不可约均衡样本总数。 3）前段{1, 2, 3, ..., n}的所有极大划分总数。 这几个数列我计算过前20项，在http://oeis.org上都没有搜到，应该是没有收录。 KeyTo9_Fans何不把它们提交到该网站去？

KeyTo9_Fans

经过了长达$3$个月的搜索，找到了$n=12$、$m=127$的解：

1. 12: 127
   
2.    91
   
3.   106  15
   
4.    19  87  72
   
5.   127 108  21  51
   
6.   116  11  97  76  25
   
7.    16 100  89   8  68  43
   
8.   117 101   1  88  80  12  31
   
9.   124   7  94  93   5  75  63  32
   
10.    13 111 104  10  83  78   3  60  28
    
11.   122 109   2 102  92   9  69  66   6  22
    
12.    99  23  86  84  18  74  65   4  62  56  34
    
13.    17  82  59  27  57  39  35  30  26  36  20  14

复制代码

#####

又经过了长达$2$个月的搜索，找到了$n=12$、$m=125$的解：

1.    20
   
2.   101  81
   
3.   118  17  64
   
4.     5 113  96  32
   
5.   125 120   7  89  57
   
6.   122   3 117 110  21  36
   
7.     8 114 111   6 104  83  47
   
8.   124 116   2 109 103   1  82  35
   
9.   115   9 107 105   4  99  98  16  19
   
10.    13 102  93  14  91  87  12  86  70  51
    
11.    90  77  25  68  54  37  50  38  48  22  29
    
12.    62  28  49  24  44  10  27  23  15  33  11  18

复制代码

#####

又经过了长达$6$个月的搜索，所有可能的情况已经找遍。

因此$m=125$是$n=12$的最优解。

该结果已经提交到OEIS上了，该数列已经更新：

https://oeis.org/A226239

mathe

fans还可以统计一下最优解的数目