All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Random Sum Resolution (Posted on 2016-06-06) Difficulty: 3 of 5
Five random positive integers are chosen independently with equal probability from 1 to N inclusively, where N is a positive integer.

Find the probability that:

(i) The number chosen last is equal to the sum of the four numbers that were chosen first.

(ii) The largest number chosen is the sum of the other four.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution Comment 1 of 1
There are n^5 total outcomes overall.

For n < 4 there are no ways the last number could equal the sum of the first four.

There is 1 way the last could be a 4 and have the first four add up to it.
There are 4 ways the last could be a 5 and have the first four add up to it.
...
There are C(k+3-4,3) ways the last could be k and have the first four add up to it.
i.e., There are C(k-1,3) ways the last could be k and have the first four add up to it.
...
There are C(n-1,3) ways the last could be n and have the first four add up to it.

(i) Sigma{k=4 to n} C(k-1,3) / n^5


(ii) When success (positive result) is found by chance in part (i), it is also necessarily a success in part (ii).

Call the success event of part (i) S, and that of part (ii) T, and use the | symbol to represent "given":

P(S) = P(T)*P(S|T)

My first thought was that P(S|T) was 1/5; my second thought was that this ignores cases where two of the numbers equal the max; but on third thought, no two numbers could equal the max, as one of the maxes would be the total, which must be larger than any of the four positive addends.

So P(S) = P(T)/5

