在 1～500 中任意取 5 个不同整数，使得这 5 个数之和能被 5 整除，有几种不同取法？

天山草 · 发表于 2021-8-1 08:05

本帖最后由天山草于 2021-8-1 08:49 编辑

王守恩发表于 2021-7-31 15:58
帖子有点乱，先确认一下，下面的结论成立吗？有反例吗？
在 1～n 中任意取 P 个不同整数，使得这 P 个数 ...

王守恩，昨天我已将此难题发到【数学研发论坛 - 难题征解】栏，看看准数学家们的反应。在下面这个帖子中，引用了陆教授的一个公式和你的两个公式。你可看一看。

【新提醒】从 1～n 这 n 个正整数中取出 m 个数，其和能被 m 整除。问：有多少种不同的取法？ - 难题征解 - 数学研发论坛 - Powered by Discuz!
https://bbs.emath.ac.cn/forum.ph ... ;tid=17953#lastpost

天山草 · 发表于 2021-8-1 18:12

@王守恩，那个验证程序可以简化如下，以 p=7, 共有 20 个数为例：

p = 7; n = 20;
lst = Range[n];
a = Subsets[lst, {p}];
L = Length[a]; k = 0;
Do[b = a[[i]];
If[Mod[Sum[b[[j]], {j, 1, p}], p] == 0, k = k + 1], {i, 1, L}];
Print[k];
\[LeftCeiling](Binomial[n, p] + 4 \[LeftFloor]n/p\[RightFloor])/
p\[RightCeiling] (*陆教授公式, p 为奇素数*)
\[LeftFloor]Binomial[n, p]/p\[RightFloor] + \[LeftFloor]n/
p\[RightFloor] - \[LeftFloor]n/
p^2\[RightFloor] (*王守恩公式, p 为奇素数*)

复制代码

独舟星海 · 发表于 2021-8-1 20:23

本帖最后由独舟星海于 2021-8-1 20:25 编辑

用什么法则可以使上面的每一种取法对应着线性不定方程的一组正整数解？x+y+z+u+v+w=501，这里有501个1，排列成一排，1与1之间有500个空位，现在拿5块挡板放在500空位的5个空位上，则可以把501个1，分成有序的6份，第一份对应x，第二份对应y，.....，第6份对应w，这样每一种放挡板法就是方程的一组解，所以放挡板的方法数就是线性不定方程的正整数解组数，那个方程共有\(C_{501-1}^{6-1}\)=\(C_{500}^{5}\)组解，与从 1~500 之间任意取 5个不同的整数的取法数相同，现在的问题是：如何使它们的每一种方法形成一一对应关系，求法则。

独舟星海 · 发表于 2021-8-1 20:29

独舟星海发表于 2021-8-1 20:23
用什么法则可以使上面的每一种取法对应着线性不定方程的一组正整数解？x+y+z+u+v+w=501，这里有501个1，排 ...

如果能找到对应法则，形成一一映射对应关系，则可以有新的方法解决此类问题，从mn个连续数字中抽取m个不同数字，它们的和能整除m的抽取方法数。

独舟星海 · 发表于 2021-8-1 20:49

独舟星海发表于 2021-8-1 20:23
用什么法则可以使上面的每一种取法对应着线性不定方程的一组正整数解？x+y+z+u+v+w=501，这里有501个1，排 ...

我们可以令x=1,2,3，.....，493,494,495,496，则此时原方程分成了496个5元1次方程：y+z+u+v+w=500,499,498，.....，9,8,7,6,5，则每个方程的解组数分别对应着：\(C_{500-1}^{5-1}\),\(C_{499-1}^{5-1}\),\(C_{498-1}^{5-1}\),\(C_{497-1}^{5-1}\),......,\(C_{9-1}^{5-1}\),\(C_{8-1}^{5-1}\),\(C_{7-1}^{5-1}\),\(C_{6-1}^{5-1}\),\(C_{5-1}^{5-1}\)。
此时，我还是不能建立一一对应关系。

独舟星海 · 发表于 2021-8-2 08:57

