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

cooooldog · 发表于 2017-8-27 09:48

本帖最后由 luyuanhong 于 2017-9-8 11:34 编辑

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

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

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

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

ccmmjj · 发表于 2017-8-28 18:49

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

cooooldog · 发表于 2017-8-28 20:15

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

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

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

王守恩 · 发表于 2017-8-28 22:24

本帖最后由王守恩于 2017-8-29 20:17 编辑

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-29 09:48

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

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

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

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

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

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

Ysu2008 · 发表于 2017-8-29 14:53

本帖最后由 Ysu2008 于 2017-8-29 09:51 编辑

我把题意理解错了……

luyuanhong · 发表于 2017-8-29 17:10

本帖最后由 luyuanhong 于 2017-8-29 17:35 编辑

题  从 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 · 发表于 2017-8-29 17:20

本帖最后由 cooooldog 于 2017-8-29 09:27 编辑

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有小数次频数

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

王守恩 · 发表于 2017-8-29 20:02

本帖最后由王守恩于 2017-8-31 05:02 编辑

谢谢楼主！给我们出了道好题。
此题与下面的题目是同一道题。
请看
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......

王守恩 · 发表于 2017-9-5 08:43

本帖最后由王守恩于 2017-9-5 09:45 编辑

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、谢谢天山草。

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

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

点评

点评

本帖子中包含更多资源

点评