 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Random numbers sum together (Posted on 2015-05-15) If three random integers are independently chosen from 1 to n, what is the probability that the first two sum to the third?

Source: Quora

 No Solution Yet Submitted by Jer No Rating Comments: ( Back to comment list | You must be logged in to post comments.) solution: as presented and with a complication | Comment 1 of 3
The problem as written is the easier of two similar puzzles. This one asks for the probability that the one chosen third is equal to the sum of the two that were chosen first.  A harder problem would be the probability that the largest, whichever it is, is the sum of the other two.

The easier one:

call {1,...,n} = N
| represents "given"

n=2
p(r1+r2 is in N) = 1/4
p(r3 is r1+r2 | r1+r2 is in N) = 1/2

P=1/4 * 1/2 = 1/8

n=3
p(r1+r2 is in N) = 3/9 = 1/3
p(r3 is r1+r2 | r1+r2 is in N) = 1/3

P = 1/3 * 1/3 = 1/9

`  O O O  * O O  * * O`

General
p(r1+r2 is in N) = Tr(n-1) / n^2,
where Tr(n-1) is the (n-1)st triangular number
p(r3 is r1+r2 | r1+r2 is in N) = 1/n

P = Tr(n-1) / n^3 = n*(n-1)/2 / n^3 = (n-1)/(2*n^2)

`  O O O O  * O O O  * * O O  * * * O     showing basis for p(r1+r2 is in N) = Tr(n-1) / n^2`

The harder one:

It's actually not too much harder once you see the right strategy. The easiest strategy is to still treat it chronologically. We've already found the probability that the third is the sum of the first and second. To complete the solution for the largest being the sum of the other two, we need only find the probability that the third integer chosen is the absolute difference between the first two chosen.  This situation is mutually exclusive of the case where the third is the sum of the first two, and also completes the set of cases where the largest is the sum of the other two.

For any pair (a,b) of the first two integers chosen, the absolute difference lies in the range 0,...,n-1, so the probability that the third chosen will be this absolute difference is (n-1)/n^2. Thus the overall probability is (n-1)/(2*n^2) + (n-1)/n^2 = 3*(n-1)/(2*n^2).

This actually surprised me, that the probability of the largest (that is, any, as the sum has to be the largest) is the sum of the other two, is 3 times the probability that the last is the sum of the first two. I thought the conditional probabilities would be more complicated and affect the result.

Tabulated:

` n      p1          p2  1 0.000000000 0.000000000  2 0.125000000 0.375000000  3 0.111111111 0.333333333  4 0.093750000 0.281250000  5 0.080000000 0.240000000  6 0.069444444 0.208333333  7 0.061224490 0.183673469  8 0.054687500 0.164062500  9 0.049382716 0.148148148 10 0.045000000 0.135000000 11 0.041322314 0.123966942 12 0.038194444 0.114583333 13 0.035502959 0.106508876 14 0.033163265 0.099489796 15 0.031111111 0.093333333 16 0.029296875 0.087890625 17 0.027681661 0.083044983 18 0.026234568 0.078703704 19 0.024930748 0.074792244 20 0.023750000 0.071250000 21 0.022675737 0.068027211 22 0.021694215 0.065082645 23 0.020793951 0.062381853 24 0.019965278 0.059895833 25 0.019200000 0.057600000 26 0.018491124 0.055473373 27 0.017832647 0.053497942 28 0.017219388 0.051658163 29 0.016646849 0.049940547 30 0.016111111 0.048333333 31 0.015608741 0.046826223 32 0.015136719 0.045410156 33 0.014692378 0.044077135 34 0.014273356 0.042820069 35 0.013877551 0.041632653 36 0.013503086 0.040509259 37 0.013148283 0.039444850 38 0.012811634 0.038434903 39 0.012491782 0.037475345 40 0.012187500 0.036562500 41 0.011897680 0.035693040 42 0.011621315 0.034863946 43 0.011357491 0.034072472 44 0.011105372 0.033316116 45 0.010864198 0.032592593 46 0.010633270 0.031899811 47 0.010411951 0.031235853 48 0.010199653 0.030598958 49 0.009995835 0.029987505 50 0.009800000 0.029400000 51 0.009611688 0.028835063 52 0.009430473 0.028291420 53 0.009255963 0.027767889 54 0.009087791 0.027263374 55 0.008925620 0.026776860 56 0.008769133 0.026307398 57 0.008618036 0.025854109 58 0.008472057 0.025416171 59 0.008330939 0.024992818 60 0.008194444 0.024583333 61 0.008062349 0.024187046 62 0.007934443 0.023803330 63 0.007810532 0.023431595 64 0.007690430 0.023071289 65 0.007573964 0.022721893 66 0.007460973 0.022382920 67 0.007351303 0.022053910 68 0.007244810 0.021734429 69 0.007141357 0.021424071 70 0.007040816 0.021122449 71 0.006943067 0.020829201 72 0.006847994 0.020543981 73 0.006755489 0.020266467 74 0.006665449 0.019996348 75 0.006577778 0.019733333 76 0.006492382 0.019477147 77 0.006409175 0.019227526 78 0.006328074 0.018984221 79 0.006248999 0.018746996 80 0.006171875 0.018515625 81 0.006096632 0.018289895 82 0.006023200 0.018069601 83 0.005951517 0.017854551 84 0.005881519 0.017644558 85 0.005813149 0.017439446 86 0.005746349 0.017239048 87 0.005681068 0.017043203 88 0.005617252 0.016851756 89 0.005554854 0.016664563 90 0.005493827 0.016481481 91 0.005434126 0.016302379 92 0.005375709 0.016127127 93 0.005318534 0.015955602 94 0.005262562 0.015787687 95 0.005207756 0.015623269 96 0.005154080 0.015462240 97 0.005101499 0.015304496 98 0.005049979 0.015149938 99 0.004999490 0.014998470100 0.004950000 0.014850000`

 Posted by Charlie on 2015-05-15 11:01:51 Please log in:

 Search: Search body:
Forums (0)