从 1～n 中取 k 个不同的数相加求和，求这个和的末位数等于 0,1,2,…,9 的频数

王守恩

cooooldog 发表于 2017-8-29 17:20
陆老师, 您可以试试从 1~15 中取3个

{47, 45, 46, 44, 45, 44, 46, 45, 47, 46}

小结。
题：  从 1～n 中取 k 个不同的数相加求和，求这个和的末位数等于 0,1,2,…,9 的频数。
我们只要解决：  从 1～n 中取 k 个不同的数相加求和，求某个和出现的频数。
至于后半部分：求这个和的末位数等于 0,1,2,…,9 的频数。
这里说的模数是10，当然模数可以是任意数。可以说没有难度。
本人可以解决：  从 1～n 中取 k 个不同的数相加求和，求某个和出现的频数。
当然，不一定非得从1开始。
谢谢cooooldog、谢谢luyuanhong、谢谢天山草。

王守恩

cooooldog 发表于 2017-8-29 09:48
这题一般情况我自己也做不出的; 用计算机穷举小的数字还行;大一些就困难了.

我现在出的这数字, 是一般 ...

挺不错的题目。谢谢陆老师！谢谢cooooldog！想你了！

lihp2020

很久以前的帖子 我以前没有翻到  
但这个问题我觉得我可以解决
从 1～n 中取 k 个不同的数相加求和，求这个和的末位数等于 0,1,2,…,9 的频数
1 把数据 分成10堆  按尾数分 分成 **0 **1 **9  
这样分类 如果  每堆一样多 那么 这样 可以利用 对称性质算出  0,1,2,…,9  =的个数 （频数=个数/总数 我们主要求个数）
2 1~n  如果不能分成一样多 假设 n=102  那么 就是多了2个数剩下 101 和102 两个数 没法放进去
那我们就单独分析 带101或者带102 的

王守恩

lihp2020 发表于 2021-11-22 10:09
很久以前的帖子 我以前没有翻到  
但这个问题我觉得我可以解决
从 1～n 中取 k 个不同的数相加求和，求 ...

不搞复杂，做具体的题目：

从1到93这93个自然数中任取两两不等的9个数, 把它们相加得到一个和;

这个和的末位整数可能分别是0,1,2,3,...,7,8,9

求,末位整数的这十种不同情况出现的频数各是多少?

lihp2020

从1到93这93个自然数中任取两两不等的2个数, 把它们相加得到一个和;
ps(9确实太大 不好分析改成了2)
这个和的末位整数可能分别是0,1,2,3,...,7,8,9
----A----
先只考虑 1~90
把数据分成10分

1 11 21 31     81
2 12 22 32     83
。。。
10 20 30       90
10组
每组 9个数据
1 不同组组合 (就是不能旋转11 与21组合)
其中
余数
        0 2,9)(2,8)(3,7)(4,6) 4种组合  就是 9*9*4
        1 0,1)(2,9)(3,8)(4,7)(5,6) 5种组合 就是 9*9*5
        2 0,2)(3,9)(4,8)(5,7) 4种组合  就是 9*9*4
        3 :(0,3)(1,2)(4,9)(5,8)(6,7) 5种组合 就是 9*9*5
        4 :(0,4)(1,3)(5,9)(6,8) 4种组合  就是 9*9*4
        5 :(0,5)(1,4)(2,3)(6,9)(7,8) 5种组合 就是 9*9*5
        6 :(0,6)(1,5)(2,4)(7,9) 4种组合  就是 9*9*4
        7 :(0,7)(1,6)(2,5)(3,4)(8,9) 5种组合 就是 9*9*5
        8 :(0,8)(1,7)(2,6)(3,5) 4种组合  就是 9*9*4
        9 :(0,9)(1,8)(2,7)(3,6)(4,5) 5种组合 就是 9*9*5
       
验证是否正确
组合是4*5+5*5 =45 =C（10,2） (10种余数选两个不相同的)
2同组组合
00 11 22 33 44 55 66 77 88 99
分别与 0 2 4 6 8
余 0/2/4/6/8 的个数是 2(任意余数有两种类型 0的是00 和55)*C(9,2)