序号元1 元2 元3 元4 元5 和余数单序
1 0 0 0 0 0 0 0 1
2 1 1 1 1 1 5 0 2
3 2 2 2 2 2 10 0 3
4 3 3 3 3 3 15 0 4
5 4 4 4 4 4 20 0 5
6 0 0 0 0 1 1 1 1
7 0 0 0 0 2 2 2 2
8 0 0 0 0 3 3 3 3
9 0 0 0 0 4 4 4 4
10 1 1 1 1 0 4 4 5
11 1 1 1 1 2 6 1 6
12 1 1 1 1 3 7 2 7
13 1 1 1 1 4 8 3 8
14 2 2 2 2 0 8 3 9
15 2 2 2 2 1 9 4 10
16 2 2 2 2 3 11 1 11
17 2 2 2 2 4 12 2 12
18 3 3 3 3 0 12 2 13
19 3 3 3 3 1 13 3 14
20 3 3 3 3 2 14 4 15
21 3 3 3 3 4 16 1 16
22 4 4 4 4 0 16 1 17
23 4 4 4 4 1 17 2 18
24 4 4 4 4 2 18 3 19
25 4 4 4 4 3 19 4 20
26 0 0 0 1 1 2 2 1
27 0 0 0 2 2 4 4 2
28 0 0 0 3 3 6 1 3
29 0 0 0 4 4 8 3 4
30 1 1 1 0 0 3 3 5
31 1 1 1 2 2 7 2 6
32 1 1 1 3 3 9 4 7
33 1 1 1 4 4 11 1 8
34 2 2 2 0 0 6 1 9
35 2 2 2 1 1 8 3 10
36 2 2 2 3 3 12 2 11
37 2 2 2 4 4 14 4 12
38 3 3 3 0 0 9 4 13
39 3 3 3 1 1 11 1 14
40 3 3 3 2 2 13 3 15
41 3 3 3 4 4 17 2 16
42 4 4 4 0 0 12 2 17
43 4 4 4 1 1 14 4 18
44 4 4 4 2 2 16 1 19
45 4 4 4 3 3 18 3 20
46 0 0 0 1 2 3 3 1
47 0 0 0 1 3 4 4 2
48 0 0 0 1 4 5 0 3
49 0 0 0 2 3 5 0 4
50 0 0 0 2 4 6 1 5
51 0 0 0 3 4 7 2 6
52 1 1 1 0 2 5 0 7
53 1 1 1 0 3 6 1 8
54 1 1 1 0 4 7 2 9
55 1 1 1 2 3 8 3 10
56 1 1 1 2 4 9 4 11
57 1 1 1 3 4 10 0 12
58 2 2 2 0 1 7 2 13
59 2 2 2 0 3 9 4 14
60 2 2 2 0 4 10 0 15
61 2 2 2 1 3 10 0 16
62 2 2 2 1 4 11 1 17
63 2 2 2 3 4 13 3 18
64 3 3 3 0 1 10 0 19
65 3 3 3 0 2 11 1 20
66 3 3 3 0 4 13 3 21
67 3 3 3 1 2 12 2 22
68 3 3 3 1 4 14 4 23
69 3 3 3 2 4 15 0 24
70 4 4 4 0 1 13 3 25
71 4 4 4 0 2 14 4 26
72 4 4 4 0 3 15 0 27
73 4 4 4 1 2 15 0 28
74 4 4 4 1 3 16 1 29
75 4 4 4 2 3 17 2 30
76 0 0 1 1 2 4 4 1
77 0 0 1 1 3 5 0 2
79 0 0 2 2 1 5 0 4
78 0 0 1 1 4 6 1 3
103 2 2 1 1 0 6 1 28
80 0 0 2 2 3 7 2 5
112 3 3 0 0 1 7 2 37
81 0 0 2 2 4 8 3 6
83 0 0 3 3 2 8 3 8
94 1 1 3 3 0 8 3 19
85 0 0 4 4 1 9 4 10
92 1 1 2 2 3 9 4 17
84 0 0 3 3 4 10 0 9
86 0 0 4 4 2 10 0 11
93 1 1 2 2 4 10 0 18
95 1 1 3 3 2 10 0 20
97 1 1 4 4 0 10 0 22
106 2 2 3 3 0 10 0 31
87 0 0 4 4 3 11 1 12
107 2 2 3 3 1 11 1 32
96 1 1 3 3 4 12 2 21
98 1 1 4 4 2 12 2 23
109 2 2 4 4 0 12 2 34
99 1 1 4 4 3 13 3 24
110 2 2 4 4 1 13 3 35
108 2 2 3 3 4 14 4 33
133 4 4 3 3 0 14 4 58
111 2 2 4 4 3 15 0 36
122 3 3 4 4 1 15 0 47
135 4 4 3 3 2 16 1 60
136 0 0 1 2 3 6 1 1
137 0 0 1 2 4 7 2 2
138 0 0 1 3 4 8 3 3
139 0 0 2 3 4 9 4 4
140 1 1 0 2 3 7 2 5
141 1 1 0 2 4 8 3 6
142 1 1 0 3 4 9 4 7
143 1 1 2 3 4 11 1 8
144 2 2 0 1 3 8 3 9
145 2 2 0 1 4 9 4 10
146 2 2 0 3 4 11 1 11
147 2 2 1 3 4 12 2 12
148 3 3 0 1 2 9 4 13
149 3 3 0 1 4 11 1 14
150 3 3 0 2 4 12 2 15
151 3 3 1 2 4 13 3 16
152 4 4 0 1 2 11 1 17
153 4 4 0 1 3 12 2 18
154 4 4 0 2 3 13 3 19
155 4 4 1 2 3 14 4 20
156 0 1 2 3 4 10 0 1
5的无序拆分，然后再组合，共有126种方法。余数0占26种组合方式，其余的都占25种组合。所以\(C_{500}^5\)/126*26=52669538711

