这是一个创建于 1386 天前的主题，其中的信息可能已经有所发展或是发生改变。
已知：允许两个组合之间一个数字相同，5 个整数的组合，1000 个组合至少需要多少个整数？
组合 1：1，2，3，4，5
组合 2：1，6，7，8，9
组合 3：2，6，10，11，12
...
已知：允许两个组合之间一个数字相同，5 个整数的组合，1000 个组合至少需要多少个整数？ 组合 1：1，2，3，4，5 组合 2：1，6，7，8，9 组合 3：2，6，10，11，12 谢谢，求多少个，付费求解。
 |
1
waytoexplorewhat 2021-02-09 20:02:16 +08:00
两个组合之间一个数字相同，那 1000 个组合共用 1 个整数，其他数字不同就好了。共 4001 个整数
|
 |
2
chocovon 2021-02-09 20:45:28 +08:00
每 15 个数就可以刚好生成 6 个组合，所以只需要 1000/6=166 个这样的 15 个数生成 996 个组合，余下 4 个组合需要至少 14 个数，总共至少需要 166*15+14=2504 个数
|
 |
3
Raven316 2021-02-09 21:36:36 +08:00
我没法用数学的方法来计算，所以我写了一个程序，然后跑了一下。
程序的思路是： 一开始只有一个元素的 list：[[1,2,3,4,5]] 接下来尝试 999 次扩张这个数组： 1 如果可以不增加所有数组的最大值的情况下，添加一个 5 整数组合，那就添加进去 2 如果在不增加最大值的情况下无法添加组合，那么遍历所有可能，取增加最大值幅度最小的可能。（在某个时间以后，增加的幅度不是 0 就是 1，我无法证明为什么，只是观察到这个现象） 注意：以上有两个原则 1 没有取所有可能，只是取了增加最大值幅度最小的可能 2 没有取所有同等条件的可能，只是任意取了一个。 因为我发现如果穷举的话，个人电脑是不可能的，而且我是用 python 写的程序。 以下稍微证明一下程序的逻辑（不严谨，但是我相信是正确的）： 明确一个概念： 首先在这个 list 中，所有数字的地位都是同等的，他们只是不同的 symbol，因为并没有数学运算，所以，你可以想象，给定 5 个数字，最多一个组合，给定 9 个数字，最多两个组合，等等，组合个数和数字个数必然是单调的递增关系，因此，我的做法相当于，先尽量利用目前已有的数字个数，得出现有的数字个数可能的最大组合数，然后增加数字的数量，幅度取最小的可能，再把多出来的数字利用完（这里可以显然看出一下子增加过多的数字是没有任何必要的，应该取增加数字个数最小的幅度，而且在程序运行的实际结果看来，在后期基本上都是一次增加一个数字） 那么为什么任取一种可能是正确的呢？ 你会发现如果给定 9 个数字，有很多种可能 例如： [1,2,3,4,5],[1,6,7,8,9] [1,2,3,4,5],[2,6,7,8,9] ... 等等 但是它们都是“同构”的，你可以想象这些组合可能有很多种，但是具有相同的结构。 因此，给定一个数字上限，你把它可能有的所有组合全部找了出来，你就找出了唯一可能的结构，具体形式是不重要的。这是我对随便取一种可能的证明（非常不严谨，我其实也有怀疑）。 我跑的结果 167 |
|
4
Raven316 2021-02-09 21:41:39 +08:00
|
 |
9
neteroster 2021-02-09 22:39:34 +08:00
我认为 #2 正确。
|
|
10
neteroster 2021-02-09 22:48:15 +08:00
C1 = {A1,A2,A3,A4,A5}
C2 = {A1,A6,A7,A8,A9} C3 = {A2,A6,A10,A11,A12} C4 = {A3,A7,A10,A13,A14} C5 = {A4,A8,A11,A13,A15} C6 = {A5,A9,A12,A14,A15} --- 可以发现，C7 将无法使用 A1 - A15 中的任意一个数，因为 C1 - C6 中的每一个元素均被使用两次。形成 1000 组数就需要 166 个这样的 C1 - C6，并且还需要一组 (C1 - C4 （注意 C4 的最后一个数是 14 ）)，也就是 (166*15 + 14) 个数。 |
 |
11
XiaoxiaoPu 2021-02-09 23:04:02 +08:00
@neteroster 有问题的。C7 不能使用 A1-A15，不代表后面的集合不能用。
|
|
12
Raven316 2021-02-09 23:36:21 +08:00
@neteroster 兄弟你写答案之前看看我 python 跑出来的答案呗，我觉得 167 就够了
|
|
13
neteroster 2021-02-09 23:55:11 +08:00 via Android
@XiaoxiaoPu @Raven316 确实应该是我理解错了，我之前想成：不允许一个数字同时出现在两组以上了，仔细想想楼主应该不是这个意思。
|
 |
14
BiteTheDust 2021-02-10 00:06:50 +08:00
n 个数能构成的 5 元组数量似乎与 The Kruskal-Macaulay function K_5(n)很相似？
oeis.org/A123574 |
Select Language