余任意奇数的组合有9*9*5 = 405
余任意偶数的组合有9*9*4+2*C(9,2)=324+72=396

验证一波数据是否正确
一共有C(90,2)=4005 而405*5+396*5 =4005 验证一下 总数至少正确

还多余3个数字 91 92 93
----B1----
这个三个数分别 和其它数据(1~90) 求余数
如91 与(1~90) 求余数有90个分别有9个余0 9个余1。。。
所以 任意一个与其它数据 都要 9个不同的余数
---B2---
91 92 93 两两求余 就简单多了
分别是 3 4 5 三个数据
所以
余任意偶数(4除外)的组合有396+3*9
余任意奇数(3 5除外)的组合有405+3*9

余4的组合有396+3*9+1
余(3 5)的组合有405+3*9+1


tips 405-396 =9 按照我以前有个帖子
【在 1～500 中任意取 5 个不同整数，使得这 5 个数之和能被 5 整除，有几种不同取法】
内部有个结论 每一个周期 就会有点变化。。。
所以对---A----部分  
一般可以得到一个结论
从1到nm这nm个自然数中任取两两不等的k个数, 把它们相加得到一个和就这个数被M除余数（1~m-1）的有多少种;
一部分的组合 是a个 部分的组合是b  则 a-b = n (或者是关于n的函数)
直接(C(nm,k)+-kn)/m   其中+-k   就要分析是那一部分 有哪些类了  应该和欧拉函数有关
当然 这个 我没法证明

而且现在 K=2 的出来了
能否使用K =2 求K=3？

当然 也只是求A部分 ---

9确实太大了 我后面分析一下

lihp2020

从1到nm这nm个自然数中任取两两不等的k个数, 把它们相加得到一个和就这个数被M除余数（1~m-1）的有多少种;
如果gdb（m,k）=1 那么余任意数都是C（nm，k）/M

王守恩

从1到93这93个自然数中任取两两不等的9个数, 把它们相加得到一个和;

这个和的末位整数可能分别是0,1,2,3,...,7,8,9

求,末位整数的这十种不同情况出现的频数各是多少?

注意: 组合数 binomial(93,9)=961,835,834,245 肯定不是平均分配到每个数字上的,否则会有小数.

还有比这更难的题目吗？！！！

王守恩

了却一桩心事！！挺不错的题目。谢谢陆老师！谢谢cooooldog！想你了！

CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\bigg(\prod_{i=1}^{84}\frac{x^{94}-x^i}{x^i-1}\bigg)x^{-3570},(x,0,756)\bigg],x\bigg]\)