独舟星海 · 发表于 2021-8-2 09:15

答案与以前楼的不一致，说明各种组合并不一致，一种组合方法的差距应该是那种分拆组合方式中的，除了最后一组外，其余分拆组合方式都一致，所以，最后一种单列，从总组合方法中单独分开最后一种组合方式，从每类余数中抽取一个自然数，则有100^5=10^10,(\(C_{500}^5\)-10^10)/5+10^10=59048937520

独舟星海 · 发表于 2021-8-2 09:39

4个相同 5=4+1组合表示4个同，1个异

5*4=20种拆成2组
分成两派，需要2步
3个相同 2个相同 5=3+2 拆成2组

5*4=20 分成2派，需要2步
2分法中没有组合方法。
2个同 3个不同 5=2+1+1+1 拆成4组
C(5,1)*C( 4,3)=5*4=20 分成4派，需要4步
4分法中也没有组合方法。
5个相同 5的拆分 5=5 表示5个相同
5*1=5种
拆成1组
1分法中，5种组合法占5种；
3个相同 2个不同 5=3+1+1 拆成3组
C(4,2)=6 分成3派，需要3步
5*4*3/2
3分法中，30种方法占10种方法，即1/3；
2个同2个同1个不同 5=2+2+1 拆成3组
分成3派，需要3步
C(5,1)*C( 4,1)*C(3,1) 60
2与2可置换或交换所以除2=30种
这种3分法中，30种方法占10种方法，即1/3；
5个不同 5=1+1+1+1+1 拆成5组
5分法中，1种方法占1种。
以上26种方法，全部给出，单独分析它占有的组合方法，安比例求值，相加即可。

lihp2020 · 发表于 2021-8-2 09:40

我周末认真考虑现在又有两个收获
1  证明当N是素数  那个公式的正确性
2  当N是素数的单乘积  也是有方法求通项公式也是比较简单的
单乘积是指比如N=2*3*5  N=3*7  因式分解  不存在两个及以上的相同质数相乘如 n=3*3*5
当然我认为这些也是可以解决的  但是思路还没有想到
周一又开始上班  可能要慢慢分享出来

独舟星海 · 发表于 2021-8-2 09:44

最后回到了luyuanhong教授的方法上。之所以整除m的比其他模m的其他余数多一种组合方法，这是导致整除m的抽取方法数多的根本原因。

		自动登录	找回密码
密码			注册

在 1～500 中任意取 5 个不同整数，使得这 5 个数之和能被 5 整除，有几种不同取法？

评分

点评