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

cooooldog

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

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

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

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

ccmmjj

不知什么时候起，我只对几何题有兴趣。这个问题直觉上不是难题，只是计算麻烦。如果有专门使用计算软件的人应该是可以交给计算机完成的问题。有一位叫eq的还有一位天山草的擅长使用计算机。如果只是要求组合概率问题lu老师是这方面的专家。我吧，只是偶尔来看看。

cooooldog

ccmmjj 发表于 2017-8-28 10:49
不知什么时候起，我只对几何题有兴趣。这个问题直觉上不是难题，只是计算麻烦。如果有专门使用计算软件的人 ...

陆老师的课主要有, pascal语言, 数据结构, 概率统计, 数学建模,

你不用怕写错, 就是大陆的陆. 没关系, 你只做几何题也行. 这道题的确比较伤脑筋.

王守恩

1，任取两两不等的9个数相加，和最小是45，最大是801。
2，我们用S(45)=1表示和45的拆分方法是1种。
3，则有
S(45)=S(801)=1
S(46)=S(800)=1
S(47)=S(799)=2
S(48)=S(798)=3
S(49)=S(797)=5
S(50)=S(796)=7
S(51)=S(795)=11
S(52)=S(794)=15
S(53)=S(793)=22
S(54)=S(792)=30
S(55)=S(791)=41
S(56)=S(790)=54
S(57)=S(789)=73
S(58)=S(788)=94
S(59)=S(787)=123
S(60)=S(786)=157
S(61)=S(785)=201
S(62)=S(784)=252
S(63)=S(783)=318
S(64)=S(782)=393
.........
往下我还真是算不了了。

cooooldog

王守恩 发表于 2017-8-28 14:24
1，任取两两不等的9个数相加，和最小是45，最大是801。
2，我们用S(45)=1表示和45的拆分方法是1种。
3， ...

这题一般情况我自己也做不出的; 用计算机穷举小的数字还行;大一些就困难了.

我现在出的这数字, 是一般的个人电脑穷举也会有难度的.
如果是类似于80里面取5个,则稍好的电脑穷举还是很快的.

乌克兰基辅大学一位今年40岁的教授给出一种构造稍微特殊一点的核心思想仍然围绕二项式的方法,从多个这样特殊的基于二项式的特殊式子里面, 找出特殊项系数并求和, 可以计算出所要的频数. 即使知道这个方法,不依赖计算机来计算相应的二项式系数也还是需要技巧.

我花了几天看明白;不得不佩服俄罗斯乌克兰这些大学,数学方面真是牛人多. 反观国内,尽出喜欢瞎起哄的民科,一点不务实,不正视自己,要么基础本来不行,要么好大喜功总想投机偷懒弄个大新闻.

不要试图跟新闻里的张益唐比; 张益唐这种起码是北大高材生+国外拿到博士学位,还顺便证明了,如果导师的论文结论成立,则黎曼猜想可以证明.

Ysu2008

我把题意理解错了……

luyuanhong

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

解  这个问题，看来没有简单的解法，只能用计算机穷举搜索。

    当 n 和 k 比较大时，计算机搜索所用的时间很长。下面举一个数字比较小的例子：

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

    用计算机搜索，可得结果如下：

(0)
   1+ 2+ 7   1+ 3+ 6   1+ 4+ 5   1+ 7+12   1+ 8+11   1+ 9+10   2+ 3+ 5   2+ 6+12
   2+ 7+11   2+ 8+10   3+ 5+12   3+ 6+11   3+ 7+10   3+ 8+ 9   4+ 5+11   4+ 6+10
   4+ 7+ 9   5+ 6+ 9   5+ 7+ 8   7+11+12   8+10+12   9+10+11
                                                               n=22
(1)
   1+ 2+ 8   1+ 3+ 7   1+ 4+ 6   1+ 8+12   1+ 9+11   2+ 3+ 6   2+ 4+ 5   2+ 7+12
   2+ 8+11   2+ 9+10   3+ 6+12   3+ 7+11   3+ 8+10   4+ 5+12   4+ 6+11   4+ 7+10
   4+ 8+ 9   5+ 6+10   5+ 7+ 9   6+ 7+ 8   8+11+12   9+10+12
                                                               n=22
(2)
   1+ 2+ 9   1+ 3+ 8   1+ 4+ 7   1+ 5+ 6   1+ 9+12   1+10+11   2+ 3+ 7   2+ 4+ 6
   2+ 8+12   2+ 9+11   3+ 4+ 5   3+ 7+12   3+ 8+11   3+ 9+10   4+ 6+12   4+ 7+11
   4+ 8+10   5+ 6+11   5+ 7+10   5+ 8+ 9   6+ 7+ 9   9+11+12
                                                               n=22