{1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 41, 54, 73, 94, 123, 157, 201, 252, 318, 393, 488, 598, 732, 887,
1076,1291, 1549, 1845, 2194, 2592, 3060, 3589, 4206, 4904, 5708, 6615, 7657, 8824,  10156,
11648, 13338, 15224, 17354, 19720, 22380, 25331, 28629, 32278, 36347,40831,45812,51294,
57358,64015,71362, 79403, 88252, 97922, 108527, 120092, 132751, 146520, 161554, 177884,
195666, 214944, 235899, 258569, 283161, 309729, 338484, 369499, 403016, 439100, 478025,
519880, 564945, 613331, 665355, 721125, 780997, 845105, 913815, 987292, 1065947, 1149940,
1239730, 1335513, 1437762, 1546707, 1662875, 1786498, 1918159, 2058130, 2207014, 2365128,
2533138, 2711363, 2900536, 3101027, 3313594, 3538657, 3777049, 4029199, 4296017, 4577988,
4876054, 5190763, 5523142, 5873748, 6243698, 6633618, 7044663, 7477526, 7933460, 8413176,
8918027, 9448798, 10006888,  10593163,  11209130,  11855672, 12534410, 13246314, 13993056,
14775691, 15596013, 16455101, 17354873, 18296499, 19281955, 20312509, 21390268, 22516522,
23693514, 24922637, 26206195, 27545681, 28943542, 30401298, 31921540, 33505891, 35157009,
36876627, 38667552, 40531537, 42471543, 44489436, 46588241, 48769932, 51037692, 53393516,
55840744, 58381479, 61019126, 63755901, 66595368, 69539751, 72592776, 75756778, 79035540,
82431501, 85948605, 89589293, 93357667, 97256267,    101289245,    105459243,     109770567,
114225838, 118829517, 123584320, 128494739, 133563574, 138795465, 144193176, 149761487,
155503235, 161423215, 167524336, 173811523, 180287616, 186957668, 193824577, 200893381,
208167022, 215650651, 223347116, 231261670, 239397187, 247758877, 256349637, 265174762,
274237010, 283541755, 293091757, 302892307, 312946148, 323258630, 333832322, 344672617,
355782044, 367165875, 378826593, 390769489, 402996819, 415513886,428322873, 441428912,
454834092, 468543531, 482559047, 496885726, 511525264, 526482531, 541759093, 557359760,
573285767, 589541854, 606129097, 623051964, 640311348, 657911619, 675853292, 694140619,
712773902, 731757073, 751090214, 770777110, 790817402, 811214719, 831968452, 853081852,
874554037, 896388074, 918582594, 941140461,964060005,987343667,1010989469,1034999623,
1059371606, 1084107393, 1109204129, 1134663313, 1160481737, 1186660641, 1213196234,
1240089481, 1267336216, 1294936893, 1322886970, 1351186608, 1379830634, 1408818914,
1438145884, 1467810859, 1497807868, 1528135918, 1558788388, 1589763966, 1621055615,
1652661456, 1684574041, 1716791167, 1749304709, 1782112145, 1815204938, 1848579981,
1882228317, 1916146522, 1950324966, 1984759905, 2019441296, 2054364816, 2089520024,
2124902287, 2160500490, 2196309704, 2232318431, 2268521171, 2304906043, 2341467270,
2378192329, 2415075170, 2452102912, 2489268968, 2526560123, 2563969544, 2601483400,
2639094636, 2676789120, 2714559293, 2752390731, 2790275688, 2828199183, 2866153296,
2904122796, 2942099318, 2980067414, 3018018588, 3055936887, 3093813715, 3131632951,
3169385612, 3207055425, 3244633357, 3282102714, 3319454433, 3356671724, 3393745219,
3430658073, 3467400943, 3503956636, 3540315872, 3576461465, 3612383904, 3648066032,
3683498462, 3718663790, 3753552777, 3788148113, 3822440426, 3856412545, 3890055309,
3923351387, 3956291870, 3988859635, 4021045724, 4052833246, 4084213559, 4115169723,
4145693438, 4175768064, 4205385354, 4234529015, 4263191205, 4291355669, 4319015011,
4346153390, 4372763545, 4398830071, 4424346213, 4449296711, 4473675337, 4497467330,
4520666691, 4543259199, 4565239437, 4586593406, 4607316307, 4627394737, 4646824193,
4665591885, 4683693975, 4701117983, 4717860750, 4733910457, 4749264314, 4763911196,
4777849031, 4791067057, 4803563947, 4815329672, 4826363315, 4836655586, 4846206342,
4855006717, 4863057344, 4870350125, 4876886147, 4882658102, 4887667871, 4891908593,
4895382960, 4898084917, 4900017619, 4901175813, 4901563471, 4901175813, 4900017619,
4898084917, 4895382960, 4891908593, 4887667871, 4882658102, 4876886147, 4870350125,
4863057344, 4855006717, 4846206342, 4836655586, 4826363315, 4815329672, 4803563947,
4791067057, 4777849031, 4763911196, 4749264314, 4733910457, 4717860750, 4701117983,
4683693975, 4665591885, 4646824193, 4627394737, 4607316307, 4586593406, 4565239437,
4543259199, 4520666691, 4497467330, 4473675337, 4449296711, 4424346213, 4398830071,
4372763545, 4346153390, 4319015011, 4291355669, 4263191205, 4234529015, 4205385354,
4175768064, 4145693438, 4115169723, 4084213559, 4052833246, 4021045724, 3988859635,
3956291870, 3923351387, 3890055309, 3856412545, 3822440426, 3788148113, 3753552777,
3718663790, 3683498462, 3648066032, 3612383904, 3576461465, 3540315872, 3503956636,
3467400943, 3430658073, 3393745219, 3356671724, 3319454433, 3282102714, 3244633357,
3207055425, 3169385612, 3131632951, 3093813715, 3055936887, 3018018588, 2980067414,
2942099318, 2904122796, 2866153296, 2828199183, 2790275688, 2752390731, 2714559293,
2676789120, 2639094636, 2601483400, 2563969544, 2526560123, 2489268968, 2452102912,
2415075170, 2378192329, 2341467270, 2304906043, 2268521171, 2232318431, 2196309704,
2160500490, 2124902287, 2089520024, 2054364816, 2019441296, 1984759905, 1950324966,
1916146522, 1882228317, 1848579981, 1815204938, 1782112145, 1749304709, 1716791167,
1684574041, 1652661456, 1621055615, 1589763966, 1558788388, 1528135918, 1497807868,
1467810859, 1438145884, 1408818914, 1379830634, 1351186608, 1322886970, 1294936893,
1267336216, 1240089481, 1213196234, 1186660641, 1160481737, 1134663313, 1109204129,
1084107393, 1059371606, 1034999623, 1010989469,  987343667,   964060005,   941140461,
918582594, 896388074, 874554037, 853081852, 831968452, 811214719, 790817402, 770777110,
751090214, 731757073, 712773902, 694140619, 675853292, 657911619, 640311348, 623051964,
606129097, 589541854, 573285767, 557359760, 541759093, 526482531, 511525264, 496885726,
482559047, 468543531, 454834092, 441428912, 428322873, 415513886, 402996819, 390769489,
378826593, 367165875, 355782044, 344672617, 333832322, 323258630, 312946148, 302892307,
293091757, 283541755, 274237010, 265174762, 256349637, 247758877, 239397187, 231261670,
223347116, 215650651, 208167022, 200893381, 193824577, 186957668, 180287616, 173811523,
167524336, 161423215, 155503235, 149761487, 144193176, 138795465, 133563574, 128494739,
123584320, 118829517, 114225838, 109770567, 105459243, 101289245,   97256267,   93357667,
89589293, 85948605, 82431501, 79035540, 75756778, 72592776, 69539751,66595368, 63755901,
61019126, 58381479, 55840744, 53393516, 51037692, 48769932, 46588241, 44489436, 42471543,
40531537, 38667552, 36876627, 35157009, 33505891, 31921540, 30401298, 28943542, 27545681,
26206195, 24922637, 23693514, 22516522, 21390268, 20312509, 19281955, 18296499, 17354873,
16455101, 15596013, 14775691, 13993056, 13246314, 12534410, 11855672, 11209130, 10593163,
10006888, 9448798, 8918027, 8413176, 7933460, 7477526, 7044663, 6633618, 6243698, 5873748,
5523142, 5190763, 4876054, 4577988, 4296017, 4029199, 3777049, 3538657, 3313594, 3101027,
2900536, 2711363, 2533138, 2365128, 2207014, 2058130, 1918159, 1786498, 1662875, 1546707,
1437762, 1335513, 1239730, 1149940, 1065947, 987292, 913815, 845105,780997,721125,665355,
613331, 564945, 519880, 478025, 439100, 403016, 369499, 338484,  309729,    283161,    258569,
235899, 214944, 195666, 177884, 161554, 146520, 132751, 120092, 108527, 97922, 88252, 79403,
71362,64015, 57358, 51294,45812, 40831,36347, 32278, 28629,25331, 22380, 19720,17354, 15224,
13338,11648, 10156, 8824, 7657, 6615, 5708, 4904,4206, 3589, 3060, 2592, 2194, 1845, 1549, 1291,
1076, 887, 732, 598, 488, 393, 318, 252, 201, 157, 123, 94, 73, 54, 41, 30, 22, 15, 11, 7, 5, 3, 2, 1, 1}

