I have an urn with $100$ balls. Each ball has a number in it, from $1$ to $100$. I take three balls from the urn without putting the balls again in the urn. I sum the three numbers obtained. What's the probability that the sum of the three numbers is more than $100$?
How to explain the procedure to calculate this probability?
On
It is often interesting to compare different methods, and usually a good idea to check theoretical work using computational methods.
In this instance, it is a simple one-liner to evaluate every possible way of choosing 3 different balls (without replacement) from 100 balls (numbered from 1 to 100), sum all the combinations, and compute the exact probability.
Here is Mathematica code to do this ... just a one-liner:
Z = Map[Total, Permutations[Range[100],{3}]]; Count[Z, x_ /; x>100]/Length[Z]
... which returns the exact solution as:
$$\text{P(sum > 100)} = \frac{33991}{40425}$$
... which is $\approx 0.840841$. It only takes a fraction of a second to evaluate.
By contrast:
The theoretical derivation posted by Jack D'Aurizio above obtained the result:
$$\text{P(sum > 100)} = 1-\frac{26561}{\binom{100}{3}} \approx 0.835739$$
The latter (accepted answer) appears to be in error. [ Update: Now resolved :) ]
On
Here's a C# solution. My original (wrong) solution divided by 1000000. It was wrong because it counted cases with duplicate numbers. This version below divides by the correct number.
static void Main(string[] args)
{
int count = 100 * 100 * 100;
int hits = 0;
for (int i = 1; i <= 100; i++)
{
for (int j = 1; j <= 100; j++)
{
for (int k = 1; k <= 100; k++)
{
if (i == j || i == k || j == k)
count--;
else if (i + j + k > 100)
hits++;
}
}
}
Console.WriteLine(hits);
Console.WriteLine(count);
double percent = (double)hits / (double)count;
Console.WriteLine(percent);
Console.ReadLine();
}
And in python:
import itertools
z=map(sum, itertools.permutations(range(1,101),3))
len(filter(lambda x: x>100, z))*1.0/len(z)
Yields:
0.8408410636982065
We know there are 100_C_3 ways to draw 3 numbers from 1 to 100 without replacement.
Let's look at counting the number of ways to draw three numbers that add up to 100 or less.
First, let's solve for drawing two numbers:
L = The limit
F = the first number
What is the number of ways to draw a second number S given the limit L and the first number F?
We know that F + 1 <= S <= L - F. If F + 1 > L - F, then there are 0 ways. If F + 1 <= L - F, then there are (L - F) - (F + 1) + 1 numbers in the range (F + 1) to (L - F). That reduces to L - 2F.
So:
W_2(L,F) = 0, If 2F+1 > L
W_2(L,F) = L - 2F, If 2F+1 <= L
We can compute W_2(L), for all valid F, by summing W_2(L,F) for F ranging from 1 to (L-1)/2:
...skipping the algebra...
If L is odd, W_2(L) = (L^2 - 2L + 1) / 4
If L is even, W_2(L) = (L^2 - 2L) / 4
Now, we can use this result in calculating the three-number problem:
If we have a first number F, then our second number, S, and third number, T, must satisfy: F < S < T F + S + T <= L
Assuming we have chosen an F small enough that there are S and T that can satisfy F + S + T <= L, then
W_3(L,F) = W_2(L - 3F)
W_3(L,F) = ((L-3F)^2-2*(L-3F)+1)/4, if 3F-L is odd
W_3(L,F) = ((L-3F)^2-2*(L-3F))/4, if 3F-L is even
Our upper limit for F is F + (F + 1) + (F + 2) <= L or F <= (L - 3) / 3
Finally, we can compute W_3(L) for all valid F, by summing W_3(L,F) for F ranging from 1 to I = Int((L-3)/3), where INT() rounds down to the nearest integer.
...skipping even more algebra...
If (L-3)/3 is even, W_3(L) = (6I^3-3(2L-5)I^2+2*(L^2-5L+5)I)/8
If (L-3)/3 is odd and L is even, W_3(L) = (6I^3-3(2L-5)I^2+2*(L^2-5L+5)I+1)/8
If (L-3)/3 is odd and L is odd, W_3(L) = (6I^3-3(2L-5)I^2+2*(L^2-5L+5)I-1)/8
For very large numbers, you can just use the first formula, since the adjustments only add or subtract 1/8.
To answer your question then,
When L = 100,
Int((L - 3) / 3) = 32
W_3(100) = 25,736
100_C_3 = 161,700
so your probability of drawing 3 balls whose sum exceeds 100 is:
(161,700 - 25,736) / 161,700 = 0.840841
On
Since I see other solutions relying on a bit of programing, I'll do it in SQL (which I often find very suited for combinatorics problems).
WITH
lvls AS (
SELECT LEVEL AS lvl
FROM dual
CONNECT BY LEVEL <= 100
),
combinations AS (
SELECT
l1.lvl AS nr_1,
l2.lvl AS nr_2,
l3.lvl AS nr_3,
l1.lvl + l2.lvl + l3.lvl AS total,
CASE
WHEN l1.lvl + l2.lvl + l3.lvl > 100
THEN 1
ELSE 0
END AS is_bigger
FROM lvls l1
JOIN lvls l2 ON (l1.lvl <> l2.lvl)
JOIN lvls l3 ON (l1.lvl <> l3.lvl AND l2.lvl <> l3.lvl)
)
SELECT
SUM(is_bigger) AS nr_bigger,
COUNT(*) AS nr_total,
SUM(is_bigger) / COUNT(*) AS chance
FROM combinations;
Which yields (unsuprisingly) $$\frac{815784}{970200} \approx 0,840841 $$
On
I post here the simulation code written in R:
rm(list = ls())
space = seq(1:100)
replication = 10000
prob=c()
for (j in 1:1000) {
result = c()
for (i in 1:replication) {
draw = sample(space,3, replace=FALSE)
s = sum(draw)
outcome = FALSE
if (s > 100) {
outcome=TRUE
}
result = c(result, outcome)
}
prob = c(prob,sum(result)/replication)
}
P = mean(prob)
We have to count the number of three elements subsets of $\{1,\ldots,100\}$ having sum greater than $100$, or $\leq 100$. For first, we have that the number of lattice points $(x,y,z)\in[1,100]^3$ such that $(x+y+z)\leq 100$ is given by: $$\sum_{x=1}^{98}\left|\{(y,z)\in[1,100]^2:y+z\leq 100-x\}\right|=\sum_{x=1}^{98}\binom{100-x}{2}=\binom{100}{3}.$$ Obviously, not every lattice point gives a valid subset. Among the previously counted lattice points, there are $33$ points of the type $(x,x,x)$ and $3\cdot 2417=7251$ points of the type $(u,u,v),(u,v,u)$ or $(v,u,u)$ with $u\neq v$. Hence the number of three elements subsets of $\{1,\ldots,100\}$ with sum $\leq 100$ is given by: $$\frac{1}{6}\left(\binom{100}{3}-7251-33\right) = 25736 $$ so the wanted probability is: $$ 1-\frac{25736}{\binom{100}{3}} $$ that is between $\frac{280}{333}$ and $\frac{37}{44}$.