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

 Random Sum Resolution (Posted on 2016-06-06)
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 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\$

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.0107510  0.00194  0.0102111  0.00199  0.0103312  0.00191  0.0098713  0.00190  0.0094214  0.00179  0.0090915  0.00186  0.0088416  0.00175  0.0087217  0.00166  0.0083418  0.00167  0.0079119  0.00141  0.0078120  0.00170  0.0083221  0.00153  0.0073922  0.00154  0.0069023  0.00129  0.0067824  0.00131  0.0066125  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.0105210  0.00236  0.0109111  0.00191  0.0099312  0.00207  0.0099613  0.00192  0.0097014  0.00161  0.0089415  0.00176  0.0092216  0.00185  0.0084517  0.00183  0.0084518  0.00169  0.0081419  0.00158  0.0079220  0.00165  0.0080121  0.00174  0.0080622  0.00129  0.0067923  0.00135  0.0066624  0.00138  0.0068125  0.00159  0.00719`

 Posted by Charlie on 2016-06-06 10:51:52

 Search: Search body:
Forums (1)