王守恩

从1到93这93个自然数中任取两两不等的9个数, 把它们相加得到一个和;

这个和的末位整数可能分别是0,1,2,3,...,7,8,9

求,末位整数的这十种不同情况出现的频数各是多少?

注意: 组合数 binomial(93,9)=961,835,834,245 肯定不是平均分配到每个数字上的,否则会有小数.

挑战一一下！！！！

从1到365这365个自然数中任取两两不等的12个数, 把它们相加得到一个和;

这个和的末位整数可能分别是0,1,2,3,...,7,8,9

求,末位整数的这十种不同情况出现的频数各是多少?

注意: 组合数 binomial(365,12)=9,723,205,992,282,927,449,305 肯定不是平均分配到每个数字上的,否则会有小数.

还有比这更难的题目吗？！！！

lihp2020

通过两三年 的学习 和巩固 我觉得 我现在 能做这到题了
1 还是 把 1~93 分成  1~90    91 92 93
[分段规则 ：
从 1～n 中取 k 个不同的数相加求和，求这个和关于p的余数个数 把 n 分段成 p的倍数 和剩下的部分]
2 求出 [1~90] 任意取 9，8，7，6 个的不同的数求和关于10的余数个数
准备知识
gdb(10,9)=1 gdb(10,8)=1 gdb(10,7)=1         gdb(10,6)=2
        10 =2*5
