手串上穿有六颗珠子，求各珠子上的数字。

白新岭

如果把43改到38以内或许有解，这时会有重复数字。

wayne

代码改进了下，加入了多核计算，运用了整数的拆分，运行$n=8$,在我的机器八核全开，只需要$6$秒钟。
$n=7$无解。
$n=8$有六组解

1. {{3,4,6,7,12,22},{{4,22,7,3,6,2,12},{12,2,6,3,7,22,4}}},
   
2. {{3,4,6,8,12,21},{{6,12,4,21,3,2,8},{8,2,3,21,4,12,6}}},
   
3. {{3,4,8,10,11,18},{{4,2,10,18,3,11,8},{8,11,3,18,10,2,4}}},
   
4. {{3,5,6,11,12,17},{{3,5,11,2,12,17,6},{6,17,12,2,11,5,3}}},
   
5. {{3,5,7,8,15,16},{{3,8,2,16,7,15,5},{5,15,7,16,2,8,3}}},
   
6. {{4,5,7,9,10,19},{{2,10,19,4,7,9,5},{5,9,7,4,19,10,2}}}

复制代码

1. n=8;
   
2. arr=a/@Range[n];
   
3. target=Flatten[{Total[arr],Table[Total[RotateLeft[arr,i][[1;;k]]],{i,0,n-1},{k,1,n-1}]}];
   
