← 我们打字和使用鼠标的方式，反映了自身的压力水平马斯克想把Twitter变成什么 →

29

脑力小体操：全贴吧无人能解的问题

下面的问题其实也有个噱头。10多年前贴吧还活着的时候，有人以“全贴吧无人能解的问题”为标题，四处发帖寻求解答过程。

后来我是没事当数独做，做着做着，确认了答案(因为可以猜出来，所以叫确认)。

让我们从0开始，选出10个非负整数。要求是 任意 两个数的差全不相同，问：10个数字从小到大排列，其中最大者(记为)A(10)的 最小值 是多少？

另外说一句，如果有人发现了比较好的算法，可以方便地算出A(n)(把10个换成n个数字时，满足条件的最大数的最小值)，可以去著名的自然数列网站oeis：https://oeis.org/，上搜索该数列，然后添加你的结果。看看是否业内领先。

+1

1. 5444346

   让GPT给写了个python程序实现：
   def find_minimal_max_number(count):
   numbers = [0]
   current_number = 0
   diffs = set()

   for _ in range(1, count):
   while True:
   current_number += 1
   is_valid = True

   for num in numbers:
   diff = abs(current_number – num)
   if diff in diffs:
   is_valid = False
   break

   if is_valid:
   numbers.append(current_number)
   for num in numbers[:-1]:
   diffs.add(abs(current_number – num))
   break

   return numbers[-1]

   count = 10
   minimal_max_number = find_minimal_max_number(count)
   print(f"The minimal value of the {count}th number is: {minimal_max_number}")

2. 5444387

   @短腿天才: 这个算法的想法很好，假如已经得到了前 n-1 个数，那么只需搜索第 n 个数，使得它与前面 n-1 个数的差都是崭新的。我第一反应也是这么搜索，唯一的问题是这样是错的，它默认了所求数列 n 里面的前 n-1 项刚好与所求数列 n-1 一模一样，没有去探索更完整的空间。
   如果我读代码没错的话，n=3 时它给出的数列应该是 {0, 1, 3}，进一步 n=4 时它就会给出 {0, 1, 3, 7}，但是其实 n=4 时显然可以优化成 {0, 1, 4, 6}，即从 7 压缩到 6 也符合要求。

   ps: 文章怎么没给 OEIS 编号啊，那让人怎么搜索，不会是要读者解出正确答案之后才能上 OEIS 匹配到吧？A004137 看定义的话涉及的概念有点像了，但还是不对。
   比较可行的思路是比如 n=5 时，5 个数产生 10 个差，最大的差自然是头尾之差，所以结尾数最小是 10。假如结尾数定为 10 的话，那从 1 到 10 的全部差都要用上，也就是必须要有差 9 和差 8，比较合理的就是安排上数字 1 和 8，这样 1 和 10 相差 9，0 和 8 相差 8。最后再定 1 和 8 中间的最后一个数，由于已经有差 1 和差 2 了，不能重复，所以只能从 4 5 里面选，不难发现两者都不符合。所以再考虑将结尾数定为 11，再同样操作，可以先安排上 1 和 9，然后再在 4 5 6 里面选，不难检验 {0, 1, 4, 9, 11} 是可以的。（注意这时候 1 和 9 不一定是必然的，因为此时的 10 个差没有全部用完从 1 到 11）

3. 5444412

   第一个数字选0的话，按照每个数较前一个数差值最小的原则，依次为0，1，3，7，12，20，30，44，65，90（即第十个数字最小是90）；再依次计算第一个数字选1、2、…依次类推。

   编程的思路应该是这样的：以第一个数字选0为例，从第三个数字开始依次计算第n个数A(n)与之前所有数字的差值并比对第n-1个数A(n)与之前所有数字的差值、第n-2个数A(n-2)与之前所有数字的差值（如果有的话）、…，在草稿上写出来是一个类似“金字塔”型数列，比对结果有重复的话则选择下一个最小的可选差值。
   然后计算第一个数字选1、2、……，第一个数的选择不会超过45，所以计算量应该不算大。

4. 5444493

   “`
   #include
   using namespace std;

   int arr[100];
   int cp = 1;
   int n;

   bool vis[100000];

   bool dfs() {
   if (cp == n) {
   return true;
   }
   for(int i = arr[cp – 1] + cp; i < 100; i++) {
   arr[cp] = i;
   for(int j = cp – 1; j >= 0; j–) {
   if (vis[arr[cp] – arr[j]]) {
   for(int k = cp – 1; k > j; k–) {
   vis[arr[cp] – arr[k]] = 0;
   }
   goto nxt;
   }
   vis[arr[cp] – arr[j]] = 1;
   }
   cp++;
   if(dfs()) return true;
   nxt:;
   }
   return false;
   }

   int main() {
   cin >> n;
   cout << dfs() << endl;
   for(int i = 0; i < n; i++) {
   cout << arr[i] << " ";
   }
   cout << endl;
   }
   “`