90+1 我们标记成 1  1-2 我们标记成 89 (循环 有点像 数域的东西)
        [1,90] 任意选  9个数 的被10 整除  余 0123456789 是一样多的
    [1,90] 任意选  8个数 的被5 整除  余 01234 是一样多的
    [1,90] 任意选  8个数 的被2 整除  余 01是 不一样多的

证明这个东西  
a  对应任意一个结果 lg[1,3,4,6,7,8,70,88,90]  对 每个元素 +1~9  都有对应的序列  但他们的余数 都是1到9 不同  原因 就是 9个元素 每个+1  整体+9  gdb(9,10)=1
b [1,90] 任意选  8个数 的被2 整除  余 01是 不一样多的
        这个 为啥 是因为 任意一种结果 对每个元素+1~9  他们的奇偶性是不变的

以上信息 可以得到
[1~90] 任意取 9个的不同的数求和关于10的余数个数都是 C（90,9）/10
[1~90] 任意取 7个的不同的数求和关于10的余数个数都是 C（90,7）/10


[1~90] 任意取 8个的不同的数求和关于10的余数个数
先求奇偶  
如果 是偶数 一定是(0奇8偶,2奇6偶 4奇4偶 6奇2偶  8奇0偶)
一共有 C(45,0)* C(45,8) +  C(45,2)* C(45,6) +.. 计为Num8偶

同理 就奇数
计为Num8奇
(验证一下Num8偶 +Num8奇=C(90,8))
[1,90] 任意选  8个数 的被5 整除  余 01234 是一样多的
[1,90] 任意选  8个数 的被10 整除  余 02468 都有 Num8偶/5
[1,90] 任意选  8个数 的被10 整除  余 13579 都有 Num8奇/5



再来同理

[1,90] 任意选  6个数 的被10 整除  余 02468 都有 Num6偶/5
[1,90] 任意选  6个数 的被10 整除  余 13579 都有 Num6奇/5

3   现在 考虑 91 92 93 3个数 2^3=8

1 无91 92 93
2 只有91
3 只有92
。。
8 91 92 93 都存在

再来计算
余数是0 的情况
C（90,9）/10 +Num8偶/5 + Num8奇/5*2 + C（90,7）/10*3 +Num6偶/5


总结 余数是奇数 12579 一共有
C（90,9）/10 +Num8奇/5 + Num8偶/5*2 + C（90,7）/10*3 +Num6奇/5
总结 余数是偶数 02468 一共有
C（90,9）/10 +Num8偶/5 + Num8奇/5*2 + C（90,7）/10*3 +Num6偶/5