差三角

KeyTo9_Fans · 发表于 2013-5-20 12:33:38

机器还可以，算法也不错。

$n=9$和$n=10$的结果如下：

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

复制代码

zgg___ · 发表于 2013-5-22 15:21:55

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

KeyTo9_Fans · 发表于 2013-5-22 15:36:41

之前提到，我把三角形横着摆是为了图方便，其实是与算法的设计有关。

我的算法很简单，就是一行一行地填数。

对于每一行，只要确定了第$1$个数，那么后面的数都确定了。

所以该算法需要枚举每行的第$1$个数，枚举量是$m^n$。

唯一的优化是：

如果前面确定下来的数已经有重复了，那么就没必要枚举下去了，直接回退即可。

#####

当$n=11$时，找到了$m=103$的解：

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

复制代码

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

#####

躺等$3$日，又得到了一个$m=102$的解：

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

复制代码

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

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

复制代码

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

KeyTo9_Fans · 发表于 2013-6-5 13:29:22

躺了$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 · 发表于 2013-6-7 12:02:07

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

hujunhua · 发表于 2013-6-10 11:48:31

由于我们坛子里的各路精英们经常会提出高质量的原创问题，我们坛子已经向《整数数列百科大全》网站贡献了很多个原创数列。 ...
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 · 发表于 2014-12-8 19:52:35

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

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

复制代码

#####

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

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

复制代码

#####

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

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

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

https://oeis.org/A226239

mathe · 发表于 2014-12-13 08:01:29

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

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 差三角

评分

评分