(3)
   1+ 2+10   1+ 3+ 9   1+ 4+ 8   1+ 5+ 7   1+10+12   2+ 3+ 8   2+ 4+ 7   2+ 5+ 6
   2+ 9+12   2+10+11   3+ 4+ 6   3+ 8+12   3+ 9+11   4+ 7+12   4+ 8+11   4+ 9+10
   5+ 6+12   5+ 7+11   5+ 8+10   6+ 7+10   6+ 8+ 9  10+11+12
                                                               n=22
(4)
   1+ 2+11   1+ 3+10   1+ 4+ 9   1+ 5+ 8   1+ 6+ 7   1+11+12   2+ 3+ 9   2+ 4+ 8
   2+ 5+ 7   2+10+12   3+ 4+ 7   3+ 5+ 6   3+ 9+12   3+10+11   4+ 8+12   4+ 9+11
   5+ 7+12   5+ 8+11   5+ 9+10   6+ 7+11   6+ 8+10   7+ 8+ 9
                                                               n=22
(5)
   1+ 2+12   1+ 3+11   1+ 4+10   1+ 5+ 9   1+ 6+ 8   2+ 3+10   2+ 4+ 9   2+ 5+ 8
   2+ 6+ 7   2+11+12   3+ 4+ 8   3+ 5+ 7   3+10+12   4+ 5+ 6   4+ 9+12   4+10+11
   5+ 8+12   5+ 9+11   6+ 7+12   6+ 8+11   6+ 9+10   7+ 8+10
                                                               n=22
(6)
   1+ 2+ 3   1+ 3+12   1+ 4+11   1+ 5+10   1+ 6+ 9   1+ 7+ 8   2+ 3+11   2+ 4+10
   2+ 5+ 9   2+ 6+ 8   3+ 4+ 9   3+ 5+ 8   3+ 6+ 7   3+11+12   4+ 5+ 7   4+10+12
   5+ 9+12   5+10+11   6+ 8+12   6+ 9+11   7+ 8+11   7+ 9+10
                                                               n=22
(7)
   1+ 2+ 4   1+ 4+12   1+ 5+11   1+ 6+10   1+ 7+ 9   2+ 3+12   2+ 4+11   2+ 5+10
   2+ 6+ 9   2+ 7+ 8   3+ 4+10   3+ 5+ 9   3+ 6+ 8   4+ 5+ 8   4+ 6+ 7   4+11+12
   5+10+12   6+ 9+12   6+10+11   7+ 8+12   7+ 9+11   8+ 9+10
                                                               n=22
(8)
   1+ 2+ 5   1+ 3+ 4   1+ 5+12   1+ 6+11   1+ 7+10   1+ 8+ 9   2+ 4+12   2+ 5+11
   2+ 6+10   2+ 7+ 9   3+ 4+11   3+ 5+10   3+ 6+ 9   3+ 7+ 8   4+ 5+ 9   4+ 6+ 8
   5+ 6+ 7   5+11+12   6+10+12   7+ 9+12   7+10+11   8+ 9+11
                                                               n=22
(9)
   1+ 2+ 6   1+ 3+ 5   1+ 6+12   1+ 7+11   1+ 8+10   2+ 3+ 4   2+ 5+12   2+ 6+11
   2+ 7+10   2+ 8+ 9   3+ 4+12   3+ 5+11   3+ 6+10   3+ 7+ 9   4+ 5+10   4+ 6+ 9
   4+ 7+ 8   5+ 6+ 8   6+11+12   7+10+12   8+ 9+12   8+10+11
                                                               n=22

    从上述计算结果来看，虽然 1～12 中各种末位数出现的频数并不相同，但是三个数之和的

末位数等于 0,1,2,…,9 的频数却相同，都是 22 。

cooooldog

luyuanhong 发表于 2017-8-29 09:10
题  从 1～n 中取 k 个不同的数相加求和，求这个和的末位数等于 0,1,2,…,9 的频数。

解  这个问题，看 ...

陆老师, 您可以试试从 1~15 中取3个

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

93中取9个的参考结果是这样的,

{96183567106, 96183599743, 96183567106, 96183599743, 96183567106,
96183599743, 96183567106, 96183599743, 96183567106, 96183599743}

最简单的证伪一般情况下"等频数"的办法是,求组合数(二项式系数  n \choose k)
12取3是一个特例, 刚好 220
93取9得到, 961835834245, 除以10有小数次频数

答案在下面二维码对应的链接中,原文是英文:

王守恩

谢谢楼主！给我们出了道好题。
此题与下面的题目是同一道题。
请看
1，1个“+”号，有2个算式。
    1+1
     1+2