P(T) = 5*P(S) = 5 * Sigma{k=4 to n} C(k-1,3) / n^5

               reduced
 N  num  den   fraction     decimal     times 5 for part ii
 4   1  1024   1//1024   0.0009765625   0.0048828125 
 5   5  3125   1//625   0.0016   0.008 
 6   15  7776   5//2592   0.0019290123456790122   0.0096450617283950616 
 7   35  16807   5//2401   0.0020824656393169512   0.0104123281965847563 
 8   70  32768   35//16384   0.00213623046875   0.01068115234375       ** maximum here **
 9   126  59049   14//6561   0.002133821063862216   0.0106691053193110805 
 10   210  100000   21//10000   0.0021   0.0105 
 11   330  161051   30//14641   0.002049040366095212   0.0102452018304760603 
 12   495  248832   55//27648   0.0019892939814814814   0.0099464699074074073 
 13   715  371293   55//28561   0.0019257028815517663   0.0096285144077588319 
 14   1001  537824   143//76832   0.0018612036651395251   0.0093060183256976259 
 15   1365  759375   91//50625   0.0017975308641975308   0.0089876543209876542 
 16   1820  1048576   455//262144   0.001735687255859375   0.008678436279296875 
 17   2380  1419857   140//83521   0.0016762251409825073   0.0083811257049125369 
 18   3060  1889568   85//52488   0.0016194177716811461   0.0080970888584057307 
 19   3876  2476099   204//130321   0.0015653655205224023   0.0078268276026120118 
 20   4845  3200000   969//640000   0.0015140625   0.0075703125 
 21   5985  4084101   95//64827   0.0014654387832230397   0.0073271939161151989 
 22   7315  5153632   665//468512   0.0014193873369305374   0.0070969366846526876 
 23   8855  6436343   385//279841   0.001375781247208236   0.0068789062360411804 
 24   10626  7962624   1771//1327104   0.0013344847125771604   0.0066724235628858024 
 25   12650  9765625   506//390625   0.00129536   0.0064768 
 26   14950  11881376   575//456976   0.0012582717691957564   0.0062913588459787822 
 27   17550  14348907   650//531441   0.0012230896750532984   0.0061154483752664924 
 28   20475  17210368   2925//2458624   0.0011896898427738442   0.0059484492138692211 
 29   23751  20511149   819//707281   0.0011579556074601183   0.0057897780373005919 
 30   27405  24300000   203//180000   0.0011277777777777777   0.0056388888888888888 
 31   31465  28629151   1015//923521   0.0010990545964845412   0.0054952729824227061 
 32   35960  33554432   4495//4194304   0.0010716915130615234   0.0053584575653076171 
 33   40920  39135393   1240//1185921   0.0010456008452502316   0.0052280042262511583 
 34   46376  45435424   341//334084   0.0010207013804911339   0.0051035069024556698 
 35   52360  52521875   1496//1500625   0.0009969179508538108   0.0049845897542690545 
 36   58905  60466176   6545//6718464   0.0009741810032769394   0.0048709050163846974 
 37   66045  69343957   1785//1874161   0.0009524261789675486   0.0047621308948377433 
 38   73815  79235168   3885//4170272   0.0009315939104211907   0.0046579695521059537 
 39   82251  90224199   703//771147   0.0009116290408962233   0.004558145204481117 
 40   91390  102400000   9139//10240000   0.00089248046875   0.00446240234375 
 41   101270  115856201   2470//2825761   0.0008741008174435134   0.0043705040872175671 
 42   111930  130691232   2665//3111696   0.0008564461309845177   0.0042822306549225888 
 43   123410  147008443   2870//3418801   0.0008394755939289826   0.0041973779696449134 
 44   135751  164916224   12341//14992384   0.000823151274673861   0.0041157563733693053 
 45   148995  184528125   3311//4100625   0.0008074378905654625   0.0040371894528273128 
 46   163185  205962976   7095//8954912   0.0007923025932583145   0.0039615129662915726 
 47   178365  229345007   3795//4879681   0.0007777147727484644   0.0038885738637423224 
 48   194580  254803968   5405//7077888   0.0007636458785445601   0.0038182293927228009 
 49   211876  282475249   4324//5764801   0.0007500692565103287   0.0037503462825516439 
 50   230300  312500000   2303//3125000   0.00073696   0.0036848 
 51   249900  345025251   4900//6765201   0.0007242948140047871   0.0036214740700239357 
 52   270725  380204032   20825//29246464   0.0007120518911277615   0.0035602594556388081 
 53   292825  418195493   5525//7890481   0.0007002107983024101   0.003501053991512051 
 54   316251  459165024   11713//17006112   0.0006887523732643886   0.0034437618663219435 
 55   341055  503284375   6201//9150625   0.0006776586298750085   0.0033882931493750426 
 56   367290  550731776   26235//39337984   0.0006669126714780299   0.0033345633573901498 
 57   395010  601692057   770//1172889   0.0006564986115480663   0.0032824930577403317 
 58   424270  656356768   7315//11316496   0.0006464015009593075   0.0032320075047965376 
 59   455126  714924299   7714//12117361   0.0006366072612675317   0.0031830363063376588 
 60   487635  777600000   32509//51840000   0.00062710262345679   0.0031355131172839506 
 61   521855  844596301   8555//13845841   0.0006178750716550911   0.0030893753582754561 
 62   557845  916132832   17995//29552672   0.0006089127913712844   0.0030445639568564222 
 63   595665  992436543   9455//15752961   0.0006002046218485527   0.0030010231092427639 
 64   635376  1073741824   39711//67108864   0.0005917400121688842   0.0029587000608444213 
 65   677040  1160290625   10416//17850625   0.0005835089807779839   0.0029175449038899197 
 66   720720  1252332576   455//790614   0.0005755020781316799   0.0028775103906583996 
 67   766480  1350125107   11440//20151121   0.0005677103521933096   0.0028385517609665487 
 68   814385  1453933568   47905//85525504   0.0005601253165371582   0.0028006265826857915 
 69   864501  1564031349   12529//22667121   0.0005527389208360426   0.0027636946041802132 
 70   916895  1680700000   26197//48020000   0.0005455435235318616   0.0027277176176593085 
 71   971635  1804229351   13685//25411681   0.000538531866506588   0.0026926593325329402 
 72   1028790  1934917632   57155//107495424   0.0005316970515879819   0.00265848525793991 
 73   1088430  2073071593   14910//28398241   0.0005250325187394529   0.0026251625936972645 
 74   1150626  2219006624   15549//29986576   0.0005185320257971433   0.0025926601289857167 
 75   1215450  2373046875   5402//10546875   0.0005121896296296296   0.0025609481481481481 
 76   1282975  2535525376   67525//133448704   0.0005059996686067479   0.0025299983430337397 
 77   1353275  2706784157   17575//35153041   0.000499956746274099   0.002499783731370495 
 78   1426425  2887174368   36575//74030112   0.0004940557161388597   0.002470278580694299 
 79   1502501  3077056399   19019//38950081   0.0004882916674807428   0.0024414583374037142 
 80   1581580  3276800000   79079//163840000   0.0004826599121093749   0.0024132995605468749 
 81   1663740  3486784401   20540//43046721   0.0004771559719961016   0.0023857798599805081 
 82   1749060  3707398432   10665//22606088   0.0004717755677143254   0.0023588778385716272 
 83   1837620  3939040643   22140//47458321   0.0004665146076280279   0.0023325730381401398 
 84   1929501  4182119424   3403//7375872   0.00046136917777315   0.0023068458888657503 
 85   2024785  4437053125   23821//52200625   0.0004563355323810777   0.002281677661905389 
 86   2123555  4704270176   49385//109401632   0.000451410084997635   0.0022570504249881756 
 87   2225895  4984209207   25585//57289761   0.0004465894001547676   0.002232947000773838 
 88   2331890  5277319168   105995//239878144   0.000441870185555546   0.0022093509277777303 
 89   2441626  5584059449   27434//62742241   0.0004372492847362592   0.0021862464236812962 
 90   2555190  5904900000   28391//65610000   0.0004327236701722298   0.0021636183508611491 
 91   2672670  6240321451   29370//68574961   0.0004282904367966027   0.0021414521839830138 
 92   2794155  6590815232   121485//286557184   0.0004239467959037453   0.0021197339795187266 
 93   2919735  6956883693   10465//24935067   0.0004196900694110827   0.0020984503470554139 
 94   3049501  7339040224   64883//156149792   0.0004155176844551928   0.0020775884222759643 
 95   3183545  7737809375   33511//81450625   0.0004114271682998135   0.0020571358414990676 
 96   3321960  8153726976   138415//339738624   0.0004074161435350959   0.0020370807176754798 
 97   3464840  8587340257   35720//88529281   0.0004034823235489735   0.0020174116177448678 
 98   3612280  9039207968   9215//23059204   0.0003996235082529301   0.0019981175412646507 
 99   3764376  9509900499   38024//96059601   0.0003958375800457467   0.0019791879002287339 
 100   3921225  10000000000   156849//400000000   0.0003921225   0.0019606125 

    4   kill "rndsumrs.txt"
    5   open "rndsumrs.txt" for output as #2
   10   for N=4 to 100
   20    Tot=0
   30    for K=4 to N
   40       Tot=Tot+combi(K-1,3)
   50    next
   60    print N,Tot;N^5,Tot//N^5,Tot/N^5,5*Tot/N^5
   65    print #2,N,Tot;N^5,Tot//N^5,Tot/N^5,5*Tot/N^5
   70   next N
   75   close #2

