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
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 |
solution: as presented and with a complication