2，2个“+”号，有3个算式。
    1+1+1
     1+1+2
     1+2+3
3，3个“+”号，有5个算式。
    1+1+1+1
     1+1+1+2
     1+1+2+2
     1+1+2+3
     1+2+3+4
4，4个“+”号，有7个算式。
    1+1+1+1+1
     1+1+1+1+2
     1+1+1+2+2
     1+1+1+2+3
     1+1+2+2+3
     1+1+2+3+4
     1+2+3+4+5
5，5个“+”号，有11个算式。
    1+1+1+1+1+1
     1+1+1+1+1+2
     1+1+1+1+2+2
     1+1+1+1+2+3
     1+1+1+2+2+2
     1+1+1+2+2+3
     1+1+1+2+3+4
     1+1+2+2+3+3
     1+1+2+2+3+4
     1+1+2+3+4+5
     1+2+3+4+5+6
     ............
我们对每个算式约定如下：
1，第1个加数是“1”；
2，后面的加数比前面的加数要大；
3，相邻两个加数的差只能是“1”或“0”；
4，相同加数的个数：后面的个数不能比前面的多。
5，这串数是2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,
385,490,627,792,1002,1255,1575,1958,2436,3010,3718......

王守恩

45        801        1
46        800        1
47        799        2
48        798        3
49        797        5
50        796        7
51        795        11
52        794        15
53        793        22
54        792        30
55        791        41
56        790        54
57        789        73
58        788        94
59        787        123
60        786        157
61        785        201
62        784        252
63        783        318
64        782        393
65        781        488
66        780        598
67        779        732
68        778        887
69        777        1076
70        776        1291
71        775        1549
72        774        1845
73        773        2194
74        772        2592
75        771        3060
76        770        3589
77        769        4206
78        768        4904
79        767        5708
80        766        6615
81        765        7657
82        764        8824
83        763        10156
84        762        11648
85        761        13338
86        760        15224
87        759        17354
88        758        19720
89        757        22380
90        756        25331
91        755        28629
92        754        32278
93        753        36347
94        752        40831
95        751        45812
96        750        51294
97        749        57358
98        748        64015
99        747        71362
100        746        79403
101        745        88252
102        744        97922
103        743        108527
104        742        120092
105        741        132751
106        740        146520
107        739        161554
108        738        177884
109        737        195666
110        736        214944
111        735        235899
112        734        258569
113        733        283161
114        732        309729
115        731        338484
116        730        369499
117        729        403016
118        728        439100
119        727        478025
120        726        519880
121        725        564945
122        724        613331
123        723        665355
124        722        721125
125        721        780997
126        720        845105
127        719        913815
128        718        987292
129        717        1065947
130        716        1149940
131        715        1239730
132        714        1335513
133        713        1437762
134        712        1546707
135        711        1662875
136        710        1786498
137        709        1918159
138        708        2058130
139        707        2207014
140        706        2365128
141        705        2533138
142        704        2711363
143        703        2900536
144        702        3101027
145        701        3313594
146        700        3538657
147        699        3777049
148        698        4029199
149        697        4296017
150        696        4577988
151        695        4876054
152        694        5190763
153        693        5523142
154        692        5873748
155        691        6243698
156        690        6633618
157        689        7044663
158        688        7477526
159        687        7933460
160        686        8413176
161        685        8918027
162        684        9448798
163        683        10006888
164        682        10593163
165        681        11209130
166        680        11855672
167        679        12534410
168        678        13246314
169        677        13993056
170        676        14775691
171        675        15596013
172        674        16455101
173        673        17354873
174        672        18296499
175        671        19281955
176        670        20312509
177        669        21390268
178        668        22516522
179        667        23693514
180        666        24922637
181        665        26206195
182        664        27545681
183        663        28943542
184        662        30401298
185        661        31921540
186        660        33505891
187        659        35157009
188        658        36876627
189        657        38667552
190        656        40531537
191        655        42471543
192        654        44489436
193        653        46588241
194        652        48769932
195        651        51037692
196        650        53393516
197        649        55840744
198        648        58381479
199        647        61019126
200        646        63755901
201        645        66595368
202        644        69539751
203        643        72592776
204        642        75756778
205        641        79035540
206        640        82431501
207        639        85948605
208        638        89589293
209        637        93357667
210        636        97256267
211        635        101289245
212        634        105459243
213        633        109770567
214        632        114225838
215        631        118829517
216        630        123584320
217        629        128494739
218        628        133563574
219        627        138795465
220        626        144193176
221        625        149761487
222        624        155503235
223        623        161423215
224        622        167524336
225        621        173811523
226        620        180287616
227        619        186957668
228        618        193824577
229        617        200893381
230        616        208167022
231        615        215650651
232        614        223347116
233        613        231261670
234        612        239397187
235        611        247758877
236        610        256349637
237        609        265174762
238        608        274237010
239        607        283541755
240        606        293091757
241        605        302892307
242        604        312946148
243        603        323258630
244        602        333832322
245        601        344672617
246        600        355782044
247        599        367165875
248        598        378826593
249        597        390769489
250        596        402996819
251        595        415513886
252        594        428322873
253        593        441428912
254        592        454834092
255        591        468543531
256        590        482559047
257        589        496885726
258        588        511525264
259        587        526482531
260        586        541759093
261        585        557359760
262        584        573285767
263        583        589541854
264        582        606129097
265        581        623051964
266        580        640311348
267        579        657911619
268        578        675853292
269        577        694140619
270        576        712773902
271        575        731757073
272        574        751090214
273        573        770777110
274        572        790817402
275        571        811214719
276        570        831968452
277        569        853081852
278        568        874554037
279        567        896388074
280        566        918582594
281        565        941140461
282        564        964060005
283        563        987343667
284        562        1010989469
285        561        1034999623
286        560        1059371606
287        559        1084107393
288        558        1109204129
289        557        1134663313
290        556        1160481737
291        555        1186660641
292        554        1213196234
293        553        1240089481
294        552        1267336216
295        551        1294936893
296        550        1322886970
297        549        1351186608
298        548        1379830634
299        547        1408818914
300        546        1438145884
301        545        1467810859
302        544        1497807868
303        543        1528135918
304        542        1558788388
305        541        1589763966
306        540        1621055615
307        539        1652661456
308        538        1684574041
309        537        1716791167
310        536        1749304709
311        535        1782112145
312        534        1815204938
313        533        1848579981
314        532        1882228317
315        531        1916146522
316        530        1950324966
317        529        1984759905
318        528        2019441296
319        527        2054364816
320        526        2089520024
321        525        2124902287
322        524        2160500490
323        523        2196309704
324        522        2232318431
325        521        2268521171
326        520        2304906043
327        519        2341467270
328        518        2378192329
329        517        2415075170
330        516        2452102912
331        515        2489268968
332        514        2526560123
333        513        2563969544
334        512        2601483400
335        511        2639094636
336        510        2676789120
337        509        2714559293
338        508        2752390731
339        507        2790275688
340        506        2828199183
341        505        2866153296
342        504        2904122796
343        503        2942099318
344        502        2980067414
345        501        3018018588
346        500        3055936887
347        499        3093813715
348        498        3131632951
349        497        3169385612
350        496        3207055425
351        495        3244633357
352        494        3282102714
353        493        3319454433
354        492        3356671724
355        491        3393745219
356        490        3430658073
357        489        3467400943
358        488        3503956636
359        487        3540315872
360        486        3576461465
361        485        3612383904
362        484        3648066032
363        483        3683498462
364        482        3718663790
365        481        3753552777
366        480        3788148113
367        479        3822440426
368        478        3856412545
369        477        3890055309
370        476        3923351387
371        475        3956291870
372        474        3988859635
373        473        4021045724
374        472        4052833246
375        471        4084213559
376        470        4115169723
377        469        4145693438
378        468        4175768064
379        467        4205385354
380        466        4234529015
381        465        4263191205
382        464        4291355669
383        463        4319015011
384        462        4346153390
385        461        4372763545
386        460        4398830071
387        459        4424346213
388        458        4449296711
389        457        4473675337
390        456        4497467330
391        455        4520666691
392        454        4543259199
393        453        4565239437
394        452        4586593406
395        451        4607316307
396        450        4627394737
397        449        4646824193
398        448        4665591885
399        447        4683693975
400        446        4701117983
401        445        4717860750
402        444        4733910457
403        443        4749264314
404        442        4763911196
405        441        4777849031
406        440        4791067057
407        439        4803563947
408        438        4815329672
409        437        4826363315
410        436        4836655586
411        435        4846206342
412        434        4855006717
413        433        4863057344
414        432        4870350125
415        431        4876886147
416        430        4882658102
417        429        4887667871
418        428        4891908593
419        427        4895382960
420        426        4898084917
421        425        4900017619
422        424        4901175813
423        423        4901563471
　        　        483368698858
合计 483368698858 ×2-4901563471=961835834245
说明：我已经找到方法了，每一个S我都是用公式得出来的，
肯定没有用计算机穷举搜索，我也无法用计算机穷举搜索。
谢谢cooooldog、谢谢luyuanhong、谢谢天山草。