4. data=Select[IntegerPartitions[(-1+n) n-2,{n-2}],Length[Union[#]]==n-2&&Min[#]>2&];
   
5. Timing[ParallelTable[{d,Select[Permutations[Join[{2},d]],Length[Tally[Differences[Sort[target/.Thread[arr->Join[{1},#]]]]]]==1&]},{d,data}]]

复制代码

wayne

$n=9$只有四组解：

1. {{1, 14, 8, 2, 28, 3, 6, 7, 4}, {1, 4, 7, 6, 3, 28, 2, 8, 14}},
   
2. {{1, 8, 12, 2, 3, 13, 24, 4, 6}, {1, 6, 4, 24, 13, 3, 2, 12, 8}},
   
3. {{1, 16, 22, 2, 3, 4, 6, 8, 11}, {1, 11, 8, 6, 4, 3, 2, 22, 16}},
   
4. {{1, 2, 4, 8, 16, 5, 18, 9, 10}, {1, 10, 9, 18, 5, 16, 8, 4, 2}}

复制代码

王守恩

wayne 发表于 2019-2-9 20:05
$n=9$只有四组解：

尊敬的wayne！
可以再来几串吗？
我不会电脑，下面的话，不知对编程是否有用。

n=10，10个数的和是9×10+1=91，电脑只要能算出1——45就可以，
    或者10个数只要算 1, 2, 3, 4, 5 个数相加的和都不相同就可以。

n=11，11个数的和是10×11+1=111，电脑只要能算出1——55就可以，
    或者11个数只要算 1, 2, 3, 4, 5 个数相加的和都不相同就可以。

n=12，12个数的和是11×12+1=133，电脑只要能算出1——66就可以，
    或者12个数只要算 1, 2, 3, 4, 5, 6 个数相加的和都不相同就可以。

风云剑

或者10个数只要算 1, 2, 3, 4, 5 个数相加的和都不相同就可以。
不太明白你的意思，是不是说统计到5相邻就可以了？
我写了个程序试了试，这样不行啊。

风云剑

1. import numpy as np;
   
2. print("input n:");
   
3. num = int(input());
   
4. 
   
5. arr = np.zeros(num, dtype = int);
   
6. sa = 0;
   
7. 
   
8. def fit(idx, n):
   
9.     global sa;
   
10.     arr[idx] = n;
    
11.     sa += n;#求已经填的所有数字之和
    
12.     if(sa <= num * (num - 1) + 1):#所有数字和小于最大值才有意义
    
13.         if(idx == num - 1):#已经填满
    
14.             #print(arr);
    
15.             arr_sum = np.zeros((num * (num - 1) + 2), dtype = int);
    
16.             #以下几个循环用于求出相邻数字之和
    
17.             for x in range(1, num - 1):#统计相邻几个的和，n相邻就是所有数字之和sa，n-1相邻是否必须统计还不清楚，目前看貌似不需要？
    
18.                 for i in range(0, num):#从第几个数开始统计
    
19.                     ss = 0;
    
20.                     for j in range(i, i + x):
    
21.                         ss += arr[j % num];
    
22.                     arr_sum[ss] += 1;#统计结果保存
    
23.             arr_sum[sa] = 1;
    
24.             arr_sum[0] = 1;
    
25.             ok = True;
    
26.             for i in arr_sum:#判断是否不重复不遗漏
    
27.                 if(i > 1):
    
28.                     ok = False;
    
29.                     break;
    
30.             if(ok):
    
31.                 print(arr);
    
32.         else:#没填满，填下一个候选数，候选数不小于2，不大于n * (n - 1) / 2
    
33.             for x in range(2, 1 + num * (num - 1) // 2):
    
34.                 dup = False;
    
35.                 for i in range(1, idx + 1):#跳过重复
    
36.                     if(arr[i] == x):
    
37.                         dup = True;
    
38.                         break;
    
39.                 if(dup == False):
    
40.                     fit(idx + 1, x);
    
41.     sa -= n;#退回一步
    
42.    
    
43. fit(0, 1);

复制代码

以上是程序，按我的理解，只要把17行的条件改成num / 2就是你说的那样了，但是结果不能覆盖1~n*(n-1)+1

王守恩

风云剑 发表于 2019-2-12 16:02
或者10个数只要算 1, 2, 3, 4, 5 个数相加的和都不相同就可以。
不太明白你的意思，是不是说统计到5相邻就 ...

谢谢风云剑！对不起！是我的说法有问题。
n=10，10个数的和是9×10+1=91，电脑只要能算出1——45就可以，
   或者10个数只要算 1, 2, 3, 4, 5 个数相加的和都不相同就可以。
"或者10个数只要算 1, 2, 3, 4, 5 个数相加的和都不相同就可以"。
这句话有问题：1, 2, 3, 4, 5 个相邻数相加的和，会出现某1对数的和是91的。
谢谢风云剑！这道题还真是有点难度！
最后把 3 楼 mathe 的想法诠释一下。
对每个 n 来说。
1：1种可能，必须有。
2：1种可能，必须有。
3：2种可能。有——1,2不能连在一起；没有——1,2必须连在一起
4：2种可能。有——1,3不能连在一起；没有——1,3必须连在一起
5：2种可能。有——1,4，2,3都不能连在一起；没有——1,4，2,3其中必有1对连在一起
6：2种可能。有——1,5，2,4，1,2,3都不能连在一起；没有——1,5，2,4，1,2,3其中必有1对连在一起
7：2种可能。有——1,6，2,5，3,4，1,2,4都不能连在一起；没有——1,6，2,5，3,4，1,2,4其中必有1对连在一起

mathe

如图算法，可以手工穷举五颗珠子的情况从小到大穷举各种数值珠子的分布。用,分隔的表示相邻的珠子，用;相隔的代表不相邻的珠子。
每次添加的数字总是当前状态还没有覆盖到而且它的补数也没有被覆盖的最小数（补数是指总和减去这个结果得到的数）。而裁剪有两种规则:如果;隔开的段数和已用珠子总数大于N,淘汰。如果出现某个数字被两个不同模式覆盖，或两个不同模式覆盖的和等于期望的珠子数值和S，淘汰。
每次添加的数可以单独分离，也可以添加在某个连续段珠子的一侧，也可以连接两段珠子合成一段
最后得出一个N-1个数的模式就已经找到一个解，再添加S和它们和的差即可构成一个合法的环.
如图中N=5,S=(5-1)*5+1=21
我们从模式1出发，覆盖集合{1}。
所以下一个需要添加数字2 （因为2和21-2=19都没有被覆盖），分别得出模式
1,2 (覆盖{1,2,3},此后需要添加数字4)
1;2 (覆盖{1,2}，此后需要添加数字3)

下一步模式1,2可以添加4变为
4,1,2
1,2,4
1,2;4
三种之一
而模式
1;2可以添加3,变为
1;2;3
1,3;2
1;2,3
三者之一，其中模式1;2;3分成3段3个数，3+3=6>5不符合条件，需要被裁剪。

而对于模式4,1,2,它覆盖了集合{1,2,3,4,5,7},所以下一步应该添加数字6，可以得出
6,4,1,2
4,1,2,6
4,1,2;6
三种，其中最后一种4,1,2;6分两段四个数2+4=6>5又不符合条件，裁剪
而模式6,4,1,2覆盖了数10=6+4和11=6+4+1,而10+11=S,所以被裁剪
同样模式4,1,2,6覆盖了数13=4+1+2+6和8=2+6,13+8=S，也被裁剪

另外一种裁剪模式可以查看1,2,4，它覆盖了集合{1,2,3,4,6,7},所以下一步需要添加5，可以得出
1,2,4,5
5,1,2,4
1,2,4;5 (数目太多淘汰）
模式5,1,2,4中两次覆盖数6=5+1=2+4,所以被裁剪

一直这样淘汰下去会发现对于N=5我们会只有余下3,1,5,2这个包含5-1=4个数的模式。
这种情况它覆盖集合{1,2,3,4,5,6,7,8,9,11},它们的补数构成{10,12,13,14,15,16,17,18,19,20},两个集合之并正好构成1~S-1的所有数(总会如此）
最后我们只要在3,1,5,2后面添加S-(3+1+5+2)=10即可构成满足条件的答案3,1,5,2,10

mathe

N=1
1
N=2
1 2
N=3
1 2 4
N=4
1 3 2 7
4 1 2 6
N=5
3 1 5 2 10
N=6
1 3 6 2 5 14
1 7 3 2 4 14
1 3 2 7 8 10
5 1 2 7 4 12
1 2 5 4 6 13
N=7

N=8
4 1 12 2 6 3 7 22
10 2 4 1 8 11 3 18
6 1 3 5 11 2 12 17
2 8 3 1 5 15 7 16
3 2 8 1 6 12 4 21
10 2 1 5 9 7 4 19
N=9
3 6 7 4 1 14 8 2 28
4 6 1 8 12 2 3 13 24
16 1 11 8 6 4 3 2 22
9 10 1 2 4 8 16 5 18
N=10
1 5 4 13 3 8 7 12 2 36
10 3 11 1 4 2 20 8 9 23
1 4 3 10 2 9 14 16 6 26
18 1 3 9 11 6 8 2 5 28
11 9 6 1 18 3 2 8 4 29
18 6 2 1 10 4 16 5 7 22
N=11

N=12
21 12 5 1 7 2 22 4 16 3 11 29
1 15 5 3 25 2 7 4 6 12 14 39
10 9 2 15 16 6 7 1 4 20 3 40
1 4 7 3 16 2 6 17 20 9 13 35
20 19 4 1 11 2 8 7 25 6 3 27
2 6 1 4 16 3 15 10 12 14 17 33
9 1 7 13 12 3 11 5 18 4 2 48
1 8 10 5 7 21 4 2 11 3 26 35
1 22 14 20 5 13 8 3 4 2 10 31
12 3 1 25 7 6 5 9 8 2 21 34
6 1 3 8 9 5 19 23 16 13 2 28
23 3 1 8 5 2 18 11 10 22 6 24
1 14 10 20 7 6 3 2 17 4 8 41
1 14 3 2 4 7 21 8 25 10 12 26
4 14 8 9 2 1 24 5 10 6 7 43
4 14 2 1 9 13 6 5 27 8 7 37
12 14 2 1 7 13 18 4 5 6 19 32
12 2 1 5 16 11 7 10 9 4 25 31
N=13

N=14
5 4 22 8 6 1 10 2 16 32 20 3 21 33
12 1 14 4 5 11 10 7 22 3 38 2 6 48
3 9 10 1 5 2 24 15 29 14 21 13 4 33
8 4 1 14 7 10 6 24 9 2 18 25 3 52
8 19 1 4 6 31 3 13 2 7 14 12 17 46
31 1 4 20 2 12 3 6 7 33 11 8 10 35
4 2 14 15 17 7 18 1 8 3 10 23 5 56
27 12 3 5 11 2 4 26 14 9 1 28 7 34
5 9 1 12 11 6 2 18 16 35 21 4 3 40
2 16 6 5 8 4 3 25 21 9 1 33 14 36
27 23 5 1 8 16 10 12 19 2 11 4 3 42
22 10 1 17 8 5 24 14 2 4 3 12 27 34
7 2 8 5 16 19 1 3 24 6 12 14 11 55
14 20 7 12 3 1 9 8 28 2 24 5 6 44
25 6 5 3 1 12 22 7 17 2 18 10 23 32
21 8 1 25 23 4 10 2 3 17 11 7 6 45
10 1 15 34 2 3 17 7 6 8 4 19 9 48
15 12 7 1 2 21 17 11 5 9 4 26 6 47
14 5 7 13 2 1 8 21 17 18 33 4 6 34
18 4 13 16 7 1 2 28 14 5 6 9 12 48
N=15

N=16

N=17
5 10 19 1 7 31 2 11 3 9 36 17 4 22 6 18 72
24 5 33 15 3 7 1 34 12 19 9 4 17 6 14 2 68
14 9 28 17 1 3 12 10 31 7 27 2 6 5 19 20 62
12 7 1 23 11 3 2 13 33 22 6 4 17 9 41 25 44
11 21 1 27 8 7 2 3 26 25 16 14 4 6 13 39 50
13 10 29 5 17 18 1 2 4 8 16 32 27 26 11 9 45

wayne

mathe好猛，我来摘桃子了，

n                a(n)
1                1
2                1
3                1
4                2
5                1
6                5
7                0
8                6
9                4
10                6
11                0
12                18
13                0
14                20
15                0
16                0
17                6
18                51
19                0
20                42

http://oeis.org/A058241