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

Home > Probability
Random numbers sum together (Posted on 2015-05-15) Difficulty: 2 of 5
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 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.014998470
100 0.004950000 0.014850000

  Posted by Charlie on 2015-05-15 11:01:51
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 (8)
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