Simulation for n=6 (as in the roll of a 5 dice (part ii), or one die 5 times (part i))

DefDbl A-Z
Dim crlf$


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 n = 6
 
 For tr = 1 To 10000
   tot = 0: high = 0
   For i = 1 To 5
     r = Int(Rnd(1) * n + 1)
     tot = tot + r
     If r > high Then high = r
   Next
   tot = tot - high
   If high = tot Then part2 = part2 + 1
   If r = tot Then part1 = part1 + 1
 Next
 
 Text1.Text = Text1.Text & part1 / 10000 & Str(part2 / 10000) & crlf
 
 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

finding

0.0018 .0095

comparing favorably (off by only 1 count in each number) to the expected

0.0019290123456790122   0.0096450617283950616 

with Randomize Timer added, and each run changed to 100,000 trials, several runs gave

0.00217 .01022
0.00204 .01009
0.00186 .00976
0.00196 .00934
0.002 .00963

Here are single sets of results for 100,000 trials each of n = 3 through 25:

 n      i       ii
 3  0.00000  0.00000
 4  0.00094  0.00526
 5  0.00158  0.00822
 6  0.00183  0.00926
 7  0.00229  0.01045
 8  0.00229  0.01066
 9  0.00214  0.01075
10  0.00194  0.01021
11  0.00199  0.01033
12  0.00191  0.00987
13  0.00190  0.00942
14  0.00179  0.00909
15  0.00186  0.00884
16  0.00175  0.00872
17  0.00166  0.00834
18  0.00167  0.00791
19  0.00141  0.00781
20  0.00170  0.00832
21  0.00153  0.00739
22  0.00154  0.00690
23  0.00129  0.00678
24  0.00131  0.00661
25  0.00130  0.00631

and a second set

 3  0.00000  0.00000
 4  0.00086  0.00486
 5  0.00148  0.00774
 6  0.00180  0.00950
 7  0.00201  0.01026
 8  0.00200  0.01058
 9  0.00212  0.01052
10  0.00236  0.01091
11  0.00191  0.00993
12  0.00207  0.00996
13  0.00192  0.00970
14  0.00161  0.00894
15  0.00176  0.00922
16  0.00185  0.00845
17  0.00183  0.00845
18  0.00169  0.00814
19  0.00158  0.00792
20  0.00165  0.00801
21  0.00174  0.00806
22  0.00129  0.00679
23  0.00135  0.00666
24  0.00138  0.00681
25  0.00159  0.00719

  Posted by Charlie on 2016-06-06 10:51:52
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information