5. 5444524

   这是Golomb ruler，基本上没什么好的算法（估计是NP-hard，但是没有证明），现在的计算记录是Distributed.net的，得到了28个刻度的Golomb ruler：0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 585。这还是去年11月的事情，全球志愿者一共花了8.5年的计算时间。然后没有人挑战29个的，因为太困难了……

   其实构造一个足够好的并不是特别困难，但找到最好的就很难，证明它是最好的就更难……

6. 5444573

   我也贴一个

   def find(n):
   _ last=int(n*(n-1)/2)
   _ while check(n, last, {0, last}, {last}, last-int(n*(n-1)/2), last-1) == False:
   _ last=last+1
   _ print(last)

   def check(n, last, seq, diffs, skip, cur):
   _ if len(seq) == n:
   _ print(seq)
   _ return True
   _ if cur in diffs:
   _ return check(n, last, seq, diffs, skip, cur-1)
   _ else:
   _ if skip >= 1:
   _ if check(n, last, seq, diffs, skip-1, cur-1): return True
   _ for x in seq:
   _ if x-cur > 0 and x-cur not in seq:
   _ if xcheck(n, last, seq, diffs, x-cur, skip, cur): return True
   _ if x+cur < last and x+cur not in seq:
   _ if xcheck(n, last, seq, diffs, x+cur, skip, cur): return True
   _ return False

   def xcheck(n, last, seq, diffs, x, skip, cur):
   _ x_diffs = [abs(x-y) for y in seq]
   _ if max(x_diffs) > cur: return False
   _ if len(set(x_diffs)) != len(x_diffs): return False
   _ for d in x_diffs:
   _ if d in diffs: return False
   _ return check(n, last, seq|{x}, diffs|set(x_diffs), skip, cur-1)

7. 5444585

   @celk:
   这里思路还是我之前说的穷举法，从最大的差开始严格递减地填充进去（中途允许skip掉一些）
   find(n) 是从n*(n-1)/2开始对不同的last逐个尝试
   check(n, last, seq, diffs, skip, cur) 是有了部分的数列seq的情况下尝试加入一个数x使得往diffs里增加一个新的差cur
   xcheck(n, last, seq, diffs, x, skip, cur) 是检查加入数x是否可行，并递归调用check

   最后得到 find(10) = 55，一种取法是 {0, 1, 6, 10, 23, 26, 34, 41, 53, 55}，两两相减共45个差，和1~55相比，被跳过的那些差是51, 50, 48, 46, 44, 42, 39, 38, 37, 36

   至于其他的 n 得到的结果分别是 0, 1, 3, 6, 11, 17, 25, 34, 44, 55, 72, …
   {0}
   {0, 1}
   {0, 1, 3}
   {0, 1, 4, 6}
   {0, 2, 7, 8, 11}
   {0, 1, 4, 10, 12, 17}
   {0, 2, 3, 10, 16, 21, 25}
   {0, 1, 4, 9, 15, 22, 32, 34}
   {0, 1, 5, 12, 25, 27, 35, 41, 44}

8. 5445024

   贴个GPT3.5的答案

   假设选出的10个非负整数为a1, a2, …, a10，不妨将它们按从小到大的顺序排列，即：

   a1 < a2 < … < a10

   由题意可知，任意两个数的差均不相同，那么相邻两个数之间的差值应该是递增的。我们考虑将这些差值从小到大排列，设它们为d1, d2, …, d9，则有：

   d1 = a2 – a1
   d2 = a3 – a2
   …
   d9 = a10 – a9

   因为任意两个数的差全不相同，所以这些差值一定是10以内的连续整数。换言之，d1到d9应该是1到9的所有正整数。

   为了使A(10)取得最小值，我们需要让a10取得最大值。根据等差数列的性质可知，a10 = a1 + 9d9。因此，为了使a10取得最大值，我们需要让a1和d9分别取得最小值和最大值，即：

   a1 = 0
   d9 = 9

   此时，d1到d8应该是1到8的所有正整数。根据上述式子可知，此时a10取得最大值，即a10 = 0 + 9 × 9 = 81。

   因此，选出的10个数为0, 1, 3, 6, 10, 15, 21, 28, 36, 45，它们从小到大排列为0, 1, 3, 6, 10, 15, 21, 28, 36, 45，其中最大值为81。